排序方法总结

912. 排序数组
     给你一个整数数组 nums，请你将该数组升序排列。
     示例 1：
     输入：nums = [5,2,3,1]
     输出：[1,2,3,5]

「冒泡排序 bubble sort」

通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。
内外循环的条件非常重要，一定要写对。数组的尾部是最先有序的，要特别注意。设数组的长度为 n

1. 首先，对 n 个元素执行“冒泡”，将数组的最大元素交换至正确位置。
2. 接下来，对剩余 n−1 个元素执行“冒泡”，将第二大元素交换至正确位置。
3. 以此类推，经过 n−1 轮“冒泡”后，前 n−1 大的元素都被交换至正确位置。
4. 仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成。

// 冒泡排序
class Solution {
    public int[] sortArray(int[] nums) {
        int size = nums.length;
        // 外循环：未排序区间为 [0, i]
        for(int i = size-1; i > 0 ; i--){
            int flag = 0;
            // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
            for(int j = 0; j < i; j++){
                if(nums[j] > nums[j+1]){
                    int tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                    // 如果顺序还是不对，就置标志位。
                    flag = 1;
                }
            }
            if(flag == 0)  break;
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

「选择排序 selection sort」

工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。
设数组的长度为 n ，初始状态下，所有元素未排序，即未排序（索引）区间为 [0,n−1] 。

1. 选取区间 [0,n−1] 中的最小元素，将其与索引 0 处的元素交换。完成后，数组前 1 个元素已排序。
2. 选取区间 [1,n−1] 中的最小元素，将其与索引 1 处的元素交换。完成后，数组前 2 个元素已排序。
3. 以此类推。经过 n−1 轮选择与交换后，数组前 n−1 个元素已排序。
4. 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

// 选择排序
class Solution {
    public int getMinIndex(int[] nums, int start, int end){
        int res = nums[start];
        int index = start;
        for(int i = start; i < end; i++){
            if(res > nums[i]){
                res = nums[i];
                index = i;
            }
        }
        return index;
    }

    private void swap(int[] nums, int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    public int[] sortArray(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            // 查找[i,nums.length]之间的最小的数，并放到i的位置。
            int minIn = getMinIndex(nums, i, nums.length);
            swap(nums, i, minIn);
        }
        return 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

「插入排序 insertion sort」

一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。
具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。
设基准元素为 base ，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后将 base 赋值给目标索引。

1. 初始状态下，数组的第 1 个元素已完成排序。
2. 选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。
3. 选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。
4. 以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。

虽然冒泡排序、选择排序和插入排序的时间复杂度都为 n^2 ，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因。

• 冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。
• 选择排序在任何情况下的时间复杂度都为 n^2 。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。
• 选择排序不稳定，无法应用于多级排序。

// 插入排序
class Solution {
    public int[] sortArray(int[] nums) {
        // 外循环：前i个已经排序。
        for(int i = 1; i < nums.length; i++){
            // 寄存nums[i]值
            int tmp = nums[i];
            int j = i - 1;
            // 将位置i的元素插入已排好队的数组中，涉及到字移动，倒序遍历
            while(j >= 0 && nums[j] > tmp){
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j+1] = tmp;
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

「快速排序 quick sort」

一种基于分治策略（log（n））的排序算法，运行高效，应用广泛。
快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

1. 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
2. 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
3. 循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。

具体的排序过程：

• 首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
• 然后，对左子数组和右子数组分别递归执行“哨兵划分”。
• 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

class Solution {
    private void swap(int[] nums, int start, int end){
        int tmp = nums[start];
        nums[start] = nums[end];
        nums[end] = tmp;
    }

    // 左闭右闭的原则
    private int partition(int[] nums, int start, int end){
        // 以nums[start]为基准数。这个基准数可以随便选
        // 尽量要使这个基准数是一个中位数。
        int base = nums[start];
        int i = start;
        int j = end;
        while(i < j){
            while(i < j && nums[j] >= base)
                j--;
            while(i < j && nums[i] <= base)
                i++;
            swap(nums, i, j);
        }
        swap(nums, start, i);  // 将基准数交换至两子数组的分界线
        return i;
    }

    private void quickSort(int[] nums, int start, int end){
        if(start >= end)    return;
        // base值划分
        int prvot = partition(nums, start, end);
        // 分别递归
        quickSort(nums, start, prvot-1);
        quickSort(nums, prvot+1, end);
    }

    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return 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
37
38
39

「归并排序 merge sort」

一种基于分治策略的排序算法，包含“划分”和“合并”阶段。

1. 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
2. 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

归并排序与二叉树后序遍历的递归顺序是一致的。

• 后序遍历：先递归左子树，再递归右子树，最后处理根节点。
• 归并排序：先递归左子数组，再递归右子数组，最后处理合并。

class Solution {
    // 关键的排序逻辑实现
    private void merge(int[] nums, int start, int mid, int end){
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        int[]  tmp = new int[end - start + 1];

        int i = start;
        int j = mid + 1;
        int k = 0;
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中（排序的过程）
        while(i <= mid && j <= end){
            if(nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组
        while(i <= mid)
            tmp[k++] = nums[i++];
        while(j <= end)
            tmp[k++] = nums[j++];

        // 将临时数组tmp中的元素复制回nums的对应区间
        for(k = 0; k < tmp.length; k++){
            nums[start + k] = tmp[k];
        }
    }

    // 左闭右开
    private void mergeSort(int[] nums, int start, int end){
        // 终止条件
        if(start >= end)  return;
        int mid = (end - start) / 2 + start;
        // 左
        mergeSort(nums, start, mid);
        // 右
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, end);
    }

    // 左闭右闭
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length-1);
        return 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
37
38
39
40
41
42
43
44
45
46
47

「堆排序 heap sort」

一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。
（使用数组实现大/小顶堆）l = 2 * i + 1; r = 2 * i + 2;

1. 输入数组并建立小顶堆，此时最小元素位于堆顶。
2. 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

Queue minHeap = new PriorityQueue<>(); 堆=优先队列

设数组的长度为 n

1. 输入数组并建立大顶堆。完成后，最大元素位于堆顶。
2. 将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减 1 ，已排序元素数量加 1 。
3. 从堆顶元素开始，从顶到底执行堆化操作（sift down）。完成堆化后，堆的性质得到修复。
4. 循环执行第 2 步和第 3 步。循环 n−1 轮后，即可完成数组排序。

「堆 heap」是一种满足特定条件的完全二叉树，主要可分为两种类型

• 「小顶堆 min heap」：任意节点的值 ≤ 其子节点的值。
• 「大顶堆 max heap」：任意节点的值 ≥ 其子节点的值。

// 堆排序
class Solution {
    // 堆化操作
    /* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
    private void siftDown(int[] nums, int n, int i){
        while(true){
            // 获取当前节点的左右子节点
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            int my = i;
            // 大顶堆，下列的两种情况不符合条件
            if(l < n && nums[l] > nums[my])
                my = l;
            if(r < n && nums[r] > nums[my])
                my = r;
            // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出    
            if(my == i)
                break;
            int tmp = nums[i];
            nums[i] = nums[my];
            nums[my] = tmp;
            // 循环向下堆化
            i = my;
        }
    }

    private void heapSort(int[] nums){
        // 保证sift内的值不越界。
        for(int i = nums.length/2-1; i >= 0; i--){
            siftDown(nums, nums.length, i);
        }
        for(int i = nums.length-1; i > 0; i--){
            // 交换根节点和最右叶子节点（即交换首位元素）
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            // 堆的长度为 i ，从节点 0 开始，从顶至底堆化
            siftDown(nums, i, 0);
        }
    }

    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return 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
37
38
39
40
41
42
43
44
45
46