排序算法总结
0. 概述
排序算法作为最经典的算法知识，可以说是每个程序员都必须得掌握的了。文本主要对常见的几种排序算法进行介绍。
首先直接给出归纳图，包括时间复杂度、空间复杂度和稳定性，可以参考下图：
在介绍算法之前，先定义基本的交换数组元素的方法，节省后面的代码量
1
2
3
4
5
6
7
| class Algorithm_Sort{
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
|
1. 冒泡排序
冒泡排序的本质在于交换，即每次通过交换的方式把当前剩余元素的最大值移动到一端，而当剩余元素减少为 0 时，排序结束。
具体来说，从左到右依次比较相邻的两个元素，如果前一个元素比较大，就把前一个元素和后一个交换位置，遍历数组之后保证最后一个元素相对于前面的永远是最大的，重复地进行直到没有再需要交换。
这里我引入了 bool 型变量，当然不用也是可以的。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Algorithm_Sort{
public void BubbleSort(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
boolean flag = true;
for (int j = 0; j < n - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
flag = false;
}
}
if (flag)
break;
}
}
}
|
复杂度分析
2. 选择排序
选择排序的思想比较简单，每次从 n-i 个元素里选择最小（大）的元素，作为有序数组的第 i 个
具体来说，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Algorithm_Sort{
public void SelectSort(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (nums[min] > nums[j])
min = j;
}
swap(nums, min, i);
}
}
}
|
复杂度分析
3. 插入排序
插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
具体来说，从第二个元素开始枚举，在已经排序的元素序列中从后向前扫描，如果该元素大于待插入元素，将该元素移到下一位置，直到小于或者等于待插入元素，重复上述步骤，直到整个数组有序。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Algorithm_Sort{
public void InsertSort(int[] nums) {
int n = nums.length;
for (int i = 1; i < n; i++) {
int tmp = nums[i];
int j = i;
while (j > 0 && nums[j - 1] > tmp) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = tmp;
}
}
}
|
复杂度分析
4. 希尔排序
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
希尔排序将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时终止。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Algorithm_Sort{
public void ShellSort(int[] nums) {
int n = nums.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int tmp = nums[i];
int j = i;
while (j - gap >= 0 && nums[j - gap] > tmp) {
nums[j] = nums[j - gap];
j -= gap;
}
nums[j] = tmp;
}
}
}
}
|
复杂度分析
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
| class Algorithm_Sort{
public void MergeSort(int[] nums, int left, int right) {
if (left >= right)
return;
int mid = (left + right) / 2;
MergeSort(nums, left, mid);
MergeSort(nums, mid + 1, right);
int[] tmp = new int[right - left + 1];
int i = left, j = mid + 1;
int cnt = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j])
tmp[cnt++] = nums[i++];
else
tmp[cnt++] = nums[j++];
}
while (i <= mid)
tmp[cnt++] = nums[i++];
while (j <= right)
tmp[cnt++] = nums[j++];
for (int k = 0; k < tmp.length; k++)
nums[left + k] = tmp[k];
}
}
|
复杂度分析
- 时间复杂度：O(nlog2n)
- 空间复杂度：O(n)
6. 快速排序
快速排序的主要思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
代码实现
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
| class Algorithm_Sort{
public void QuickSort(int[] nums, int left, int right) {
if (left < right) {
int pos = partition_1(nums, left, right);
QuickSort(nums, left, pos - 1);
QuickSort(nums, pos + 1, right);
}
}
public int partition_1(int[] nums, int left, int right) {
int pivot = nums[left];
int pos = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] <= pivot) {
pos++;
swap(nums, i, pos);
}
}
swap(nums, left, pos);
return pos;
}
public int partition_2(int[] nums, int left, int right) {
int pivot = nums[left];
int low = left, high = right;
while (low < high) {
while (low < high && nums[high] >= pivot)
high--;
while (low < high && nums[low] <= pivot)
low++;
if (low < high)
swap(nums, low, high);
}
swap(nums, left, low);
return low;
}
}
|
复杂度分析
- 时间复杂度：O(nlog2n)
- 空间复杂度：O(nlog2n)
7. 堆排序
堆排序把整个数组变成一个最大堆，然后每次从堆顶取出最大的元素，这样依次取出的最大元素就形成了一个排序的数组
具体来说，将待排序序列构造成一个大根堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列。
代码实现
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
| class Algorithm_Sort{
public void HeapSort(int[] nums) {
int n = nums.length;
BuildMaxHeap(nums, n);
for (int i = n - 1; i > 0; i--) {
swap(nums, 0, i);
n--;
Heapify(nums, 0, n);
}
}
public void BuildMaxHeap(int[] nums, int n) {
for (int i = n / 2 - 1; i >= 0; i--)
Heapify(nums, i, n);
}
public void Heapify(int[] nums, int i, int n) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int max = i;
if (left < n && nums[left] > nums[max])
max = left;
if (right < n && nums[right] > nums[max])
max = right;
if (max != i) {
swap(nums, i, max);
Heapify(nums, max, n);
}
}
}
|
复杂度分析
- 时间复杂度：O(nlog2n)
- 空间复杂度：O(1)
