数据结构排序
数据结构——排序
1. 排序概念及运用
1.1概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
1.2 常见的排序算法
2. 实现常见排序算法
int a[ ] = { 5 , 3 , 9 , 6 , 2 , 4 , 7 , 1 , 8 }
2.1 插入排序
基本思想：
直接插入排序是一种简单的插入排序法，其基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
在生活中，我们在玩扑克牌的时候就会用到插入排序的思想。
2.1.1 直接插入排序
将上面降序的数组转换成升序的数组
代码实现：
//直接插入排序
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n-1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else {
break;
}
}
arr[end + 1] = tmp;
}
}直接插入排序的特征：
- 元素的集合越接近有序，直接插入排序算法的时间效率会越高
- 时间复杂度：O(
- 空间复杂度：O(1)
当数组有序且为降序，将数组调整升序时，时间复杂度就会达到最大：O(
为了解决上述最坏的情况（当数组有序且为降序，将数组调整升序时），就有了其它的方法：希尔排序
2.1.2 希尔排序
希尔排序法又称为缩小增量法。希尔排序的基本思想是：先选定一个整数（通常是gap=n/3+1），把待排序的所有记录分成各组，将所有距离相等的记录放在一组并且进行排序，之后gap=gap/3+1得到下一个整数，再将排过序的数组进行分组排序，当gap=1时，就相当于直接插入排序了。
希尔排序是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。
希尔排序的特征：
希尔排序是对直接插入排序的优化。
当 gap > 1 时 都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。整体而言，可以达到优化的效果。
代码实现：
//希尔排序
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap>1)
{
//推荐写法：除3
gap = gap/ 3 + 1;
//直接插入排序
for (int i = 0; i < n - gap; i++) // i < n 的话，当 i = n-1时，end = n-1 tmp=arr[end+1]=arr[n] 此时访问就会越界
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];
end-=gap;
}
else {
break;
}
}
arr[end + gap] = tmp;
}
}
}运行结果：
2.1.2.1 希尔排序时间复杂度计算
外层循环：
外层循环时间复杂度直接给出为：O(logn)
内层循环：
希尔排序时间复杂度不好计算，因为gap的取值有很多，导致很难取计算，因此在书中给出的希尔排序的时间发现阿杜都不固定。
在严蔚敏的《数据结构（C语言版）》中给出的实现复杂度为：O()
2.2 选择排序
选择排序的基本思想：
每一次从待排序的数据元素中选出最小/最大的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
2.2.1 直接选择排序
//直接选择排序
void SelectSort(int* arr, int n)
{
int begin = 0, end = n-1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin+1; i <= end; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
//会出现问题，出现问题的原因是begin刚好是最大值
//若maxi和begin在同一位置
if (begin == maxi)
{
maxi = mini;
}
//找到小的了，找到大的了，发生交换
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
}
}直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(
- 空间复杂度：O(1)
2.2.2 堆排序
堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，他是选择排序的一种。它是通过堆来进行选择数据。注意：排升序建大堆，排降序建小堆。
堆排序在二叉树的内容中就有所提到，这里就不再写了。
2.3 交换排序
交换排序基本思想：
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前面移动
2.3.1 冒泡排序
冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点点像数组的一侧移动。
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
exchange = 1;
Swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}冒泡排序的特性总结：
- 时间复杂度：O(
- 空间复杂度：O(1)
五种排序的运行时间：
2.3.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序聚合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有的元素均大于基准值，然后最左右子序列重复该过程，直到所有的元素都排列在相应的位置上为止。
快速排序实现主框架：
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//1.找基准值
int keyi = _QuickSort(arr,left,right); //根
//2.二分
//[left , keyi-1] keyi [keyi+1 , right]
QuickSort(arr, left, keyi-1); //左侧部分二分 //左
QuickSort(arr, keyi + 1, right); //右侧部分二分 //右
}_QuickSort（找基准值）方法主要有以下几种实现方法：
2.3.2.1Hoare版本的快速排序
思路：
- 创建左右变量
- 从右到左找比基准值小的数据，从左到右找比基准值大的数据，左右指针数据交换，循环操作
问题1：为什么跳出循环后right位置的值一定不大于key?
因为跳出循环的条件是 left 大于 right，right 走到了 left 的左侧，即 left 扫过的区域，让 left 停止前进的原因是 left 大于 key，所以 right 位置的值小于等于 key。以下有3种场景：
问题2：为什么 left 和 right 位置的数据和key值相等也要交换？
当数组中大量的数据相同时，就不能进行有效的分割排序，会使时间复杂度效率大大降低。
代码实现：
//快速排序
//找基准值
//hoare版本
int _QuickSort(int* arr, int left, int right)
{
int keyi = left;
++left;
while (left <= right)
{
//right:从右往左找小于基准值的数据
while(left <= right && arr[right] > arr[keyi])//要不要arr[right] = arr[keyi]时要不要交换
{
right--;
}
//left:从左往右找大于基准值的数据
while(left <= right && arr[left] < arr[keyi])
{
left++;
}
//right 和 left 进行交换的条件是 left<=rifght
if (left <= right)
{
Swap(&arr[left++], &arr[right--]);
}
}
//跳出循环 left > right
Swap(&arr[keyi], &arr[right]);
return right;
}运行结果：
根据上面的情况得到，所以当 right 或 left 与基准值相等时也要发生交换，这样会大大降低时间复杂度。
其实当数组是有序或大量数据重复并且总是选择第一个元素或是最后一个元素作为基准值的时候，快速排序的时间复杂度会到达最大，也就是 O(N^2)，因为有序的时候找基准值的递归次数为n。
2.3.2.2 挖坑法
//找基准值——挖坑法
int _QuickSort1(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
while (left < right)
{
//right:找小的数据，成为新的坑
while (left < right && arr[right] > key)
{
right--;
}
//跳出循环——找到比基准值小的数据了
arr[hole] = arr[right];
hole = right;
//left:找大的数据，成为新的坑
while (left < right && arr[left] < key)
{
left++;
}
//跳出循环——找到比基准值大的数据了
arr[hole] = arr[left];
hole = left;
}
//跳出循环——left>right,将基准值key放在hole的位置上
arr[hole] = key;
return hole;
//返回基准值的下标
}运行结果：
但是当我们换一组数据的时候就会出现问题：
将数组的内容调整为：[8 8 7 1 8]
运行结果为：
挖坑版本的快速排序的正确代码如下：
//找基准值——挖坑法
int _QuickSort1(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
while (left < right)
{
//right:找小的数据，成为新的坑
while (left < right && arr[right] >= key)
{
right--;
}
//跳出循环——找到比基准值小的数据了
arr[hole] = arr[right];
hole = right;
//left:找大的数据，成为新的坑
while (left < right && arr[left] <= key)
{
left++;
}
//跳出循环——找到比基准值大的数据了
arr[hole] = arr[left];
hole = left;
}
//跳出循环——left>right,将基准值key放在hole的位置上
arr[hole] = key;
return hole;
//返回基准值的下标
}2.3.2.3 lomuto前后指针法（双指针法）
//找基准值——双指针法
int _QuickSort2(int* arr, int left, int right)
{
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
}
cur++;
//1.arr[cur] < arr[keyi]，并且prev和cur指向的不是同一个位置，发生交换，否则不交换
//2.arr[cur] > arr[keyi]，不进入循环，cur++
}
//跳出循环（cur越界）
Swap(&arr[prev], &arr[keyi]);
return prev;
}运行结果：
相同条件下，几种排序算法的比较：
可以看见快速排序的时间复杂度是最小的，执行的时间最少。
快速排序特性总结：
- 时间复杂度： O(nlogn)
- 空间复杂度：O(logn)
以上都是递归版本的快速排序，下面是非递归版本的快速排序
//非递归版本的快速排序
//借助数据结构——栈
int QuickSortNonR(int* arr, int left, int right)
{
Stack st;
StackInit(&st);
//左右下标入栈
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶元素——两次
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//对区间[begin,end]找基准值，双指针法
int prev = begin, cur = prev + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != arr[keyi])
{
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
//此时的prev就是基准值
keyi = prev;
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}2.4 归并排序
归并排序算法思想：
规避归排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用，将已有序的子序列和合并，得到完全有序的序列，即先使每个子序列有序，在世子序列间有序。沱江两个有序表合并为一个有序表，称为二路归并。
归并主要步骤：
代码实现：
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
//int mid = (left + right) / 2;//数据量大的时候就会导致溢出的情况
//安全写法：
int mid = left + (right - left) / 2;
//根据mid划分成两个序列：
//[left,mid] [mid+1,right]
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid+1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2<=end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else {
tmp[index++] = arr[begin2++];
}
}
//跳出循环，可能存在begin2越界，第一个序列没有全部放入tmp数组中
//跳出循环，可能存在begin1越界，第二个序列没有全部放入tmp数组中
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//将tmp数组中的数据挪回到arr数组中
for (int i = left; i <= right; i++)
{
//这里的i不能等于begin1，因为begin1会变化，应该赋值为一个不会变化的变量
arr[i] = tmp[i];
}
}
//归并排序
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}2.5 非比较排序
2.5.1 计数排序
前面的排序都是通过比较大小来进行排序的，有没有不通过比较大小来进行排序的算法呢？
当然有，计数排序就是不用通过比较大小来进行排序。计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将有序回收到原来的序列中
代码实现：
//非比较排序:计数排序
void Count(int* arr, int n)
{
int min = arr[0], max = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}
//申请数组大小
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail!\n");
return;
}
//初始化，也可以用realloc
memset(count, 0, sizeof(int) * range);
//统计次数
for (int i = 0; i < range; i++)
{
count[arr[i] - min]++;
}
//将count出现的次数还原到原数组中
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
free(count);
}运行结果：
计数排序时间复杂度：
时间复杂度为：O（N+range）
计数排序的空间复杂度：
空间复杂度：O（range）
计数排序的特性：
- 计数排序在数据范围集中时，效率很高，但是使用范围及场景有限。
- 时间复杂度：O(N+range)
- 空间复杂度：O(range)
- 稳定性：稳定
3.排序算法复杂度及稳定性分析
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录（有重复值），若经过排序，这些记录的相对次序保持不变，即在原序列中，arr[i] = arr[j]，且arr[i]在arr[j]之前，而在排序后的序列中，arr[i]仍在arr[j]之前，则称这种排序算法是稳定的，否则称为不稳定的。
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
| 冒泡排序 | O(n^{2}) | O(n^{}) | O(n^{2}) | O(1) | 稳定 |
| 直接选择排序 | O(n^{2}) | O(n^{2}) | O(n^{2}) | O(1) | 不稳定 |
| 直接插入排序 | O(n^{2}) | O(n^{}) | O(n^{2}) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n^{2}) | O(n^{1.3}) | O(n^{2}) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n^{}) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^{2}) | O(logn)~O(n^{}) | 不稳定 |
稳定性验证案例：
直接选择排序： 5 8 5 2 9
希尔排序：5 8 2 5 9
堆排序：2 2 2 2
快速排序： 5 3 3 4 3 8 9 10 11
