1.选择排序

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
class Solution {
    public int[] sortArray(int[] nums) {
        /*
        选择排序:
        每一轮选取未排定的部分中最小的部分交换到未排定部分的最开头，经过若干个步骤，就能排定整个数组
        即：先选出最小的，再选出第 2 小的，以此类推
        时间复杂度:O(N^2) 空间复杂度:O(1) 不稳定
         */
        int n = nums.length;
        // 有序区间[0,i-1]，一开始全部都是无序的，因此i=0
        for (int i = 0; i < n; i++) {
            // 最小数字对应的索引，在[i,n-1]内查找
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIdx]) minIdx = j;
            }
            // 确定了区间[i,n-1]最小数字对应的索引minIdx，交换nums[i]与nums[minIdx]
            swap(nums, i, minIdx);
        }
        return nums;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

2.插入排序

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
class Solution {
    public int[] sortArray(int[] nums) {
        /*
        插入排序
        每次将一个数字插入一个有序的数组里，成为一个长度更长的有序数组，有限次操作以后，数组整体有序
        该算法在接近有序的情况下，表现优异
        时间复杂度:O(N^2) 空间复杂度:O(1) 稳定
         */
        int n = nums.length;
        // 有序区间[0,i-1]，枚举要插入的数字，由于0没办法往前插，因此i=1开始
        for (int i = 1; i < n; i++) {
            // 暂存nums[i]
            int t = nums[i];
            // j为要插入的位置
            int j = i;
            // 寻找首个能插入的坑位j，即nums[j-1] <= t
            while (j > 0 && nums[j - 1] > t) {
                nums[j] = nums[j - 1];
                j--;
            }
            // 将暂存的数字t插入到坑位j
            nums[j] = t;
        }
        return nums;
    }
}

3.冒泡排序

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
class Solution {
    public int[] sortArray(int[] nums) {
        /*
        冒泡排序
        外层循环每一次经过两两比较，把每一轮未排定部分最大的元素放到了数组的末尾
        时间复杂度:O(N^2) 空间复杂度:O(1) 稳定
         */
        int n = nums.length;
        // 枚举要冒泡的右边界i
        for (int i = n - 1; i >= 0; i--) {
            // 默认排序好
            boolean sorted = true;
            // 枚举j∈[0,i-1]，那么最右边j+1=i，正好使得i的元素位置正确
            for (int j = 0; j < i; j++) {
                // 若nums[j]>nums[j+1]，nums[j]要浮到右边去
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    // 说明没有排序好
                    sorted = false;
                }
            }
            // 一次也没交换说明前面有序了，退出
            if (sorted) break;
        }
        return nums;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

4.快速排序

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
class Solution {
    public int[] sortArray(int[] nums) {
        /*
        快速排序:
        1.每一轮选一个基准元素pivot
        2.利用两个指针分别将<=pivot和>pivot的元素分别放在pivot的左边与右边
        3.最后递归调用原函数直至区间长度缩小为1
        时间复杂度:O(NlogN) 空间复杂度:O(1) 不稳定
        虽然快排不稳定，但是很多不需要稳定情况下，快排非常快
         */
        int n = nums.length;
        quickSort(nums, 0, n - 1);
        return nums;
    }

    private void quickSort(int[] nums, int low, int high) {
        // 区间长度<=1 直接返回
        if (low >= high) return;
        // 左右指针
        int l = low, r = high;
        // 基准元素
        int pivot = nums[low];
        while (l < r) {
        	// r指针先行可以确保最后停留的位置必定是<=基准，再不济就移动到pivot位置上；而l指针先行会找到首个大于基准的位置
        	// 例如在[1,2,3,4,5]这种情况会停在2处，此时r指针想找小于等于基准的元素但是也只能移动到2处结束
        	// 循环退出->将1与2的位置交换，此时有[2,1,3,4,5] 违反了快排的宗旨了，再递归左右子区间就出错
            // 归根到底右指针先行，是为了避免左指针主动时导致停留在比基准大的地方，与基准交换后直接导致基准左边有元素大于基准
        	// 右指针先行会主动占据<=基准的元素，再不济就是移动到基准位置，这两种情况符合快排目的
            // 因此选了nums[low]作为基准因此要右指针先行
            // r停留在右边首个<=pivot的位置处
            while (l < r && nums[r] > pivot) r--;
            // l停留在左边首个>pivot的位置处
            while (l < r && nums[l] <= pivot) l++;
            // 交换nums[l]与nums[r]
            if (l < r) {
                // nums[l] ^= nums[r];
                // nums[r] ^= nums[l];
                // nums[l] ^= nums[r];
                int t = nums[l];
                nums[l] = nums[r];
                nums[r] = t;
            }
        }
        // l==r
        // 交换nums[l]与基准元素pivot
        nums[low] = nums[l];
        nums[l] = pivot;
        // 此时pivot左边均<=pivot，右边均>pivot，递归调用快排排序左右区间
        quickSort(nums, low, r - 1);
        quickSort(nums, r + 1, high);
    }
}

5.归并排序

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
class Solution {
    int[] t;    // 合并有序数组的中间容器

    public int[] sortArray(int[] nums) {
        /*
        归并排序:
        本质原理就是使得左右两边的数组有序，再合并这两个有序数组
        时间复杂度:O(NlogN) 空间复杂度:O(N) 稳定
         */
        int n = nums.length;
        t = new int[n];
        mergeSort(nums, 0, n - 1);
        return nums;
    }

    // 带区间边界的归并排序方法，该方法使得nums[l,r]有序
    private void mergeSort(int[] nums, int l, int r) {
        // 区间长度小于等于1直接返回
        if (l >= r) return;
        // 区间中点
        int mid = l + (r - l) / 2;
        // 递归排序[l,mid]和[mid+1,r]
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        // 合并两边的有序数组
        merge(nums, l, mid, r);
    }

    // 合并两个有序区间nums[l,mid]和nums[mid+1,r]
    private void merge(int[] nums, int l, int mid, int r) {
        // 合并后的指针
        int idx = l;
        // 左右区间指针
        int i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                t[idx++] = nums[i++];
            } else {
                t[idx++] = nums[j++];
            }
        }
        // 再排序没有走完的
        while (i <= mid) t[idx++] = nums[i++];
        while (j <= r) t[idx++] = nums[j++];
        // 再将t[l,r]位置拷贝至nums[l,r]位置
        System.arraycopy(t, l, nums, l, r - l + 1);
    }
}

6.堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

p19

参考资料：堆排序（超详细图解 java 版）

主要步骤：

1.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆（升序一般用大顶堆）

2.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端

3.重新调整结构,使其满足堆定义，然后继续交换堆顶元素与当前末尾元素

4.反复执行调整+交换步骤，直到整个序列有序

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
class Solution {
    public int[] sortArray(int[] nums) {
        /*
        堆排序:
        1.将无序序列构建成一个堆，根据需求选择大顶堆或小顶堆（升序一般用大顶堆）
        2.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
        3.重新调整结构,使其满足堆定义，然后继续交换堆顶元素与当前末尾元素
        4.反复执行调整+交换步骤，直到整个序列有序
        时间复杂度:O(NlogN) 空间复杂度:O(1) 不稳定
         */
        int n = nums.length;
        // 升序一般用大顶堆，即节点大于等于左右子节点
        // 初始调整堆，由已知结论知只调节一半即可使得整个堆有序
        for (int i = n / 2 - 1; i >= 0; i--) {
            sink(nums, i, n - 1);
        }
        // 交换排序数组:这里的end是堆末位的索引
        for (int end = n - 1; end > 0; end--) {
            // 交换nums[0]与nums[end]，此时nums[end]就是最大的元素，位置正确
            swap(nums, 0, end);
            // 调整堆，范围为[0,end-1]
            sink(nums, 0, end - 1);
        }
        return nums;
    }

    // 调整堆使其有序:target为节点索引，end为堆要调整的范围
    private void sink(int[] nums, int target, int end) {
        // 节点索引指针
        int idx = target;
        // 保存原来节点的值
        int t = nums[target];
        // 只要有左子节点就进行循环
        while (2 * idx + 1 <= end) {
            // 最大节点对应索引，初始化为左子节点索引
            int maxLR = 2 * idx + 1;
            // 比较得出左右子节点最大值
            if (maxLR + 1 <= end && nums[maxLR + 1] > nums[maxLR]) maxLR++;
            // 正确的堆结构:nums[idx]>=nums[maxLR]
            // 因此只要nums[idx]<nums[maxLR]就要进行下沉
            if (nums[idx] < nums[maxLR]) {
                // 将nums[idx]与nums[maxLR]交换就可以完成一次下沉
                swap(nums, idx, maxLR);
            } else {
                // 下沉至正确位置，整个堆只有一个数字无序，其他均有序
                break;
            }
            // idx指针向maxLR前进，即来到了原来的值位置
            idx = maxLR;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}