数据结构之排序

---

1 排序概述

将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。
排序的分类：
（1）内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。
（2）外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。
常见的排序算法分类如下图所示，本文主要讨论内部排序。

2 插入排序

2.1 直接插入排序

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

	public static void directInsertSort(int[] arr){
	    for (int i = 1; i < arr.length; ++i){
	        for (int j = i; j > 0; --j){
	            if (arr[j] < arr[j - 1]){
	                swap(arr, j, j - 1);
	            } else {
	                break;
	            }
	        }
	    }
	}

	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

2.2 希尔排序

希尔排序法基本思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

	public static void shellSort(int[] arr){
        int gap = arr.length;
        while (true){
            gap /= 2;
            for (int i = 0; i < gap; ++i){
                for (int j = i + gap; j < arr.length; j += gap){    // 这个循环里其实就是一个插入排序
                    int k = j;
                    while (k >= gap && arr[k] < arr[k - gap]){
                        swap(arr, k, k - gap);
                        k -= gap;
                    }
                }
            }
            if (gap == 1){
                break;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3 选择排序

3.1 简单选择排序

简单选择排序思想：第1次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1] ~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2] ~arr[n-1]中选取最小值，与arr[2]交换，…，第n-1次从arr[n-2] ~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

	public static void simpleSelectSort(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[minIndex]){
                    minIndex = j;
                }
            }
            if (i != minIndex){
                swap(arr, i, minIndex);
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.2 堆排序

堆排序基本介绍
（1）堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。
（2）堆是具有以下性质的二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
（3）每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
（4）大顶堆如下图所示：

堆排序基本思想
（1）将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点；
（2）将其与末尾元素进行交换，此时末尾就为最大值；
（3）然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。

	public static void heapSort(int[] arr){
        // 将数组调整为大根堆
        for (int i = arr.length / 2 - 1; i >= 0; --i){   // 因为数组从0开始计数，所以要减1
            adjustHeap(arr, i, arr.length);
        }

        // 排序
        for (int i = arr.length - 1;  i > 0; --i){
            swap(arr, 0, i);
            adjustHeap(arr, 0, i);
        }
    }

    public static void adjustHeap(int[] arr, int i, int length){
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1){     // 因为数组从0开始计数，所以要加1
            if (k + 1 < length && arr[k] < arr[k + 1]){    // 选取左，右孩子当中较大的值与父节点交换
                ++k;
            }
            if (arr[i] < arr[k]){
                swap(arr, i, k);
                i = k;    // 继续调整子树当中的节点
            } 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

4 交换排序

4.1 冒泡排序

冒泡排序基本思想：通过对待排序序列从前向后(从下标较小的元素开始)，依次比较相邻元素的值，若发现逆序则交换,使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。
因为排序的过程中各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的比较。

   public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length - 1; ++i){
            boolean flag = true;     // 标识变量，表示是否进行过交换
            for (int j = 0; j < arr.length - i - 1; ++j){
                if (arr[j] > arr[j + 1]){
                    flag = false;
                    swap(arr, j, j + 1);
                }
            }
            if (flag){
                break;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.2 快速排序

快速排序法基本思想：快速排序是对冒泡排序的一种改进，基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

    public static void quickSort(int[] arr, int left, int right){
        if (left > right){
            return;
        }
        int i = left;
        int j = right;
        int temp = arr[left];

        while (i < j){
            while (arr[j] >= temp && i < j){    // 从右向左找到第一个比基准值小的元素
                --j;
            }
            while (arr[i] <= temp && i < j){    // 从左向右找到第一个比基准值大的元素
                ++i;
            }
            swap(arr, i, j);
        }
        // 交换基准值
        arr[left] = arr[j];
        arr[j] = temp;

        quickSort(arr, left, j - 1);
        quickSort(arr, j + 1, right);

    }
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

5 归并排序

归并排序基本思想：归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略(分治法将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

空间复杂度为O(n)，来自于辅助数组。

    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        if (left < right){
            int mid = left + (right - left) / 2;    // 中间索引
            mergeSort(arr, left, mid, temp);    // 向左递归进行分解
            mergeSort(arr, mid + 1, right, temp);    // 向右递归进行分解
            merge(arr, left, mid, right, temp);    // 合并
        }
    }

    public static void merge(int[] arr, int left, int mid, int right, int[] temp){
        int i = left;    // 左侧区间的第一个数
        int j = mid + 1;    // 右侧区间的第一个数
        int k = 0;

        // 把左右两边（有序）的数据按照规则填充到temp数组，直到左右两边的有序序列一边处理完为止
        while (i <= mid && j <= right){
            if (arr[i] < arr[j]){
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 把有剩余数据的一边的数据依次填充到temp
        while (i <= mid){
            temp[k++] = arr[i++];
        }
        while (j <= right){
            temp[k++] = arr[j++];
        }

        // 将temp数组的元素拷贝到arr
        k = 0;
        int t = left;
        while(t <= right){
            arr[t++] = temp[k++];
        }
    }
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

6 基数排序

基数排序基本思想：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。



一趟分配O(n)，一趟收集O( r)，总共d趟分配、收集，总的时间复杂度为O(d(n+r))；需要r个辅助队列，空间复杂度=O( r)。

    public static int number(int[] arr){
        int res = 0;
        for (int i = 0; i < arr.length; ++i){
            if (arr[i] > res){
                res = arr[i];
            }
        }
        return (res + "").length();
    }

    public static void radixSort(int[] arr){
        int num = number(arr);
        int[][] bucket = new int[10][arr.length];    // 一共建立10个桶
        int[] bucketElement = new int[10];    // 记录每个桶的数据量
        int index = 0;

        for (int i = 0; i < num; ++i){
            // 将数据放入桶中
            for (int j = 0; j < arr.length; ++j){
                int k = (int) (arr[j] / Math.pow(10, i) % 10);
                bucket[k][bucketElement[k]] = arr[j];
                ++bucketElement[k];
            }

            // 将数据写回arr数组
            for(int j = 0; j < 10; ++j){
                int k = 0;
                while (k < bucketElement[j]){
                    arr[index++] = bucket[j][k];
                    ++k;
                }
                bucketElement[j] = 0;
            }
            index = 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
33
34
35
36

7 各种排序算法的性质

算法的稳定性
若待排序表中有两个元素Ri和Rj，其对应的关键字相同即keyi=keyj，且在排序前Ri在Rj的前面，若使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称这个排序算法是不稳定的。

---

参考：
https://www.bilibili.com/video/BV1E4411H73v?p=1&vd_source=ff364c22743db2666f3a26c417a3f759
https://www.bilibili.com/video/BV1b7411N798?p=1&vd_source=ff364c22743db2666f3a26c417a3f759