【数据结构】八大排序算法详解
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
🧑💻作者 @情话0.0
📝专栏《数据结构》
👦个人简介一名双非编程菜鸟在这里分享自己的编程学习笔记欢迎大家的指正与点赞谢谢
排序
前言
在日常生活中我们经常需要对收集到的各种数据进行处理这些数据处理中用到的核心运算就是排序。例如手机App中的各种排行榜每年都会有的全国高校排行榜等等它们都是按照一定的规律来进行排序的。目前已有上百种排序算法此篇博客将介绍几类经典而又常用的排序算法包括基本的算法思想、实现代码及性能分析。
一、概述
所谓排序就是将待排序文件中的记录按照其中的某个或某些关键字的大小递增或递减的排列起来即将一组无序的记录序列调整为有序的记录序列。
1.排序的稳定性
当待排序记录的关键字均不相同时排序结果是唯一的否则排序结果不唯一。在待排序的文件中若存在多个关键宇相同的记录,经过排序后这些具有相同关键宇的记录之间的相对次序仍然保持不变,则该排序方法是稳定的若具有相同关键宇的记录之间的相对次序发生了变化则称这种排序方法是不稳定的。
2.排序的分类
根据排序时数据所占用存储器的不同可将排序分为两大类内部排序和外部排序。
内部排序待排序的数据量较少整个排序过程可以完全在内存中进行
外部排序待排序的数据量太大内存无法容纳全部数据整个排序过程需要借助外存才能完成即排序过程中要进行数据的内、外存交换。
按逐步扩大有序序列长度的方法可将内部排序分为五大类插人类、选择类、交换类、归并类和分配类。
插入类将无序子序列中的一个或几个记录插人有序序列中,从而增加记录的有序子序列的长度。
选择类从记录的无序子序列中选择关键字最小或最大的记录并将它加人有序子序列从而增加记录的有序子序列的长度。
交换类通过交换无序子序列中的记录从而得到其中关键字最小或最大的记录并将它加人有序子序列从而增加记录的有序子序列的长度。
归并类通过归并两个或两个以上的记录有序子序列逐步增加记录有序子序列的长度。
分配类唯一一类不需要进行关键字之间比较的排序算法它主要利用分配和收集两种基本操作实现整个排序过程。
3. 排序算法的性能评价
评价排序算法好坏的标准主要有两条时间复杂度、空间复杂度。
二、排序算法的实现
注以下排序算法都完成递增的排序实现
1.插入类排序
插入类排序的思想为在一个已排好序的有序序列内对待排序的无序序列的记录逐个进行处理每一步将一个待排序的记录与同组那些已经排好序的记录进行比较然后将其插入在有序序列的合适位置直到将所有的待排序记录全部插入为止。
整个过程与打扑克牌时整理手上的牌非常类似。手中的第一张牌无需整理以后每次从桌上拿到的牌与手上的牌从右向左或从左向右依次比较再将其插入到合适的位置直到取完牌为止。
根据插入排序待插入记录的插入位置不同而使用不同的实现算法直接插入排序、希尔排序。
1.1直接插入排序
动图演示
基本思路首先从序列第二个元素开始将其设置为key
然后与前面的元素一一比较若前面的元素比 key 大则将前面的元素往后挪动一个位置
直到遇到比 key 小的元素然后再将 key 放在空余的位置即可
以此类推直到将所有的元素都按照这样的方法插完。
看上图第一轮将 7 作为 key 然后与 5 比较发现比 key 小则不发生任何改动
第二轮将第三个元素 1 作为 key先与 7 比较将 7 往后移动一个位置key 与 5 再比较将 5 往后移动此时 key 前面的元素都已经比完则将 key 放在首位
第三轮及后续几轮以此类推完成排序。
代码实现
void InsertSort(int* array, int sz)
{
for (int i = 1; i < sz; ++i)
{
int j = i - 1;// j 作为 key 前面元素的标记
int key = array[i];
//循环的终止条件分别为将 key 前面的元素都往后挪动一个位置j == -1和 key 遇到一个比自己小的元素
while (j >= 0 && key < array[j])
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
直接插入排序总结
我们发现当所有的元素全部有序时只需进行比较的 n-1 次无需挪动元素那也就是说元素越接近有序算法的效率就越高。
最好时间复杂度O(n)所有元素为顺序最坏时间复杂度O(n^2)所有元素逆序
在整个排序的过程中没有借助任何空间所以空间复杂度为 O(1)
直接插入排序是稳定的。因为具有相同关键字值的元素必然插在具有同一值的前一个元素的后面即它们之间的相对顺序不变。
1.2 希尔排序( 缩小增量排序 )
希尔排序法的基本思想是先选定一个整数gap把待排序文件中所有记录分成gap个组所有距离为 gap 的记录分在同一组内并对每一组内的记录进行插入排序。然后对 gap 缩减重复上述分组和排序的工作。当到达 gap==1时所有记录在统一组内排好序。
对于希尔排序我们将前几轮的排序称为预排序目的就是为了让整个序列基本有序然后再对全体元素完成一次直接插入排序。因为直接插入排序在元素基本有序的情况下效率很高。
代码实现
void ShellSort(int* array, int sz)
{
int gap = sz;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = gap; i < sz; ++i)
{
int key = array[i];
int j = i - gap;
while (j >= 0&&key<array[j])
{
array[j + gap] = array[j];
j -= gap;
}
array[j + gap] = key;
}
}
}
注意 该算法在具体实现时并不是先对一个子序列完成所有插入排序操作再对另一个子序列进行而是从第一个子序列的第二个元素开始顺序扫描整个待排序序列当前待排序元素属于哪一个子序列就在它相应的的子序列中进行排序。因而各个子序列地元素将会轮流出现即算法将在每一个子序列中轮流进行插入排序。
希尔排序总结
在希尔排序开始时增量gap较大分组越多每组的元素越少因此各组内直接插入较快。后来增量逐渐缩小分组数逐渐减少每组内的元素个数越多直接插入越慢但是越接近有序。
时间复杂度在O(nlogn) ~ O(n^2) 之间最好时间复杂度为O(n^1.3) 最坏时间复杂度为O(n^2)。
空间复杂度为O(1)。
希尔排序是一种不稳定的排序算法。
2. 选择类排序
选择类排序的基本思想是在第 i 趟的序列中选择第 i 小的元素作为有序序列的第 i 个元素。该算法的关键就在于如何从剩余的待排序序列中找出最小或最大的元素。
2.1 简单选择排序
动图演示
基本思路从第一个元素开始从头向尾遍历标记序列中最小的元素待所有元素对比完之后与第一个元素交换然后继续从第二个元素开始继续比较直到完成最后只有两个元素的交换。
代码实现
void SelectSort(int* array, int sz)
{
for (int i = 0; i < sz- 1; ++i)
{
// 找当前区间中最大元素的位置
int maxPos = 0;
for (int j = 1; j < sz- i; ++j)
{
if (array[j] > array[maxPos])
maxPos = j;
}
//加一层判断若最大元素就在待排序序列的末尾就无需交换
if (maxPos != sz- i - 1)
{
Swap(&array[maxPos], &array[sz- i - 1]);
}
}
}
上面的代码在每一次遍历过程将最大值找到并将其放在待排序序列末尾其实还可以对其进行优化就是再一次的遍历过程中既找到最大值也找到最小值并将这两个值放在合适的位置上。
简单选择排序代码优化
void SelectSortOP(int* array, int sz)
{
int begin = 0, end = sz- 1; // [begin, end]
while (begin < end)
{
// 在[begin, end]区间中找最大和最小的元素
int maxPos = begin, minPos = begin;
int j = begin + 1;
while (j <= end)
{
if (array[j] > array[maxPos])
maxPos = j;
if (array[j] < array[minPos])
minPos = j;
++j;
}
// 如果最大元素不在区间最后的位置
if (maxPos != end)
Swap(&array[maxPos], &array[end]);
// 如果end位置存储的刚好是最小的元素上面的交换就将最小的元素位置更改了---maxPos
// 最小元素的位置发生了改变则必须要更新minPos
if (minPos == end)
minPos = maxPos;
// 如果最小元素不在区间起始的位置
if (minPos != begin)
Swap(&array[minPos], &array[begin]);
++begin;
--end;
}
}
注意 对简单选择排序的优化代码一定要注意待排序序列的末尾刚好存放的最小元素或者首部存放的是最大元素在发生交换时就会出现错误。假设说末位存放着最小元素当你先将最大元素交换到末位此时最大元素已经就位然后要将最小元素放在首位可是最小元素的标记指向着末位当你再完成最小元素的交换时就会发现把刚换过来的最大元素交换到了前面。所以说一定要注意最大元素或最小元素标记的改变。
简单选择排序总结
简单选择排序很容易理解但是它的效率实在太低很少使用。
时间复杂度为O(n^2)
空间复杂度为O(1)
简单选择排序是不稳定的
2.2 堆排序
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。
想要完成堆排序首先要通过向下调整算法将二叉树这样的数据结构建成一个堆然后再利用堆删除的思想完成排序。
2.2.1 堆向下调整算法
假若现在给你一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};
void Swap(HPDataType* left, HPDataType* right)
{
HPDataType temp = *left;
*left = *right;
*right = temp;
}
void AdjustDown(Heap* hp,int n,int parent)
{
int child = parent * 2 + 1; //调整结点的左孩子
while (child < n) //当child大于结点个数时调整完毕
{
//判断是否有右孩子并且右孩子大于左孩子
if (child + 1 < n&&hp->array[child] < hp->array[child + 1])
{
child += 1;
}
if (hp->array[child]>hp->array[parent])
{
Swap(&hp->array[child], &hp->array[parent]); //若孩子大于父亲则交换
//继续向下调整继续判断
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}
2.2.2 堆排序
在堆建立完毕之后利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。
思路 1完成建堆让其拥有父亲结点大于孩子结点的特性或者父亲结点小于孩子结点
2交换根结点与最后一个孩子结点那么此时最大的结点就来到了堆的最后一位将堆的元素个数减一然后在从根结点刚交换上去的结点完成向下调整算法。《注意 堆的顺序结构是用数组实现的所以说将堆元素个数减一并不是将其删除而是将其放在了数组的最后一个位置》
3一直持续到最后两个结点将其完成交换即可完成堆排序。
void Swap(HPDataType* left, HPDataType* right)
{
HPDataType temp = *left;
*left = *right;
*right = temp;
}
void AdjustDown(int* array, int root, int sz)
{
// 用child标记parent较大的孩子默认先标记parent的左孩子
// 先标记左孩子的原因是如果parent有孩子parent一定是先有左孩子然后才有右孩子
int parent = root;
int child = parent * 2 + 1;
while (child < sz)
{
// 找parent中较大的孩子用parent左右孩子比较
// 必须先保证parent的右孩子存在
if (child + 1 < sz && array[child + 1] > array[child])
{
child += 1;
}
// 检测parent是否满足堆的性质
if (array[parent] < array[child])
{
Swap(&array[parent], &array[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* array, int sz)
{
int root = sz - 2 / 2;
// 1. 建堆
// 注意从倒数第一个非叶子节点的位置开始使用堆调整一直调整到根节点的位置
for (int i = root; i >= 0; --i)
{
AdjustDown(array, i, sz);
}
// 2. 排序--->利用堆删除的思想进行排序
for (int i = sz - 1; i > 0; --i)
{
Swap(&array[0], &array[i]);
AdjustDown(array, 0, i);
}
}
堆排序的时间代价主要花费在建堆和排序上
建堆的时间复杂度
因此建堆的时间复杂度为O(n)。
排序的时间复杂度
首先要明白的是建好堆之后然后通过堆删除的思想来排序。而堆删除的思路是怎样先将根结点与最后一个结点交换然后把根结点放在数组地末位然后数组元素减一再将刚换上去地结点去执行向下调整算法直到将所有地元素都交换完毕。我们发现对于每一个元素都要执行一次向下调整算法而向下调整算法向下走的是单支树所以向下调整算法的时间复杂度为O(logn)那么对于n个节点来说完成整个排序的时间复杂度就为O(nlogn)。
所以堆排序的时间复杂度为O(n)+O(nlogn)因为大O的渐进表示法的表示堆排序的时间复杂度为O(nlogn)
空间复杂度为O(1)
堆排序是一种不稳定的排序算法。
3. 交换类排序
交换类排序算法的基本思想为将待排序序列的元素两两比较只要发现逆序就进行交换知道没有逆序为止。如果要将整个序列调整为递增序列那么元素之间是递减关系就为逆序。冒泡排序和快速排序就是典型的交换类排序算法。
3.1 冒泡排序
动图演示
冒泡排序也叫做“相邻比逆法”即在扫描待排序记录序列时顺次比较相邻两个元素大小如果逆序就交换位置。如果以将序列调整成升序为例则逆序为两个关键字是降序序列。
具体地各趟排序过程如下
第1趟比较第1和第2个元素如果逆序就交换再依次比较第2个和第3个元素、第3个和第 4 个…若是逆序则交換。经过该趟比较和交换最大的数必然“沉到”最后一个位置。
第2趟用同样的方法在前面的 n-1 个元素中依次进行比较和交换第2大的数“沉到”倒数第2个位置上。
第 i 趟仍用同样方法在剩下的 n-i+1 个元素中依次进行比较和交换第 i 大的数“沉到”倒数第 i 个位置上。
重复此过程直到 i=n-1最后一趟比较完为止。
代码实现
void BubbleSort(int* array, int sz)
{
// 控制冒泡的趟数
for (int i = 0; i < sz- 1; ++i) // -1的目的是可以少冒一趟因为最后一次冒泡区间中只剩余一个元素
{
// 具体冒泡的方式用相邻位置的元素进行比较如果不满足条件就进行交换
// j表示后一个元素的下标j要取到最后一个元素
for (int j = 1; j < sz- i; ++j) // -1目的j最多只能取到冒泡区间的倒数第二个元素
{
if (array[j-1] > array[j])
Swap(&array[j], &array[j - 1]);
}
}
}
同样我们可以对上面的代码进行优化优化的点在哪呢就是万一在排序的过程中序列已经顺序了那就没有必要再冒泡下去了此时我们便设置一个标记 flag 每次冒泡前将其设置为0若在一趟冒泡中发生了元素交换就说明元素并没有顺序便将其改为1若在一趟冒泡中没有发生任何元素的交换就说明该序列顺序那么 flag 就不会被更改然后就直接退出最外层的循环完成了冒泡排序。
void BubbleSortOP(int* array, int sz)
{
int flag = 0;
for (int i = 0; i < sz- 1; ++i) // -1的目的是可以少冒一趟因为最后一次冒泡区间中只剩余一个元素
{
flag = 0; // 该趟冒泡还没有比较因此将falg设置为0
for (int j = 1; j < sz- i; ++j) // -1目的j最多只能取到冒泡区间的倒数第二个元素
{
if (array[j - 1] > array[j])
{
Swap(&array[j], &array[j - 1]);
flag = 1; // 在该趟冒泡时区间还无序
}
}
if (!flag)
return;
}
}
冒泡排序总结
冒泡排序在最好的情况下是序列为顺序那么外层循环只进行一次就结束整个排序过程最好的时间复杂度位O(n)但在最差的情况下外层循环最多进行 n-1 次每一次外层控制的内层循环进行 n-i 次最坏的时间复杂度为O(n^2)
空间复杂度O(1)
冒泡排序是一种不稳定的排序算法。
3.2 快速排序
快速排序是一种应用非常广泛的排序算法从它的名字就可以看出它的排序效率是比较高的。在1962年Hoare提出了一种划分交换排序由于它几乎最快的排序算法所以就被称为“快速排序”。
快速排序采用了一种分治的策略分治法的基本思想是将原问题分解为若干个规模更小的问题但结构与原问题相似的子问题递归的解这些子问题然后将这些子问题的解组合称为原问题的解。
基于这样的思想快速排序的基本思想为取待排序元素序列中的某一元素作为基准值我们假设取最左边的值为基准值按照该基准值将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后在左右子序列重复该过程直到所有元素都排列在相应位置上为止。可以看出快速排序的遍历规则与二叉树的前序遍历非常类似的。
接下来将从以下几个方面来对快排做一个详细介绍
3.2.1 hoare版本
动图演示
基本思想选择待排序序列最左边的元素为基准值key左右标记分别指向序列的第一个元素和最后一个元素先让右标记往左走当找到比key小的数字停下来然后再让左标记往右走当找到比key大的数字停下来交换左右标记对应的数字然后继续这样的操作直到左右标记指向同一个元素左右标记相遇然后再交换基准值key和左右标记指向的元素。
这样快排的一轮排序就完成了可以看到每当完成一轮排序总会有一个元素落位到它该在的位置。
代码实现
void swap(int* left, int* right)
{
int temp = *left;
*left = *right;
*right = temp;
}
int Partion(int* array, int begin, int end)
{
int left = begin;
int left = end;
int keyi = left;//基准值
while (left < right)
{
//右标记向左走直到找到小于key的元素就停下
while (left < right&&array[right] >= array[keyi])
{
--right;
}
//左标记向右走直到找到大于key的元素就停下
while (left < right&&array[left] <= array[keyi])
{
++left;
}
swap(&array[left], &array[right]);
}
//交换基准值key和左右标记指向的元素
//加判断的原因在于key右边的元素都比它小所以就没有必要进行交换操作
if (end != left)
{
swap(&array[left], &array[keyi]);
}
//返回已经被放好元素的位置也就是key最终所在的位置
return begin;
}
void quicksort(int* array, int left, int right)
{
//排序的终止条件左右标记指向同一个元素也就是待排序序列只有一个元素
if (left >= right)
{
return;
}
int div = Partion(array, left, right);
//排序刚放好位置元素的左半边
quicksort(array, left, div - 1);
//排序刚放好位置元素的右半边
quicksort(array, div + 1, right);
}
3.2.2 挖坑法
动图演示
基本思想同样选择序列的最左边值为基准值左右标记分别指向序列的第一个元素和最后一个元素那个坑位就是key所在的位置先让右标记向左走当找到比key小的元素停下然后将该元素放置到那个坑位此时就有了一个新坑位而刚才的坑位就被填补了然后再让左标记向右走当找到比key大的元素停下然后将该元素放置到新坑位直到左右标记共同指向一个位置也就是指向了一个坑位然后再把基准值放到那个坑位就结束了一次排序过程。
和hoare版本一样每当完成一轮排序总会有一个元素落位到它该在的位置。
代码实现
int Partion(int* array, int begin, int end)
{
int left = begin, right = end;
int key = array[begin];
while (left < right)
{
while (left < right && array[right] >= key)
{
--right;
}
if (left != right)
{
array[left] = array[right];
}
while (left < right && array[left] <= key)
{
++left;
}
if (left != right)
{
array[right] = array[left];
}
}
array[left] = key;
return left;
}
void quicksort(int* array, int left, int right)
{
if (left >= right)
{
return;
}
int div = Partion(array, left, right);
quicksort(array, left, div - 1);
quicksort(array, div + 1, right);
}
3.2.3 双指针前后指针
动图演示
基本思想同样选择序列的最左边值为基准值cur指向第二个元素prev指向第一个元素。cur先向右移动当遇到比key小的元素停下来然后再与prev的下一个元素交换。一直持续这样的操作直到cur将所有元素都遍历完然后再将prev指向的元素与key交换。这样该序列也就被分为两块。在这过程中可以发现cur和prev中间的元素都是比key大的元素。
代码实现
int Partion(int* array, int begin, int end)
{
int key = array[begin];
int cur = begin+ 1, prev = begin;
while (cur <= end)
{
if (array[cur] < key && ++prev != cur)
{
Swap(&array[cur], &array[prev]);
}
++cur;
}
Swap(&array[prev], &array[begin]);
return prev;
}
void quicksort(int* array, int left, int right)
{
if (left >= right)
{
return;
}
int div = Partion(array, left, right);
quicksort(array, left, div - 1);
quicksort(array, div + 1, right);
}
3.2.4 栈实现 非递归
上面三种快速排序算法都是以递归的方法实现的下面这个方法借用栈来实现非递归的排序算法。
第一步将序列的左右标记分别入栈然后进入循环判断条件为栈是否为空再将左右标记出栈
第二步利用刚出栈的这两个参数左右标记使用排序算法Partion(array, left, right)以key为基准将序列分割称为两部分左边比key小右边比key大然后返回key所在的位置
第三步现在就有两个待排序的序列它们之间隔着一个刚落好位置的key将这两部分序列的左右标记分别入栈要做到与快排同样的基本思想前序遍历我们得先将key的右半部分入栈再入栈key的左半部分。
最后当key的左右两边都只有一个元素或没有元素时就停止入栈那么再进入到循环判断条件时因为栈空就退出循环至此非递归的快排就结束了。
int Partion(int* array, int begin, int end)
{
int key = array[begin];
int cur = begin+ 1, prev = begin;
while (cur <= end)
{
if (array[cur] < key && ++prev != cur)
{
Swap(&array[cur], &array[prev]);
}
++cur;
}
Swap(&array[prev], &array[begin]);
return prev;
}
void QuickSortNor(int* array, int begin, int end)
{
Stack s;
StackInit(&s);
StackPush(&s, begin);
StackPush(&s, end);
while (!StackEmpty(&s))
{
int right = StackTop(&s);
StackPop(&s);
int left = StackTop(&s);
StackPop(&s);
int keyi = Partion(array, left, right);
if (keyi + 1 < right)
{
StackPush(&s, keyi + 1);
StackPush(&s, right);
}
if (left < keyi - 1)
{
StackPush(&s, left);
StackPush(&s, keyi - 1);
}
}
StackDestroy(&s);
}
3.2.5 快排优化三数取中法+小区间优化
3.2.5.1 三数取中法
为什么要用到三数取中法来进行优化就是因为万一选取的基准值刚好是该序列的最小值那么在一趟排序完成之后并没有什么效果只是那个基准值的位置刚好落位了但是它右边的元素都没有任何变化所以说为了避免这样的情况发生我们采取三数取中法来进行优化。
三数取中法是怎样操作的呢选序列的最左、右边和中间的三个值比大小将那个中间值放在最左边作为基准值然后再去执行排序算法。
代码实现
int GetMiddleIndex(int* array, int left,int right)
{
int mid = (left + right) / 2;
if (array[left] < array[mid])
{
if (array[mid] < array[right])
return mid;
if (array[right] < array[left])
return left;
else
return right;
}
else
{
if (array[left] < array[right])
return left;
if (array[right] < array[mid])
return mid;
else
return right;
}
}
3.2.5.2 小区间优化
想一下快排的思想就是不断地分割小序列然后再递归实现它的每一层的递归次数以2倍的次数进行增长。当元素较多时以递归的方法实现是不错的但是当序列元素较少时再使用递归就没有必要了我们可以选择使用其他的排序方法来实现小序列的排序。
void QuickSort(int* array, int left, int right)
{
if (right - left < 16)
{
// [left, right)区间中数据少到一定程度使用插入排序来优化
InsertSort(array + left, right - left);
}
else
{
int div = Partion(array, left, right);
QuickSort(array, left, div);
QuickSort(array, div + 1, right);
}
}
将这两种优化算法应用到双指针排序算法中
int GetMiddleIndex(int* array, int left,int right)
{
int mid = (left + right) / 2;
if (array[left] < array[mid])
{
if (array[mid] < array[right])
return mid;
if (array[right] < array[left])
return left;
else
return right;
}
else
{
if (array[left] < array[right])
return left;
if (array[right] < array[mid])
return mid;
else
return right;
}
}
int Partion(int* array, int begin, int end)
{
int midex = GetMiddleIndex(array, begin, end);
if (midex != begin)
{
Swap(&array[midex], &array[begin]);
}
int key = array[begin];
int cur = begin+ 1, prev = begin;
while (cur <= end)
{
if (array[cur] < key && ++prev != cur)
{
Swap(&array[cur], &array[prev]);
}
++cur;
}
Swap(&array[prev], &array[begin]);
return prev;
}
void QuickSort(int* array, int left, int right)
{
if (right - left < 16)
{
// [left, right)区间中数据少到一定程度使用插入排序来优化
InsertSort(array + left, right - left);
}
else
{
int div = Partion(array, left, right);
QuickSort(array, left, div);
QuickSort(array, div + 1, right);
}
}
快速排序总结
快速排序的时间复杂度为O(nlogn)
在平均情况下快速排序总共需要分割 logn 次即需要 logn 个辅助空间所以空间复杂度为O(logn)
快速排序是一种不稳定的排序算法。
4. 归并类排序
4.1 归并排序 二路归并
动图演示
归并排序也是一种基于分治法的排序。归并排序是将原始无序序列分成两个子序列然后分别对这两个子序列递归地进行排序最后再将有序子序列合并。
归并排序是通过不断划分子序列·直到每个子序列只有一个元素时就停止划分然后将这两个子序列的元素一一比较合并为一个有序序列。看上图先对序列不断划分直到每个子序列只剩下一个元素就开始归并。第一次归并时5和7各自为一个序列 然后将5和7合并为57然后再合并1和2为12下一步将刚刚合并的两个已经各自顺序的序列5712进行合并为一个序列为1257然后再去合并另外一半当另一半合并完3689再将这两半序列合并为一个序列就结束了。它的遍历过程大致和后序遍历类似。
void _MergeSort(int* array, int begin, int end, int* tmp)
{
//当整个序列只剩下一个元素就不再划分
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;
//不断地划分子区间
_MergeSort(array, begin, mid, tmp);
_MergeSort(array, mid + 1, end, tmp);
//开始归并
int left1 = begin, right1 = mid; //第一个序列的左右标记
int left2 = mid + 1, right2 = end; //第二个序列的左右标记
int i = begin;
while (left1 <= right1&&left2 <= right2)
{
//一、先将该归并的元素的放在一个新数组中
//新数组的作用仅仅是一个过渡的作用最终还是要归还已排好序的元素给原数组
if (array[left1] < array[left2])
{
tmp[i++] = array[left1++];
}
else
{
tmp[i++] = array[left2++];
}
}
//将另外一个序列中还未添加的元素递补进新数组中
while (left1 <= right1)
{
tmp[i++] = array[left1++];
}
while (left2 <= right2)
{
tmp[i++] = array[left2++];
}
//二、待该归并的元素归并完之后再将这几个元素拷贝到原数组中
memcpy(array + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}
void MergeSort(int* array, int sz)
{
int* tmp = (int*)malloc(sizeof(int)*sz);
_MergeSort(array, 0, sz - 1, tmp);
}
4.1 归并排序非递归
归并排序的非递归的大致思路为第一步设置一个步长 rangeN == 1根据这个步长控制归并序列的元素个数。同时设置四个标记分别指向左序列的第一个元素left1和最后一个元素right1右序列的第一个元素left2和最后一个元素right2然后从两个序列的左标记开始比对归并。
第一轮归并时步长为1先归并前两个元素左右序列各一个元素接着在归并后续的两个元素一直持续这样的方法直到所有的元素都两两归并完
第二轮先将步长rangeN*2左右序列各自两个元素然后继续从序列左边开始先归并前四个元素接着归并后续四个元素同样直到所有元素归并完开始下一轮
后续的做法都是一样增加步长再归并当最终只剩下两个待排序的有序序列时在完成一次归并之后就完成整个序列的归并。
根据整个过程来看它的遍历过程类似于二叉树的层序遍历。
注意 非递归的归并排序大致思路就是这样但是其中还是有点小问题就是每次归并的两个序列的左右标记有可能存在越界的问题。
①此时进行的是每个序列有两个元素的归并rangeN == 2但是整个序列只有九个元素前八个元素都可以正常进行归并但是从第九个元素开始只有第一个序列左标记没有越界
②同样步长为2序列只有十个元素那么第一个序列的左右标记是好的第二序列的左右标记都会越界
③步长为2序列有十一个元素那么只有第二序列的右标记越界。
当遇到这样不同的情况我们要做出不同反应对于第一种和第二种情况右序列不存在而左序列是有序的所以无需任何操作直接退出开始下一轮的归并即可。对于第三种来说左右序列都有元素所以就得将右序列的右标记进行改动让其指向最后一个元素即可。
void MergeSortNonR(int* array, int sz)
{
int* tmp = (int*)malloc(sizeof(int)*sz);
int rangeN = 1;
while (rangeN < sz)
{
for (int i = 0; i < sz; i += 2*rangeN)
{
int left1 = i, right1 = rangeN + i - 1;
int left2 = rangeN + i, right2 = i + 2*rangeN - 1;
if (right1>=sz)
{
break;
}
else if (left2 >= sz)
{
break;
}
else if (right2 >= sz)
{
right2 = sz - 1;
}
int j = i;
while (left1 <= right1&&left2 <= right2)
{
if (array[left1] <= array[left2])
{
tmp[j++] = array[left1++];
}
else
{
tmp[j++] = array[left2++];
}
}
while (left1 <= right1)
{
tmp[j++] = array[left1++];
}
while (left2 <= right2)
{
tmp[j++] = array[left2++];
}
memcpy(array + i, tmp + i, sizeof(int)*(right2 - i + 1));
}
rangeN *= 2;
}
free(tmp);
tmp = NULL;
}
归并排序总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题
时间复杂度为O(nlogn)
空间复杂度为O(n)因为要借助一个新数组来起到拷贝的作用
归并排序是一种不稳定的排序算法。
5. 分配类排序
5.1 计数排序
计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤
统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中
void CountSort(int array[], int size)
{
// 1.找数据范围--->O(N)
int minValue = array[0];
int maxValue = array[0];
for (int i = 1; i < size; ++i)
{
if (array[i] > maxValue)
maxValue = array[i];
if (array[i] < minValue)
minValue = array[i];
}
// 2.计算用来计数的空间个数maxValue-minValue+1, 申请用来保存计数的空间
int range = maxValue - minValue + 1;
int* temp = (int*)malloc(range*sizeof(int));
memset(temp, 0, sizeof(int)*range);
// 3. 统计区间中每个元素出现的个数--->O(N)
for (int i = 0; i < size; ++i)
temp[array[i] - minValue]++;
// 4. 回收: 按照计数数组下标从小到大进行回收--->O(N)
int index = 0;
for (int i = 0; i < range; ++i)
{
while (temp[i]--)
{
array[index++] = i + minValue;
}
}
free(temp);
}
计数排序的特性总结
时间复杂度O(N) N: 表示元素的个数
空间复杂度O(M) M:表示数据范围中包含数据的种类的个数
稳定性 稳定
场景数据密集集中在某个范围中
排序算法复杂度及稳定性分析
| 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 直接插入排序 | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) ~ O(n^2) | O(1) | 不稳定 |
| 简单选择排序 | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(1) | 不稳定 |
| 冒泡排序 | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(logn)~O(n) | 不稳定 |
| 归并排序 | O(nlogn) | O(n) | 稳定 |