当前位置:   article > 正文

六大排序算法_6大排序算法

6大排序算法


前言

排序算法可以分为内部排序和外部排序。内部排序指的是数据的排序全部在内存中完成,而外部排序指的是排序数据量很大,内存中一次不能全部容纳,需要依靠外部存储来完成排序。

一、冒泡排序

假设给定一个数组arr,要求从小到大进行排序,从数组中第一个元素开始,遍历每一个位置的元素,将当前遍历的元素与其下一个元素进行比较,若当前元素更大,则与下一个元素交换位置,直至遍历完成整个数组(数组中最后一个元素除外),此时数组最右端的元素为最大值,接着对数组除最右端的元素的剩下的n-1个元素进行操作,再对数组除最右端的元素的剩下的n-2个元素进行操作,直至整个数组有序。

public class bubbleSort {
    public void bubbleSort(int[] arr){
        int n = arr.length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < arr.length - i - 1; j++){
                // 当前元素与下一个元素比较
                if(arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

根据代码,可以得出冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1)。

二、选择排序

假设给定一个数组arr,要求从小到大进行排序。遍历数组,找到其中最小的元素,与第一个位置的元素进行比较,若小则交换该元素与第一个元素的位置,接着找到其余n-1个元素的最小值,若小则交换该元素与第二个元素的位置,重复以上的操作,直至数组有序。

public void selectSort(int[] arr){
        int n = arr.length;
        for(int i = 0; i < n - 1; i++){
            int minIndex = i; //初始化最小元素的序号
            // 找到未排序数组中的最小元素
            for(int j = i + 1; j < n; j++){
                if(arr[j] < arr[i]){
                    minIndex = j;
                }
            }
            // 交换最小元素位置
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

该算法的时间复杂度为O(n),空间复杂度为O(1)。

三、插入排序

假设给定一个数组arr,要求从小到大进行排序。首先将第一个元素看作是有序的,将其余的元素根据大小插入到第一个元素的左右,形成有序序列,接着从剩下未排序的元素中遍历插入到有序序列中,直至数组有序。

public void insertSort(int[] arr){
        int n = arr.length;
        // 默认第一个元素已排序
        for(int i = 1; i < n - 1; i++){
            int j = i - 1;
            int waitSortElement = arr[i];
            while(j >= 0 && arr[j] > waitSortElement){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = waitSortElement;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

该算法的时间复杂度为O(n),空间复杂度为O(1)。

四、希尔排序

假设给定一个数组arr,要求从小到大进行排序。希尔排序也是插入排序的一种,希尔排序首先按一定的gap,即步长,将数组进行分组,一共gap组,组内进行插直接入排序,排序完成后,各个组内是有序的,接着gap变为原来的一半,继续进行相同的分组排序,直至整个数组有序。

public void insertShellSort(int[] arr, int gap, int index){
        for(int i = index + gap; i < arr.length; i += gap){
            int j = i - gap;
            int waitSortElement = arr[i];
            while(j >= 0 && arr[j] > waitSortElement){
                arr[j+gap] = arr[j];
                j -= gap;
            }
            arr[j+gap] = waitSortElement;
        }
    }
    
public void shellSort(int[] arr){
	int gap;
 	for(gap = arr.length / 2; gap < arr.length; gap /= 2){
    	for(int i = 0; i < gap; i++){
        	insertShellSort(arr, gap, i);
     	}
 	}
 }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

希尔算法的空间复杂度为O(1),时间复杂度未知,但优于直接插入排序。而且希尔算法也是不稳定的算法,假如数组中出现了两个相同的元素,经过排序后,这两个元素的相对位置可能发生变化,因此是不稳定的。

五、归并排序

归并排序算法的思想是分治的思想,首先将数组分成若干子表,当子表长度为1时,则认为子表是有序的,接着将子表两两合并,形成一个有序的新表,重复这一步骤,直至只有一个有序表,则归并排序完成。
left和right的开始输入为0和ar.length - 1。

public int[] mergeSort(int[] arr, int left, int right){
        // 数组长度为1,返回单个元素的数组
        if(left == right)
            return new int[]{arr[left]};
        int mid = 1 + (right - left) / 2;
        // 对左右两个数组进行归并
        int[] leftArr = mergeSort(arr, left, mid);
        int[] rightArr = mergeSort(arr, mid + 1, right);
        int[] newArr = new int[leftArr.length + rightArr.length];

        int i = 0;
        int j = 0;
        int k = 0;
        while(i < leftArr.length && j < rightArr.length){
            newArr[k++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        if(i < leftArr.length){
            newArr[k++] = leftArr[i++];
        }
        if(j < rightArr.length){
            newArr[k++] = rightArr[j++];
        }
        return newArr;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

归并排序的空间复杂度为O(n),因为使用了额外的数组空间,时间复杂度为O(nlogn),分治的过程类似于完全二叉树,利用递归的方法实现。

六、快速排序

快速排序的基本思想是通过一次排序将整个序列分成两部分,一部分比关键字小,一部分比关键字大,在分别对两部分进行快速排序,直至整个数组有序。一次快速排序的过程如下,通常初始化关键字为数组中的第一个元素,将序列中比它小的放在它之前,比它大的放在它之后。

public int[] quickSort(int[] arr, int start, int end){
        int key = arr[start];
        int left = start;
        int right = end;
        while(left < right){
            while(left < right && arr[right] > key){
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] < key){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = key;
        if(left > start){
            arr = quickSort(arr, start, left);
        }
        if(right < end){
            arr = quickSort(arr, left+1, end);
        }
        return arr;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

快速排序的空间复杂度为O(logn),时间复杂度的最好情况是O(nlogn),最坏情况是O(n^2)。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/411826
推荐阅读
相关标签
  

闽ICP备14008679号