排序算法总结

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 8.2k 阅读时长 ≈ 7 分钟
排序算法 冒泡 选择 插入 希尔 快速 归并 堆 基数
平均时间复杂度 O(n2) O(n2) O(n2) O(n1.5) O(N*logN) O(N*logN) O(N*logN) O(d(n+r))

冒泡排序(BubbleSort)

基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
过程：

  • 比较相邻的两个数据，如果第二个数小，就交换位置。
  • 从后向前两两比较，一直到比较最前两个数据，最终最小数被交换到起始位置，这样第一个最小数的位置就排好了。
  • 继续重复上述过程，依次将2、3、…n-1个最小数排好位置。

java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
public class SortClass {

    public static void main(String[] args){
        // 测试数据
        int[] arr = {3,10,5,7,3,14,0,2};
        descendingOrder(arr);
        ascendingOrder(arr);
        optimizeOrder(arr);
        
        // 运行结果：
        // [14, 10, 7, 5, 3, 3, 2, 0]
        // [0, 2, 3, 3, 5, 7, 10, 14]
        // [0, 2, 3, 3, 5, 7, 10, 14]
    }

    /**
     * 降序
     */
    private static void descendingOrder (int[] arr){
        // 临时变量
        int temp;
        // 表示趟数，一共length此。
        int length=arr.length-1;
        for (int i = 0;i<length;i++){
            for (int j = length;j>i;j--){
                if (arr[j]>arr[j-1]){
                    temp = arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 升序
     */
    private static void ascendingOrder (int[] arr){
        // 临时变量
        int temp;
        // 表示趟数，一共length此。
        int length=arr.length-1;
        for (int i = 0;i<length;i++){
            for (int j = length;j>i;j--){
                if (arr[j]<arr[j-1]){
                    temp = arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 优化
     * 当数据顺序排好之后，算法仍然会继续下一轮比较。
     * 设置标志位 flag，如发生交换设置为 true，否则为 false，
     * 这样当一轮比较结束后 flag 仍为 false 时，
     * 即这一轮没有发生变化，说明顺序已排好，没必要继续下去了。
     */
    private static void optimizeOrder (int[] arr){
        // 临时变量
        int temp;
        // 表示趟数，一共length此。
        int length=arr.length-1;
        // 是否交换的标志
        boolean flag;
        for (int i = 0;i<length;i++){
            flag = false;
            for (int j = length;j>i;j--){
                if (arr[j]<arr[j-1]){
                    temp = arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                    flag = true;
                }
            }
            if (!flag){
                break;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

选择排序(SelectionSort)

基本思想：

  • 在长度为 N 的数组中，第一次遍历 n-1 个数，找到最小的数值与第一个元素交换，
  • 第二次遍历 n-2 个数，找到最小的数值与第二个元素交换，
  • 依次类推，
  • 第 n-1 次遍历，找到最小的数值与第 n-1 个元素交换，排序完成。

java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class SortClass {

    public static void main(String[] args){
        // 测试数据
        int[] arr = {3,10,5,7,3,14,0,2};
        int length = arr.length;
        selectSort(arr,length);

        // 运行结果：
        // [0, 2, 3, 3, 5, 7, 10, 14]
    }

    private static void selectSort(int[] arr,int length){
        for (int i = 0; i < length-1; i++) {
            int minIndex = i;
            for(int j = i+1;j<length;j++){
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if (minIndex != i){
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

插入排序(InsertionSort)

基本思想：

  • 在要排序的一组数中，假设前 n-1 个数已经排好序，
  • 现将第 n 个数插到前面的有序数列中，使得这 n 个数也是排好顺序的，
  • 如此反复循环，直到排好顺序。

java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class SortClass {

    public static void main(String[] args){
        // 测试数据
        int[] arr = {3,10,5,7,3,14,0,2};
        int length = arr.length;
        insertSort(arr,length);

        // 运行结果：
        // [0, 2, 3, 3, 5, 7, 10, 14]
    }

    private static void insertSort(int[] arr,int length){
        int temp;
        for (int i = 0; i < length - 1; i++) {
            for (int j = i+1;j>0;j--){
                if (arr[j]<arr[j-1]){
                    temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }else {
                    // 不需要交换
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

快速排序(QuickSort)

基本思想：（分治）

  • 先从数列中取出一个数作为 key 值，
  • 将比这个数小的全部放在它的左边，大于或等于它的数全部放在右边，
  • 对左右两个小数列重复第二步，直至各区间只有一个数。

辅助理解：挖坑填数

  • 初始时：i=0，j=9，key=72，arr={72 , 6 , 57 , 88 , 60 , 42 , 83 , 73 , 48 , 85}
    由于已将 arr[0] 的值保存到 key 中，可以理解成在数组 arr[0] 上挖了个坑，可以将其它数据填充进来，
    （– , 6 , 57 , 88 , 60 , 42 , 83 , 73 , 48 , 85）
    从 j 开始向前找一个比 key 小的数，如当 j=8 时符合条件，则 arr[0] =arr[8] 并 i++，
    （48 , 6 , 57 , 88 , 60 , 42 , 83 , 73 , 48 , 85）
    这样坑 arr[0] 解决了，但又多出了一个新坑 arr[8]，
    （48 , 6 , 57 , 88 , 60 , 42 , 83 , 73 , – , 85）
    这次从 i 开始向后找一个大于 key 的数，如当 i=3 时符合条件，则 arr[8] = arr[3] 并 j- -，
    （48 , 6 , 57 , 88 , 60 , 42 , 83 , 73 , 88 , 85）
  • 此时，i=3，j=7，key=72，arr={48 , 6 , 57 , 88 , 60 , 42 , 83 , 73 , 88 , 85}
    再重复上述步骤，先从后面找，再从前面找，
    从 j 开始向前找，当 j=5 时符合条件，则 arr[3] = arr[5] 并 i++，
    （48 , 6 , 57 , 42 , 60 , 42 , 83 , 73 , 88 , 85）
    从 i 开始向后找，当 i=5 时，由于 i==j 退出，
    此时，i=j=5，而 arr[5] 刚好又是上次挖的坑，因此将 key 填入 arr[5]，
    （48 , 6 , 57 , 42 , 60 , 72 , 83 , 73 , 88 , 85）
  • 此时，i=3，j=5，key=72，arr={48 , 6 , 57 , 42 , 60 , 72 , 83 , 73 , 88 , 85}
    可以看出 arr[5] 前面的数字都小于它，而后面的数字都大于它，
    因此再对 arr[0…4] 和 arr[6…9] 这两个子区间重复上述步骤即可。

java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class SortClass {

    public static void main(String[] args){
        // 测试数据
        int[] arr = {32,10,5,7,3,14,0,2,3,66,7,66,3,0,99,88,33,36};
        // int[] arr = {1,2,3,4,5,6};
        int length = arr.length;
        quickSort(arr,0,length-1);

        // 运行结果：
        // [0, 10, 5, 7, 3, 14, 0, 2, 3, 3, 7, 32, 66, 66, 99, 88, 33, 36]
        // [0, 10, 5, 7, 3, 14, 0, 2, 3, 3, 7, 32, 66, 66, 99, 88, 33, 36]
        // [0, 7, 5, 7, 3, 3, 0, 2, 3, 10, 14, 32, 66, 66, 99, 88, 33, 36]
        // [0, 3, 5, 7, 3, 3, 0, 2, 7, 10, 14, 32, 66, 66, 99, 88, 33, 36]
        // [0, 2, 0, 3, 3, 3, 7, 5, 7, 10, 14, 32, 66, 66, 99, 88, 33, 36]
        // [0, 0, 2, 3, 3, 3, 7, 5, 7, 10, 14, 32, 66, 66, 99, 88, 33, 36]
        // [0, 0, 2, 3, 3, 3, 7, 5, 7, 10, 14, 32, 66, 66, 99, 88, 33, 36]
        // [0, 0, 2, 3, 3, 3, 7, 5, 7, 10, 14, 32, 66, 66, 99, 88, 33, 36]
        // [0, 0, 2, 3, 3, 3, 5, 7, 7, 10, 14, 32, 66, 66, 99, 88, 33, 36]
        // [0, 0, 2, 3, 3, 3, 5, 7, 7, 10, 14, 32, 36, 66, 33, 66, 88, 99]
        // [0, 0, 2, 3, 3, 3, 5, 7, 7, 10, 14, 32, 33, 36, 66, 66, 88, 99]
        // [0, 0, 2, 3, 3, 3, 5, 7, 7, 10, 14, 32, 33, 36, 66, 66, 88, 99]
    }

    /**
     * 挖坑填数 + 分治
     */
    private static void quickSort(int[] arr,int left,int right){
        if (arr == null||left>=right){
            return;
        }
        int i=left;
        int j=right;
        // 选择第一个数为key
        // key 值得选取可以有多种形式，
        // 例如中间数或者随机数，
        // 分别会对算法得复杂度产生不同影响。
        int key=arr[left];

        while (i<j){
            // 从右向左，找第一个小于 key 的值。
            while (i<j && arr[j]>=key){
                j--;
            }
            if (i<j){
                arr[i++]=arr[j];
            }

            // 从左向右，找第一个大于 key 的值。
            while (i<j && arr[i]<=key){
                i++;
            }
            if (i<j){
                arr[j--] = arr[i];
            }
        }
        // i == j;
        arr[i]=key;
        System.out.println(Arrays.toString(arr));
        // 递归调用左半数组
        quickSort(arr,left,i-1);
        // 递归调用右半数组
        quickSort(arr,i+1,right);
    }

}

归并排序(MergeSort)

基本思想：

  • 建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。
  • 如何将两个有序数列合并，可以比较两个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数，然后再比较，如有数列为空，则直接将另一个数列的数据依次取出即可。

java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class SortClass {

    public static void main(String[] args){
        // 测试数据
        int[] a = {1,2,31,41,51,61,62,63};
        int[] b = {11,13,15,32,33,50,62};
        int aLength = a.length;
        int bLength = b.length;
        int cLength = aLength+bLength;
        int[] c = new int[cLength];
        mergeSort(a,aLength,b,bLength,c);

        // 运行结果：
        // [1, 2, 11, 13, 15, 31, 32, 33, 41, 50, 51, 61, 62, 62, 63]
    }

    /**
     * 合并有序数列
     */
    private static void mergeSort(int[] a,int n,int[] b,int m,int[] c){
        int i,j,k;
        i=j=k=0;
        while (i<n && j<m){
            if (a[i]<b[j]){
                c[k++]=a[i++];
            }else {
                c[k++]=b[j++];
            }
            System.out.println(k+"----"+i+"----"+j);
        }
        while (i<n){
            c[k++]=a[i++];
        }
        while (j<m){
            c[k++]=b[j++];
        }
        System.out.println(Arrays.toString(c));
    }

}

解决了上述的合并有序数列问题，再看归并排序，其基本思路就是将数组分成2组，各自再分成2组，依此类推，当分出的小组只有一个数据时，可认为这个小组组内已经达到了有序，然后再合并相邻的2个小组就可以了，这样通过先递归的分解数列，再合并数列就完成了归并排序。

平均时间复杂度：O(N*logN)）
归并排序的效率是比较高的，设数列长为 N，将数列分开成小数列一共要 logN 步，每步都是一个合并有序数列的过程，时间复杂度可以记为 O(N),故一共为 O(N*logN)。

java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class SortClass {

    public static void main(String[] args){
        // 测试数据
        int[] a = {11,2,20,0,33,13,11,66,88,66};
        int aLength = a.length;
        int[] c = new int[aLength];
        mergeSort(a,0,aLength-1,c);

        // 运行结果：
        // [2, 11, 20, 0, 33, 13, 11, 66, 88, 66]
        // [2, 11, 20, 0, 33, 13, 11, 66, 88, 66]
        // [2, 11, 20, 0, 33, 13, 11, 66, 88, 66]
        // [0, 2, 11, 20, 33, 13, 11, 66, 88, 66]
        // [0, 2, 11, 20, 33, 11, 13, 66, 88, 66]
        // [0, 2, 11, 20, 33, 11, 13, 66, 88, 66]
        // [0, 2, 11, 20, 33, 11, 13, 66, 66, 88]
        // [0, 2, 11, 20, 33, 11, 13, 66, 66, 88]
        // [0, 2, 11, 11, 13, 20, 33, 66, 66, 88]
    }

    private static void mergeSort(int[] arr,int first,int last,int temp[]){
        if (first<last){
            int middle=(first+last)/2;
            // 左半部分排好序
            mergeSort(arr,first,middle,temp);
            // 右半部分排好序
            mergeSort(arr,middle+1,last,temp);
            // 合并左右部分
            mergeArray(arr,first,middle,last,temp);
        }
    }

    /**
     * 合并，将两个序列 arr[first...middle], arr[middle+1...end] 合并
     */
    private static void mergeArray(int[] arr,int first,int middle,int end,int[] temp){
        int i=first;
        int m=middle;
        int j=middle+1;
        int n=end;
        int k=0;
        while (i<=m && j<=n){
            if (arr[i] <= arr[j]){
                temp[k]=arr[i];
                k++;
                i++;
            }else {
                temp[k]=arr[j];
                k++;
                j++;
            }
        }
        while (i<=m){
            temp[k]=arr[i];
            k++;
            i++;
        }
        while (j<=n){
            temp[k]=arr[j];
            k++;
            j++;
        }
        for (int z=0;z<k;z++){
            arr[first+z]=temp[z];
        }
        System.out.println(Arrays.toString(arr));
    }

}