- 插入排序
- 希尔排序
- 冒泡排序
- 快速排序
- 选择排序
- 堆排序
- 归并排序
排序
1.排序数组
题目
给你一个整数数组
nums，请你将该数组升序排列。示例 1：
1
2输入：nums = [5,2,3,1]
输出：[1,2,3,5]示例 2：
1
2输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]提示：
1 <= nums.length <= 5 * 10^4-5 * 10^4 <= nums[i] <= 5 * 10^4
思路
排序方法有很多，接下来一一来实现：
插入排序（稳定）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// 直接插入排序
class Solution {
public int[] sortArray(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int temp = nums[i]; // 当前要排序的元素
int j = i;
while (j > 0 && nums[j - 1] > temp) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = temp;
}
return nums;
}
}希尔排序（不稳定）：
- 将原本有大量记录数的记录进行分组，分割成若干个子序列，然后在这些子序列内分别进行插入排序，当整个序列都基本有序时，再对全体记录进行一次插入排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// 希尔排序
class Solution {
public int[] sortArray(int[] nums) {
// incre是增量，递减到1
for (int incre = nums.length / 2; incre > 0; incre /= 2) {
for (int i = incre; i < nums.length; i++) {
int temp = nums[i];
int j = i;
while (j >= incre && nums[j - incre] > temp) {
nums[j] = nums[j - incre];
j -= incre;
}
nums[j] = temp;
}
}
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// 冒泡排序
class Solution {
public int[] sortArray(int[] nums) {
for (int i = nums.length - 1; i > 0; i--) {
boolean flag = true; // 用flag来标记是否发生了元素交换
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
flag = false;
}
}
if (flag) {
break; // 如果没有发生元素交换，说明已经有序，退出循环
}
}
return nums;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41// 快速排序
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int pivot = nums[right]; // 选择数组段中最后一个元素作为分区点
int fast, slow;
fast = slow = left;
while (fast < right) {
if (nums[fast] < pivot) {
// 如果快指针指向的元素小于pivot，则交换快慢指针的元素，
// 然后快慢指针都向后移动一位
swap(nums, fast, slow);
slow++;
}
// 如果快指针指向的元素大于等于pivot，则快指针直接向后移动一位
fast++;
}
// 当循环结束后：
// [left, slow - 1]的元素小于pivot
// [slow, right - 1]的元素大于等于pivot
swap(nums, slow, right);
// 交换元素后：
// [left, slow - 1]的元素小于pivot
// [slow + 1, right]的元素大于等于pivot
quickSort(nums, left, slow - 1);
quickSort(nums, slow + 1, right);
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}- 时间复杂度：最好、平均是 O(nlogn)，最坏是 O(n^2)
对快速排序算法的优化：
- 当数组长度小于某个阈值，比如说 10 的时候，转为使用插入排序。
- 选取 pivot 的时候，不要直接用数组段的最后一个元素作为分区点，而是可以进行采样，比如采样 3 个元素，排序后取中间值作为 pivot。
- 还可以判断采样的 3 个元素是否有序，如果有序，可以合理推测数组段大致有序，可以使用直接插入排序，因为直接插入排序在数组段大致有序的情况下时间复杂度可以达到 O(n)。
选择排序（不稳定）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// 选择排序
class Solution {
public int[] sortArray(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
swap(nums, i, minIndex);
}
return nums;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47// 堆排序
class Solution {
public int[] sortArray(int[] nums) {
heapSort(nums);
return nums;
}
public void heapSort(int[] nums) {
// 1.初始化堆
// 初始化堆是从最后一个非叶子结点开始，从右至左，从下至上调整
// 最后一个非叶子结点的下标：((nums.length - 1) - 1) / 2 = nums.length / 2 - 1
for (int i = nums.length / 2 - 1; i >= 0; i--) {
heapify(nums, i, nums.length - 1);
}
// 2.堆排序的过程
for (int i = nums.length - 1; i > 0; i--) {
swap(nums, 0, i); // 将大顶堆的根结点和剩余要排序的树的最后一个结点交换
heapify(nums, 0, i - 1); // 重新构造成大顶堆
}
}
// 将下标为i的结点作为根结点的子树调整为一个最大堆
// len是剩余要排序的树的最后一个结点下标
public void heapify(int[] nums, int i, int len) {
int temp = nums[i];
int parent, child;
for (parent = i; parent * 2 + 1 <= len; parent = child) {
child = parent * 2 + 1;
if (child + 1 <= len && nums[child + 1] > nums[child]) {
// 有右孩子结点并且右孩子结点的值更大
child++; // 让孩子结点指向右结点
}
if (nums[child] > temp) {
nums[parent] = nums[child];
} else {
break;
}
}
nums[parent] = temp;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}- 时间复杂度：最好、最坏、平均都是 O(nlogn)
★归并排序（稳定）：
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) {
mergeSort(nums, 0, nums.length - 1);
return nums;
}
public void mergeSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// left + (right - left) / 2 的写法要优于 (left + right) / 2，因为考虑到了溢出的情况
int center = left + (right - left) / 2;
// 对左半部分进行归并排序
mergeSort(nums, left, center);
// 对右半部分进行归并排序
mergeSort(nums, center + 1, right);
// 将左右两部分合并
merge(nums, left, center, right);
}
// left 是第一个子序列的开始位置
// center是第一个子序列的结束位置
// right 是第二个子序列的结束位置
public void merge(int[] nums, int left, int center, int right) {
int[] temp = new int[right - left + 1]; // 用多少，分配多少
int i, j, k;
i = left; // i指向第一个子序列的开始位置
j = center + 1; // j指向第二个子序列的开始位置
k = 0;
while (i <= center && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 第一个子序列还有剩余
while (i <= center) {
temp[k++] = nums[i++];
}
// 第二个子序列还有剩余
while (j <= right) {
temp[k++] = nums[j++];
}
// 将归并后的结果赋给原数组
k = 0;
for (i = left; i <= right; i++) {
nums[i] = temp[k++];
}
}
}- 时间复杂度：最好、最坏、平均都是 O(nlogn)
如果想要得到时间复杂度为 O(n) 的排序算法，那只能是基于非比较的排序算法，例如基数排序、计数排序、桶排序。
- 桶排序：将待排序的元素分配到有限数量的桶中，然后对每个桶中的元素进行排序，最后将所有桶中的元素合并起来得到有序序列。
- 桶排序的关键在于如何将元素分配到桶中以及如何对桶中的元素进行排序。
- 桶排序：将待排序的元素分配到有限数量的桶中，然后对每个桶中的元素进行排序，最后将所有桶中的元素合并起来得到有序序列。