详解排序算法
文章目录
- 1. 排序算法分类
- 2. 比较排序算法介绍
- 2.1 插入排序
- 2.1.1 直接插入排序
- 2.1.2 希尔排序
- 2.2 选择排序
- 2.2.1 直接选择排序
- 2.2.2 堆排序
- 2.2.2.1 向下调整算法建堆
- 2.2.2.2 向上调整算法建堆
- 2.2.2.3 进行堆排序
- 2.2.2.4 堆排序时间、空间复杂度分析
- 2.2.2.5 利用堆排序解决TOP-K问题
- 2.3 比较排序
- 2.3.1 冒泡排序
- 2.3.2 快速排序
- 2.3.2.1 快速排序的递归实现
- 2.3.2.2 快速排序的非递归实现
- 2.4 归并排序
- 2.4.1 归并排序的递归版本
- 2.4.3 归并排序的非递归版本
- 3. 非比较排序
1. 排序算法分类
排序算法分为两大类：比较排序与非比较排序。
非比较排序，即计数排序。
比较排序又分为四类：
- 插入排序：直接插入排序和希尔排序
- 选择排序：直接选择排序和堆排序
- 交换排序：冒泡排序和快速排序
- 归并排序: 归并排序
2. 比较排序算法介绍
2.1 插入排序
2.1.1 直接插入排序
基本思想：直接插入排序是将一个待排序的数插入到一个已经有序的序列中，得到一个新的有序序列。平时玩扑克牌，整理手牌时，就使用了直接插入排序。
直接插入排序的代码实现：
void InsertSrot(int* arr, int size)
{
for (int i = 0; i < size - 1; i++)
{
int pos = i, tmp = arr[pos + 1];
while (pos >= 0)
{
if (arr[pos] > tmp)
{
arr[pos + 1] = arr[pos];
pos--;
}
else
break;
}
arr[pos + 1] = tmp;
}
}
直接插入排序时间与空间复杂度：
- 时间复杂度：时间复杂度为O(n ^ 2)，但排序数组越趋近于有序，时间复杂度会越低，趋近于O(n)
- 空间复杂度：只利用了常数个临时变量，空间复杂度为O(1)
2.1.2 希尔排序
希尔排序，又称为缩小增量法，其实质就是利用一个gap，进行分组的直接插入排序，然后gap不断缩小（即缩小增量），直至gap为1时，进行最后一次gap = 1的直接插入排序，即得有序序列。
讲得通俗些，希尔排序是直接插入排序改进而来的，gap不为1时，所作的排序可以视作预排序，这些预排序都是为了最后一次gap = 1的直接插入排序做准备——使得进行最后一次直接插入排序的序列趋近于有序，这样可以降低直接插入排序的时间复杂度。
希尔排序的代码实现：
void ShellSort(int* arr, int size)
{
int gap = size;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < size - gap; i++)
{
int pos = i;
int tmp = arr[pos + gap];
while (pos >= 0)
{
if (arr[pos] > tmp)
{
arr[pos + gap] = arr[pos];
pos -= gap;
}
else
break;
}
arr[pos + gap] = tmp;
}
}
}
希尔排序中gap如何缩小是有讲究的。我在上述代码中采用的缩小方式是除3加1（一定要加1，确保进行的最后一次希尔排序为gap=1的直接插入排序），这也是被普遍采用的一种缩小方式。
希尔排序的时间复杂度与空间复杂度：
- 时间复杂度：由于gap取值的变化性，希尔排序的时间复杂度是不固定的，很难进行准确计算。因此，我们再此不做过多解释，可以将希尔排序的时间复杂度简单理解为O(n ^ 1.3)。但就整体而言，希尔排序的时间复杂度优于直接插入排序。
- 空间复杂度：O(1)
2.2 选择排序
2.2.1 直接选择排序
直接选择排序的思想比较简单：在一个给定的序列中，找到最大值和最小值，然后把最大值放在这个序列末尾，最小值放在序列开头（如果排升序），然后这个序列在两边同时缩进一个，得到一个新的序列，再重复上述操作，直至序列长度为1时结束。
直接选择排序的代码如下：
void SelectSort(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int max = begin, min = begin;
for (int i = begin; i <= end; i++)
{
if (arr[i] > arr[max])
max = i;
if (arr[i] < arr[min])
min = i;
}
if (begin == max)
max = min;
swap(arr[begin++], arr[min]);
swap(arr[end--], arr[max]);
}
}
2.2.2 堆排序
在了解堆排序之前，我们必须清楚什么是堆。
堆具备如下性质：
- 堆是一棵完全二叉树
- 堆中某个结点的值总是不大于或不小于其父结点的值。因此，我们可得两类堆——根结点最大的堆，我们称为最大堆或大根堆，根结点最小的堆，我们称之为最小堆或小根堆。
对于堆，或者说对于完全二叉树，我们使用数组来存储，有以下存储规则。
- 对于具有n个结点的完全二叉树，如果按照从上至下，从左至右的数组顺序堆所有结点从0开始进行编号，则序号为i的结点有：
- 若i > 0 , i 位置父结点的序号为（i - 1）/ 2;i = 0时，为根结点，无父节点
- 若2i + 1 < n,则左孩子序号为2i + 1. 2i + 1 >= n,无左孩子
- 若2i + 2 < n,则右孩子序号为2i + 2, 2i + 2 >= n,无右孩子
2.2.2.1 向下调整算法建堆
既然要进行堆排序，我们肯定要先获取一个有效堆。统一起见，接下来我们都建大堆。
向下调整算法建堆代码如下所示：
void AdjustDown(int* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子结点
while (child < n)
{
if (child + 1 < n && arr[child] < arr[child + 1])
child++;
if (arr[child] > arr[parent])
{
swap(arr[child], arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
2.2.2.2 向上调整算法建堆
向上调整算法建堆的代码如下所示：
void AdjustUp(int* arr, int child)
{
int parent = (child - 1) / 2;//child结点的parent结点
while (child > 0)
{
if (arr[child] > arr[parent])
{
swap(arr[child], arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
2.2.2.3 进行堆排序
在获取有效堆之后，我们便可以开始堆排序。需要注意的是，堆只是保证了父结点与子结点之间的大小关系，并不保证整个数组是有序的，所以我们需要进一步处理。但堆有什么特殊性质呢？我们知道，大堆的根结点是最大的，小堆的根结点是最小的。
因此，我们利用这个性质，可以像堆弹出根结点一样，先把根结点所存储的数值与数组中最后一个子结点存储的数值进行交换，这样整个数组中最大的数（最小的数）就到了其所应到的位置上。然后，我们数组的大小减去1，即把此时的最后一个元素排除在外，之后再使用向下调整算法获得一个有效堆，再重复上述过程，直至数组中待处理的元素个数为1时，终止循环。
具体的代码如下所示：
//堆排序
void HeapSort(int* arr, int n)
{
//向下调整算法建堆
for (int i = (n - 2) / 2; i >= 0; i--)
AdjustDown(arr, i, n);
//向上调整算法建堆
for (int i = 1; i < n; i++)
AdjustUp(arr, i);
//两种建堆方式，选择一种即可
//已建立有效堆，进行堆排序
int size = n;
while (size > 1)
{
swap(arr[0], arr[size - 1]);
size--;
AdjustDown(arr, 0, size);
}
}
2.2.2.4 堆排序时间、空间复杂度分析
堆排序的时间复杂度需要分为两种情况来讨论：向上调整算法建堆和向下调整算法建堆。
当使用向上调整算法建堆时，此调整算法的时间复杂度为O(n * log n)。
当使用向下调整算法建堆时，此调整算法的时间复杂度为O(n)。
而对于已经建立的有效堆，进行实际堆排序时，即上述代码第二个循环的时间复杂度为O(n * log n)，与向上调整算法建堆的时间复杂度相同。
所以，将两个循环叠加，综合来看的话，堆排序的时间复杂度为O(n * log n)。但需要注意的是，实际上堆排序中使用向下调整算法建堆会优于使用向上调整算法建堆，所以堆排序中使用向下调整算法建堆会更普遍一些。
堆排序的空间复杂度显然为O(1)。
2.2.2.5 利用堆排序解决TOP-K问题
TOP-K问题在现实生活中是非常常见的，比如游戏中最活跃的10名玩家，一个公司中绩效最高的10个人。对于数据量不是很大的TOP-K问题，可以直接创建数组存储，然后直接排序。但现实中，数据量是非常大，内存中是存不下的，这种时候我们只能将这些数据放在文件中，在这种情况下，我们该如何解决TOP-K问题呢？
我们使用堆排序来解决。具体步骤如下：
- 先从所有数据中读取K个数据到内存中，存储在数组中。
- 对数组进行向下调整算法建堆（向上调整算法建堆），获得一个有效堆，此时堆的根结点就是整个堆的最大值（最小值）。
- 继续逐个从文件中读取数据，并与堆的根结点所对应数据比较，满足条件（大于或小于）即令此数据为堆的根结点。
- 向下调整算法建堆，之后不断重复步骤3和4，直至文件中的数据被读取完毕。此时，数组中的数据即为所要求得的TOP-K。
2.3 比较排序
2.3.1 冒泡排序
冒泡排序较为简单，时间复杂度为O(n ^ 2),此处不做解释，具体看代码：
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int flag = 1;
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
flag = 0;
}
}
if (flag)
break;
}
}
2.3.2 快速排序
快速排序的核心思想在于，在待排序的序列中选定一个基准值，然后通过一次快排，使得整个序列能够分为两个部分，一部分的值满足小于等于此基准值，另一部分的值满足大于等于此基准值，这是一次快排达到的效果。快速排序有递归与非递归之分。
2.3.2.1 快速排序的递归实现
快速排序的递归实现有很多种版本，如hoare版本,挖坑法以及lumuto的前后双指针快排，而对于快排基准值的选择也有很多，如取序列的开头或结尾，又或是中间数，或者随机取基准值。不同的版本下，再考虑到基准值所选取的不同，快排的具体写法是有差异的，但核心思想是不变的，最难处理的主要快排的边界问题，边界问题处理不好，快排就很容易陷入快排错误，或者死递归中。
以下对快排的递归实现不详细介绍，而是展示一个使用hoare快排的通用模板：
void QuickSort(int* arr, int l, int r)
{
if (l >= r)
return;
int i = l - 1, j = r + 1, x = arr[(l + r) >> 1];
while (i < j)
{
do i++; while (arr[i] < x);
do j--; while (arr[j] > x);
if (i < j)
swap(arr[i], arr[j]);
}
QuickSort(arr, l, j);
QuickSort(arr, j + 1, r);
}
2.3.2.2 快速排序的非递归实现
快速排序的非递归实现要借助数据结构栈。
本质上，因为是非递归实现，借助栈实际上是为了将一轮快排后，得到的左右子序列的边界存储起来，用于进行之后的快排，如此往复，直至栈为空，此时快排结束。
代码示例如下所示：
void QuickSort(int* arr,int l,int r)
{
stack<int> st;
if(l < r)
st.push(r),st.push(l);
while(!st.empty())
{
l = st.top(),st.pop();
r = st.top(),st.pop();
int i = l - 1,j = r + 1,x = arr[(l + r) >> 1];
while(i < j)
{
do i++;while(arr[i] < x);
do j--;while(arr[j] > x);
if(i < j)
swap(arr[i],arr[j]);
}
//先排左序列，再排右序列
if(j + 1 < r)
st.push(r),st.push(j + 1);
if(l < j)
st.push(j),st.push(l);
}
}
2.4 归并排序
2.4.1 归并排序的递归版本
归并排序是一种利用递归思想的排序算法，它的基本流程如下：
- 先对数组不断二分递归，直至划分出的每个小组别元素的个数为1，由此得到最小的有序序列
- 然后再对这些有序的序列，通过有序序列的合并方法，两两不断合并，直至合并出原数组大小的有序序列
归并排序的时间复杂度为O(n * log n)，但由于需要创建一个临时数组用于存储归并出的有序序列，因此归并排序的空间复杂度为O(n)。
具体代码如下所示：
void MergeSort(int* arr, int left,int right)
{
if (left >= right)
return;
int mid = (left + right) >> 1;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
int i = left, j = mid + 1;
vector<int> tmp;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
tmp.push_back(arr[i++]);
else
tmp.push_back(arr[j++]);
}
while (i <= mid)
tmp.push_back(arr[i++]);
while (j <= right)
tmp.push_back(arr[j++]);
//将tmp数组中的内容拷贝到arr数组的相应位置
for (int i = left, j = 0; i <= right; i++, j++)
arr[i] = tmp[j];
}
在这里补充一点知识，归并排序既是内排序，也是外排序。内排序，即排序数据全部存储在内存中的排序；而外排序则是排序数据不存储在内存中的排序。讲得准确些，外排序是由于排序数据量过大，导致这些数据无法全部读入内存中，因此将其存储在内存之外，比如硬盘的文件中。对于这种存储在硬盘文件上的数据，无法一次性拿到所有数据，只能读部分数据，再排这部分数据，如此循环。而归并排序的有序序列归并的思想是可以用于外排序的，因此归并排序可以用于给存储在文件中数量无比庞大的数据进行外排序。
2.4.3 归并排序的非递归版本
归并排序不用递归，使用循环来实现。
3. 非比较排序
非比较排序，即排序时不需要通过比较数据以确定数据之间的先后关系，而是通过一个计数数组以实现排序，我们将这种排序称为计数排序，又称为鸽巢原理。
具体代码如下所示：
void CountSort(int* arr, int n)
{
int max = arr[0], min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
int range = max - min + 1;
vector<int> count(range, 0);
for (int i = 0; i < n; i++)
count[arr[i] - min]++;
for (int i = 0, j = 0; i < range; i++)
while (count[i]--)
arr[j++] = i + min;
}
计数排序的时间复杂度为O(n)，空间复杂度为O(range)。
通过以上代码我们可以发现计数排序比较适用于待排序数据比较集中的情况，因为此时计数数组不用开得很大，空间复杂度不大；而若是数据很分散，计数数组需要开得比较大，甚至会出现range要远大于数据个数的情况，此时就不推荐使用计数排序。