八大排序（时间复杂度、稳定性、基本思想、代码实现）_八种基本排序及其时间复杂度

好久没看八大算法了，把八大算法重新回忆一下，这里写的都是升序。

1. 冒泡排序

时间复杂度：O(n²)

稳定排序：相等元素的相对顺序保证不变

基本思想：每趟排序过程中通过两两比较相邻元素，将小的数字放到前面，大的数字放在后面。

public static void sort(int[] arr) {
    boolean flag;   // flag用来判断是否交换，若一轮里没有交换说明已经有序
    // 每for一遍都找到了最大的放最右边，所以二层for循环里要-j
    for (int j = 0; j < arr.length; j++) {
        flag = false;
        for (int i = 0; i < arr.length - 1 - j; i++) {
            if (arr[i] > arr[i+1]) {
                swap(arr, i, i+1);
                flag = true;
            }
        }
        if (!flag) {
            return;
        }

    }
}
// 交换数组里的两项
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2. 快速排序

时间复杂度：O(nlogn)

不稳定排序：相等元素可能会因为分区而交换顺序

基本思想：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。

public static void main(String[] args) {

    int[] arr = {5, 10, 7, 9, 8, 9, 10, 7, 5, 4};
    change(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}
// 递归函数
private static void change(int[] arr, int left, int right) {
    if (left >= right) return;	//递归出口
    int pos = sort(arr, left, right);
    change(arr, left, pos - 1);
    change(arr, pos + 1, right);
}

public static int sort(int[] arr, int left, int right) {
    int base = arr[left];
    while (left < right) {
        while (arr[right] >= base && left < right) right--;
        arr[left] = arr[right];
        while (arr[left] <= base && left < right) left++;
        arr[right] = arr[left];
    }
    arr[left] = base;	//left=right
    return left;
}
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

3. 插入排序

时间复杂度：O(n²)

稳定排序：相等元素的相对顺序保证不变

基本思想：从最左边第1个数字开始，默认前面数组有序，往后遍历，若后面元素小则往前逐个交换直到到合适位置。

public static void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {	// 第一个默认有序，i从1开始就行
        for (int j = i - 1; j >= 0; j--) {	// j最开始指向i-1，j+1指向i，若顺序不对，则j和j+1往前移(j--)
            if (arr[j] > arr[j+1]) {
                冒泡.swap(arr, j, j+1);
            } else {
                break;	// 没交换就不用再往前比了，前面是默认有序的
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

4. 希尔排序

时间复杂度：O(nlogn)

不稳定排序：分组比较交换导致不稳定

希尔排序就是从插入排序演变来的

插入排序中如果很多小的数字在数组靠后的位置会非常影响性能，所以希尔排序根据分组把相对大的数字放后面去了

基本思想：把数组划分为步长长度的子数组，然后让所有子数组的相同位置比较，然后再减少步长同操作直到步长为1

public static void sort(int[] arr) {
    // 步长可以自己设置，这里步长设置为长度一半arr.length/2
    for (int grp = arr.length/2; grp > 0 ; grp/=2) {  // grp是步长，从length/2  ~  1
        for (int i = 0; i < arr.length; i++) {
            for (int j = i - grp; j >= 0; j-=grp) { // 让j+grp从i开始往后，j要>=0
                if (arr[j] > arr[j+grp]) {
                    冒泡.swap(arr, j, j+grp);
                } else {
                    break;  // 因为是默认前面有序往后排的，当最右边的不用交换的时候前面也是有序的
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5. 选择排序

时间复杂度：O(n²)

不稳定排序：再选出最小的交换到最左边时，可能会导致原位置上相等元素放到后面

比如 5,3,5,2，2 是最小值，会和第 1 个 5 进行交换，那第 1 个 5 就去了第 2 个 5 的后面，两个 5 的相对位置发生改变。

基本思想：每趟从待排序的记录中选择出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

public static void sort(int[] arr) {
    for (int j = 0; j < arr.length; j++) {
        int min = arr[j];
        int minIndex = j;
        for (int i = j + 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min=arr[i];
                minIndex=i;
            }
        }
        arr[minIndex] = arr[j];
        arr[j]=min;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6. 堆排序

记住：堆排序是利用了堆的思想，并没有用堆这个数据结构，只用了数组实现，根据数组角标能找父节点，左右孩子节点

时间复杂度：O(nlogn)

不稳定排序：构建大顶堆可能会打乱

基本思想： 利用完全二叉树构建大顶堆，堆顶堆底交换，剩余元素继续构建大顶堆，堆底元素不再参与构建

怎么构建大顶堆代码能看懂最好，看不懂搜一下。

public static void sort(int[] arr) {
        for (int i = arr.length; i >=0; i--) {
            adjust(arr, i, arr.length);
        }
        // 堆顶堆底进行交换
        for (int j = arr.length - 1; j >= 0; j--) {
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjust(arr, 0, j);
        }
    }

    /**
     * 堆的维护
     * @param arr
     * @param parent
     * @param length
     */
    public static void adjust(int[] arr, int parent, int length) {
        int child = 2*parent+1;

        while (child < length) {    // 有右孩子
            int rchild = child + 1;
            // 定义右孩子，找到左右孩子的最大值
            if (rchild < length && arr[child] < arr[rchild]) {
                child++;    // child指向左右孩子当中的最大值
            }
            // 父子节点进行对比
            if (arr[parent] < arr[child]) {
                // 父子节点进行交换
                冒泡.swap(arr, parent, child);

                parent = child;
                child = 2 * child + 1;
            } else {
                break;
            }
        }

    }
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

7. 归并排序

时间复杂度：O(nlogn)

稳定排序：相等元素的相对顺序保证不变

基本思想： 合并有序序列。 先拆分后合并，在合并的过程中借助临时空间进行排序。拆分：从中间位置拆开，数据分成左右两部分，继续拆分直到拆分成一个一个的时候，拆分停止。

public static void main(String[] args) {
    int[] arr = {5,7,4,2,0,3,1,6};
    split(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}

// 拆分
public static void split(int[] arr, int left, int right) {
    // 判断left和right是否指向同一块区域
    if (left == right) {
        return;
    }
    int i = (left + right) / 2;

    split(arr, left, i);
    split(arr, i+1, right);

    merge(arr, left, right, i);
}
public static void merge(int[] arr, int left, int right, int mid) {
    int s1 = left;      // 左游标
    int s2 = mid + 1;   // 右游标

    int[] temp = new int[right - left + 1]; //定义临时数组
    int index = 0;

    while(s1 <= mid && s2 <= right) {   // 左右两个数组挨个对比，小的进
        if (arr[s1] <= arr[s2]) {
            temp[index] = arr[s1];
            s1++;
        } else {
            temp[index] = arr[s2];
            s2++;
        }
        index++;
    }
    while (s1 <= mid) {
        temp[index] = arr[s1];
        s1++;index++;
    }
    while (s2 <=right) {
        temp[index] = arr[s2];
        s2++;index++;
    }

    for (int i = 0; i < temp.length; i++) {
        arr[i+left] = temp[i];
    }
}
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

8. 基数排序

时间复杂度：O(d*(n+k))

其中d是数字的最大位数，k是每个位上可能出现的取值范围

稳定排序：相等元素的相对顺序保证不变

基本思想： 将整数按位数切割成不同的数字，然后按每个位数分别比较。利用10个桶辅助排序。

public static void sort(int[] arr) {

    // 定义桶
    int[][] bucket = new int[10][arr.length];
    // 定义桶记录
    int[] elementCounts = new int[10];//每个桶里的顶
    // 获取最大值的位数,知道遍历几次
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int maxLength = (max + "").length();    // 知道遍历几遍
    int n = 1;  // n是1、10、100.。根据n来取第几位数来排序
    for (int k = 0; k < maxLength; k++) {
        // 数据放入桶
        for (int i = 0; i < arr.length; i++) {
            int element = arr[i]/n%10;    // element代表各位数值，也代表要放入哪号桶
            int count = elementCounts[element];    // 读取桶记录中的数据
            bucket[element][count] = arr[i];   // 数据存入
            elementCounts[element]++;   // 桶记录+1
        }
        // 数据取出
        int index = 0;  // 定义游标遍历数组，去出的数据要放入的下标
        // 遍历桶记录
        for (int i = 0; i < elementCounts.length; i++) {
            if (elementCounts[i] != 0) {
                // 定义游标遍历对应的桶里边的数据
                for (int j = 0; j < elementCounts[i]; j++) {
                    arr[index] = bucket[i][j];
                    index++;
                }
            }
            // 清楚桶记录,让桶索引都变为0
            elementCounts[i] = 0;
        }
        n = n * 10;
        System.out.println(Arrays.deepToString(bucket));    // 遍历二维数组的方法，学到了
    }
}
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