常用的排序算法的时间复杂度以及稳定性

排序算法分为一般排序和高级排序，高级排序算法往往效率超高，除此之外，排序算法的稳定性也是可参考的一个指标之一。

一般排序算法

一、冒泡排序

• 算法代码实现

#include "stdio.h"

#define MAXSIZE 13

void change(int nums[], int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

int main() {
    int nums[] = {10, 31, 22, 7, 83, 69, 112, 12, 53, 29, 88, 200, 1};

    //冒泡排序,外层循环每次是数组的长度减1
    for (int i = MAXSIZE - 1; i > 0; i--) {
        //内层循环，每次是从0到i处的元素进行排序
        for (int j = 0; j < i; ++j) {
            int d1 = nums[j];
            int d2 = nums[j + 1];
            if (d1 > d2) {
                change(nums, j, j + 1);
            }
        }

    }

    for (int i = 0; i < MAXSIZE; ++i) {
        printf(" %d , ", nums[i]);
    }

    return 0;
}
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

冒泡排序每一轮都需要将当前元素与下一个元素相比较，如果大于，则交换位置，在一轮排序完成后，可以保证最大数已经排在最后面了，n个数，进行n-1轮排序即可把全部元素排序完成。

• 复杂度

冒泡排序的算法时间复杂度为 o(n²)

• 稳定性

冒泡排序是稳定的

二、插入排序

• 算法代码实现

public class InsertSort extends BaseSort{

    public static void main(String[] args) {
        int[] nums = InitData.getInitData();

        //外层循环依次递增，每进行一次外层循环，前i个数就是默认排好序的
        for (int i = 1; i < nums.length; i++) {
            //内层循环从i开始，依次与见面的数进行比较，一直比较到第一个大于当前元素为止
            for (int j = i; j > 0 ; j--) {
                int d1 = nums[j - 1];
                int d2 = nums[j];
                if (d2 < d1){
                    change(nums,j,j-1);
                }else break;
            }
        }

        System.out.println(Arrays.toString(nums));

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

插入排序默认待插入元素为止之前的元素是已经排好序的，所以只要遇到比待插入元素小的元素即可跳出循环。

• 复杂度

插入排序的算法最好时间复杂度是o(n),这种情况下是所有元素本来就是有序的，无需进行排序。

最坏时间复杂度为 o(n²)，所有元素是逆序时。

平均时间复杂度为 o(n²)。

• 稳定性

插入排序算法也是稳定的。

三、选择排序

• 选择排序的代码实现

/**
    选择排序：
        选择排序的时间复杂度是o(n2),且是一种不稳定的排序算法， 7 19 28 19 16 23
 */
public class SelectionSort extends BaseSort{

    public static void main(String[] args) {
        int[] initData = InitData.getInitData();
        //外层循环每一次遍历，都把当前下标处的元素当成是最小的，然后依次往后比较，查看是否还有比当前下标元素小的
        for (int i = 0; i < initData.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < initData.length; j++) {
                //比较j处是否大于minIndex处，如果小于则交换
                if (initData[j] < initData[minIndex]){
                    minIndex = j;
                }
            }
            if (minIndex != i){
                //交换位置
                change(initData,minIndex,i);
            }

        }

        System.out.println(Arrays.toString(initData));

    }

}
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

选择排序是每次把待排序的元素看作是最小元素，依次往后遍历，如果有小于当前元素的，则交换下标。

• 复杂度

选择排序的时间复杂度是o(n²)

• 稳定性

选择排序不是一种稳定排序算法。

高级排序

一、希尔排序

• 希尔排序算法代码实现

/**
    希尔排序：高级排序
        希尔排序是一种高级排序，也可以看作是插入排序的升级版
 */
public class ShellSort extends BaseSort{

    public static void main(String[] args) {
        int[] nums = InitData.getInitData();
        /*
            希尔排序先将待排序的数组通过增量使得变成一个比较优的插入排序，即大部分元素是有序的。
            希尔排序中提出了增量的概念，增量可以理解把待排序的数组分为增量个组，每组内的元素进行排序
            每一次增量变化，都会把所有元素排序一遍
        */
        //1.确定增量，默认是值是数组长度 / 2
        int step = nums.length / 2;
        //step为1时，所有元素都在一个组里了，无需再继续排序
        while (step > 0){
            for (int i = step; i < nums.length; i++) {
                //最多比较到当前组整数第1个元素即可
                for (int j = i ; j >= step ; j = j - step) {
                    //与该组内前一个元素比较
                    int d1 = nums[j - step];
                    int d2 = nums[j];
                    //如果待插入的元素比前一个元素大，则跳出循环，否则交换位置
                    if (d2 < d1){
                        change(nums,j,j - step);
                    }else break;
                }
            }
            step = step / 2;
        }
        System.out.println(Arrays.toString(nums));

    }

}
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

希尔排序的目的就是最终构建出一个比较优的插入排序，也就是说当数组中大部分元素都是有序的时候，此时只需要移动少量元素即可完成整个数组的排序。如何让一个数组变成比较优的待插入排序数组？希尔排序中引入了增量的概念，每次插入都需要根据当前增量来排序，增量把待排序的数据分为多少组，若增量为6，那么就分为了6个组，然后每个组内的元素进行排序，元素每次都是和 减增量个元素进行比较，当增量变为1时，其实就是一个纯粹的插入排序了，只不过由于前面的分组排序，此时已经被优化成一个比较优的插入排序数组了，希尔排序就是一个插入排序，只不过插入排序中，初始时从第1个开始比较，然后内存循环依次与前 1 个元素进行比较，比较后 减 1 ，我们把1的位置换成当前的增量，每做一个插入排序，增量就 / 2，一直到1。

• 复杂度

希尔排序的算法复杂度证明过程极为复杂，最好时的复杂度为 o(n)。

• 稳定性

希尔排序不是一种稳定排序算法。

二、归并排序

• 归并排序算法代码实现

/*
    归并排序：
        分治思想，将数组的每个元素依次拆分到只有一个时，再进行合并，合并时排序
*/
public class MergeSort extends BaseSort{

    //辅助数组
    private static int[] assists;

    public static void sort(int[] nums){
        assists = new int[nums.length];
        int lo = 0;
        int hi = nums.length - 1;
        sort(nums,lo,hi);
    }

    //对nums数组进行拆分，每次都拆分成一半，如果hi <= lo 了，则不进行拆分
    private static void sort(int[] nums, int lo, int hi) {
        if (hi <= lo){
            return;
        }
        int mid = (lo + hi) / 2;
        sort(nums,lo,mid);
        sort(nums,mid + 1,hi);
        //执行到这里开始合并
        merge(nums,lo,mid,hi);

    }

    //将数据分为两组 lo-mid为一组，mid+1-hi为一组，对两组数据进行合并，合并时排序
    private static void merge(int[] nums, int lo, int mid, int hi) {
        int i = lo;//辅助数组的起始指针
        int p1 = lo;//第一组的起始指针
        int p2 = mid + 1;//第二组的起始指针

        while (p1 <= mid && p2 <= hi){
            //分别对比p1与p2哪个大
            if (nums[p1] > nums[p2]){
                assists[i++] = nums[p2++];
            }else {
                assists[i++] = nums[p1++];
            }
        }

        //如果其中一个数组填充完成，则只需把另一个复制即可
        while (p1 <= mid){
            assists[i++] = nums[p1++];
        }

        while (p2 <= hi){
            assists[i++] = nums[p2++];
        }

        //拷贝到原数组
        for (int j = lo; j <= hi; j++) {
            nums[j] = assists[j];
        }
    }

    public static void main(String[] args) {
        int[] initData = InitData.getInitData();
        sort(initData);
        System.out.println(Arrays.toString(initData));

    }


}

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

归并排序是一种分治思想，将待排序的数组两两拆分，一直拆分到每组只剩一个元素后开始合并，在合并的时候排序，归并排序的实现需要用到一个辅助数组。

• 复杂度

归并排序的算法时间复杂度是o(nlog2n);

• 稳定性

归并排序是一种稳定排序算法。

三、快速排序

• 快速排序算法代码实现

/**
    快速排序：快速排序也是一种分治思想，每次都选定一个数，且把大于这个数的移动到右边，小于这个数的移动到左边
    直到每组剩余一个数
 */
public class QuickSort extends BaseSort{

    public static void sort(int [] nums){
        int lo = 0;
        int hi = nums.length - 1;
        //快速排序
        sort(nums,lo,hi);
    }

    private static void sort(int[] nums, int lo, int hi) {
        if (hi <= lo){
            return;
        }
        //计算分区
        int partition = partition(nums,lo,hi);
        //得到分区下标后，继续拆分
        sort(nums,lo,partition);
        sort(nums,partition+1,hi);
    }

    private static int partition(int[] nums, int lo, int hi) {
        //选取一个元素
        int element = nums[lo]; //比element大的往右排，比element小的往左排
        while (lo < hi){
            //移动右指针，直到遇到比element小的
            while (lo < hi && nums[hi] >= element){
                hi--;
            }
            //lo处的元素等于hi处的元素
            nums[lo] = nums[hi];

            //移动左指针,直到遇到比element大的
            while (lo < hi && nums[lo] <= element){
                lo++;
            }
            nums[hi] = nums[lo];
        }

        nums[lo] = element;
        return lo; //此时element的左侧是比自己小的，右侧是比自己大的

    }

    public static void main(String[] args) {
        int[] initData = InitData.getInitData();
        sort(initData);
        System.out.println(Arrays.toString(initData));
    }

}
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

快速排序也是一种分治思想，从待排序的数组中选出一个值，然后定义两个指针，依次从数组开始与末尾进行扫描，将比选出的值大的元素移动到右边，比选中的值小的移动到左边，依次递归，直到每组元素都剩余1个为止。

• 复杂度

快速排序的时间复杂度是 o(nlog2n)

• 稳定性

快速排序不是一种稳定的排序算法

四、堆排序

• 堆排序算法代码实现

/**
    堆排序：首先将一个数组构建成一个堆，然后依次将堆的第一个元素与最后一个元素交换位置，length--
    然后在将下标为1的元素下沉，此时继续执行以上操作，直到length为1
 */
public class HeapSort extends BaseSort {

    public static void sort(int[] nums){
        int[] data = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            data[i + 1] = nums[i];
        }
        int mid = nums.length / 2;
        int length = nums.length;
        for (int i = mid; i > 0 ; i--) {
            sinkElement(data,i,length);
        }

        for (int i = length; i > 0; i--) {
            change(data,1,length);
            length--;
            //将下标1处的元素下沉
            sinkElement(data,1,length);
        }
        //拷贝回原数组
        for (int i = 0; i < nums.length; i++) {
            nums[i] = data[i + 1];
        }

    }

    private static void sinkElement(int[] nums, int index, int length) {
        //判断index处是否有子节点
        while (index * 2 <= length){
            int maxIndex = index * 2;
            if (maxIndex + 1 <= length){
                //如果index * 2 + 1也小于等于length，说明还有右节点，此时需要比较左节点和右节点的大小
                if (nums[maxIndex + 1] > nums[maxIndex] ){
                    maxIndex = maxIndex + 1;
                }
            }
            //判断是否比最大的那个子节点大，如果小于则交换，如果大于，则不用交换
            if (nums[index] < nums[maxIndex]){
                change(nums,index,maxIndex);
            }else break;
            index = maxIndex;//index等于较大子节点那个位置，如果还有子节点，继续比较
        }
    }

    public static void main(String[] args) {
        int[] initData = InitData.getInitData();
        sort(initData);
        System.out.println(Arrays.toString(initData));

    }

}
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

使用堆排序要理解堆数据结构，和二叉树相似，只不过根节点是大于等于左右节点，或者是根节点小于等于左右节点，在排序时先将待排序数组转换为堆，再依次删除堆的第一个元素。

• 复杂度

堆排序的算法时间复杂度为o(nlog2n)

• 稳定性

堆排序不是一种稳定的排序算法 。

五、基数排序

上述排序算法主要是比较的关键字，而基数排序是将每个关键字分组，然后依次比较。例如有10000个学生，出生年月在1991-2005之前，按照出生年月排序。此时可以将关键字分组，分为3组（年，月，日） (d)，年的取值范围是1991-2005,月的取值范围是 01-12 ,而日的取值范围是 01-31,取最大的范围就是31,31就是r的取值范围。

• 复杂度

基数排序的算法时间复杂度是o(d(n+r)),以上述为例，n=10000，d是每个关键字的分组的个数，d = 3，r就是每个分组的取值范围
r = 31 ,o(d(n+r)) = 3(10000+31) 。

• 稳定性

基数排序是一种稳定的排序算法（基你太稳）。

稳定的排序算法

基数排序、归并排序、冒泡排序、插入排序

不稳定的排序算法

堆排序、快速排序、希尔排序、选择排序