排序算法总结

本文最后更新于:5 个月前

排序算法总结

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 型变量,当然不用也是可以的。

BubbleSort

代码实现

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++) { // 冒泡得到n-1个最大值
// 设定一个标记,若为 true,则表示此次循环没有进行交换,排序已经完成。
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;
}
}
}

复杂度分析

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)

2. 选择排序

选择排序的思想比较简单,每次从 n-i 个元素里选择最小(大)的元素,作为有序数组的第 i

具体来说,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

SelectSort

代码实现

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++) { // 进行n-1趟即可,最后一个元素自动有序
int min = i; // 记录最小值所在位置
for (int j = i + 1; j < n; j++) {
if (nums[min] > nums[j])
min = j;
}
swap(nums, min, i); // 交换
}
}
}

复杂度分析

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)

3. 插入排序

插入排序通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

具体来说,从第二个元素开始枚举,在已经排序的元素序列中从后向前扫描,如果该元素大于待插入元素,将该元素移到下一位置,直到小于或者等于待插入元素,重复上述步骤,直到整个数组有序。

InsertSort

代码实现

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]; // tmp临时存放nums[i]
int j = i; // j从i开始往前枚举
while (j > 0 && nums[j - 1] > tmp) { // 只要tmp小于前一个元素nums[j-1]
nums[j] = nums[j - 1]; // 后移一位
j--;
}
nums[j] = tmp; // 插入位置为j
}
}
}

复杂度分析

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)

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) { // 增量gap,并逐步缩小增量
// 下面是插入排序的思想
for (int i = gap; i < n; i++) { // 从第gap个元素,逐个对其所在组进行直接插入排序
int tmp = nums[i]; // tmp临时存放nums[i]
int j = i;
while (j - gap >= 0 && nums[j - gap] > tmp) { // 只要tmp小于前gap个元素nums[j-gap]
nums[j] = nums[j - gap]; // 后移gap位
j -= gap;
}
nums[j] = tmp; // 插入位置为j
}
}
}
}

复杂度分析

  • 时间复杂度:O(n1.3)
  • 空间复杂度:O(1)

5. 归并排序

归并排序是利用归并的思想实现的排序方法,采用经典的分治策略。

具体来说,在排序的过程中,把原来的数组变成左右两个子数组,然后分别进行排序,当左右的子数组排序完毕之后,再合并这两个子数组形成一个新的排序数组,整个过程递归进行,当只剩下一个元素或者没有元素的时候就直接返回。

MergeSort

代码实现

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. 快速排序

快速排序的主要思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序

QuickSort

代码实现

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);
//int pos = partition_2(nums, left, right);
QuickSort(nums, left, pos - 1);
QuickSort(nums, pos + 1, right);
}
}
//方法一
public int partition_1(int[] nums, int left, int right) {
// 随机基准值
// int tmp = new Random().nextInt(right - left + 1) + left;
// swap(nums, tmp, left);
int pivot = nums[left]; // 第一个数作为基准值
int pos = left; // pos为分界点
for (int i = left + 1; i <= right; i++) { // 遍历除基准值外的元素
if (nums[i] <= pivot) { // 保证pos的左侧都小于等于pivot
pos++;
swap(nums, i, pos);
}
}
swap(nums, left, pos); // 把分界点元素移动到分界位置
return pos;
}
//方法二
public int partition_2(int[] nums, int left, int right) {
// 随机基准值
// int tmp = new Random().nextInt(right - left + 1) + left;
// swap(nums, tmp, left);
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 个元素的次小值。如此反复执行,便能得到一个有序序列。

HeapSort

代码实现

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--) // 第一个非叶子结点 n/2-1
// 从下至上,从右至左调整结构
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)

本文作者: EmoryHuang
本文链接: https://emoryhuang.cn/blog/3445979243.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明来自EmoryHuang