今天肝篇万字长文
目录
1.排序的概念及其运用
1.1排序的概念
1.2排序运用
1.3 常见的排序算法
2.常见排序算法的实现
2.1 插入排序
2.1.1基本思想
2.1.2直接插入排序
2.1.3 希尔排序( 缩小增量排序 )
2.2 选择排序
2.2.1基本思想
2.2.2 直接选择排序
2.2.3 堆排序
2.3 交换排序
2.3.1冒泡排序
2.3.2 快速排序
2.3.2 快速排序优化
2.3.2 快速排序非递归
2.4 归并排序
2.5 非比较排序
3.排序算法复杂度及稳定性分析
1.排序的概念及其运用 1.1排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的 *** 作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序
2.常见排序算法的实现 2.1 插入排序 2.1.1基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。例子：我们玩扑克牌洗牌的时候
2.1.2直接插入排序当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}比较简单
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为n的记录分在同一组内，并对每一组内的记录进行排序。然后，取更小的n，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。
希尔排序对插入排序进行了优化，进行了一步预排序 *** 作，当gap较大的时候，能把较大的数更快地往数据尾放，较小的数更快地往数据头放，但是越接近无序。当gap较小的时候，数据就越接近有序。
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n-gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}在这里我们取gap每次/3+1，能保证最后gap一定会取到1
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。
来自殷人昆老师的C++版数据结构
2.2 选择排序 2.2.1基本思想每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
2.2.2 直接选择排序在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素。若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
void SelectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)
{
int min = left;
int max = left;
for (int i = left + 1; i <= right; i++)
{
if (a[i] < a[min])
min = i;
if (a[i]>a[max])
max = i;
}
Swap(&a[min], &a[left]);
if (max == left)//最大的就是第一个的时候
{
max = min;
}
Swap(&a[max], &a[right]);
left++;
right--;
}
}把最小值放在最左边，最大值放到最右边即可
这里注意一个bug点，如果我们选到的最大值正好是最左边，那么把最小值与最左边交换后，最大值实际上变成了最小值所在的位置（交换前），因此要加一步判断，如果确实是这个情况，要把最大值位置更新。
直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
可以看一下下面这篇博客，讲的已经挺详细了
关于堆的博客
堆排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
是最最最最最初学的排序，现在看已经非常简单
冒泡排序
冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
目前位置还比较简单
2.3.2 快速排序重头戏来咯！
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int key = PartSort3(a, begin, end);
QuickSort(a, begin, key - 1);//对key左边排序
QuickSort(a, key + 1, end);//对key右边排序
}我们发现与二叉树前序遍历规则非常像，因此写递归框架时可想象二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
接下来我们来看三种常见将区间按照基准值划分成左右两半部分的常见方式，也就是实现每一次排序的方法PartSort（以下讲解全部默认选的key值是区间最左边的值且排升序，后续在优化部分可以优化）
1.hoare版本
我们选最左边为key值后，假设现在有两个小兵分别站在最左边和最右边，我们让最右边的小兵先走，他的任务是找比key所在位置的值小的数，找到后停下，左边的小兵再开始走，他的任务则是找比key所在位置大的数，找到后停下。交换两个小兵所在位置的数，然后重复上述步骤直到两个小兵相遇，两个小兵相遇后再交换相遇位置的数和key值所在位置的数。下面我们自己画图来理解一下，下面绿色代表左边小兵，红色代表右边小兵
右边的红色小兵先走，比key所在位置5小，停下，左边小兵开始走，找比key所在位置大的
两个小兵都完成任务了，交换两个小兵的值
接下来继续红色小兵先走，找比key小的
我们发现两个小兵相遇了，交换相遇位置和key处的值
原来我们的key所在的数是5，那么现在5左边都是比5小的数，5的右边都是比5大的数，我们的一趟排序是不是就好了？
那我们来思考一个问题，为什么我们要让右边的小兵先走？
先说答案：当选左边做key的时候，让右边先走，当选右边做key的时候，让左边先走
为什么呢，我们看刚刚的情况，当右边的小兵第二次开始走的时候，直接就走到了左边小兵第一次停下的地方，也就是说左边小兵还没有走，两个小兵就已经相遇，那这个相遇位置有什么特点？那就是相遇位置一定是比key小的数，因为左边小兵要停下，那么就一定要找到了比key大的数，然后和右边小兵找到的比key小的数交换，这样一来最后左边小兵所在位置一定是比key小的数，那有没有可能右边小兵停下后左边小兵没有找到比key大的数，而一直走到和右边小兵相遇呢？当然有
这种情况下是不是右边小兵一起步就找到然后停下了，然后左边小兵一直走，走到最右边，然后1和5交换，但是这样也同样满足了最后5的左边都是比5小的数。但是如果我们选左边做key的话，让左边先走，大家可以画第一次的情况，最后交换后的序列应该是 7 4 1 5 6 8，我们选的key5的左右显然不满足要求。下面来看一下递归版本的代码实现
int PartSort1(int* a, int left, int right)//hoare
{
int key = left;
while (left < right)
{
//找小
while (left < right && a[right] >= a[key])
{
--right;
}
//找大
while (left < right && a[left] <= a[key])
{
++left;
}
Swap(&a[right], &a[left]);
}
Swap(&a[key], &a[left]);
return left;
}这里我们看一下两个小兵找小和找大循环的判断条件，加了left 如果所有的数都比key大，那么右边的小兵就一直无法完成任务，一直往左边走，直到最后数组越界，还是没有找到，造成程序崩溃，因此要加这个限制条件。 第二个限制条件也一样，如果一个待排序数组全部都是一样的数，那么右边的小兵是不是也无法完成任务了，和上面一样，因此也要加这个限制条件。 再来看一个差不多思路的版本 2.挖坑法 我们还是以左边为key，不过这次这个key直接存着最左边的值，作为一个临时变量使用，这样最左边的数据有了临时拷贝我们就在最左边挖一个坑，左边有坑，左边的小兵当然不能走了，右边的小兵开始走，任务还是一样，找小，当找到后左边的小兵接收到这个数，就把这个数放到左边的坑里面，同时把坑填好，右边的小兵在自己的位置挖坑，然后左边的小兵出发找大，找到后给右边的小兵，右边的小兵把这个大的数放在自己的坑里，然后填坑，左边的小兵挖坑，再重复上述步骤，直到两个小兵相遇，相遇后把我们实现存储的最左边的值放到这个最后的坑里，这样就完成了。还是画图理解一下，我们用黑色代表坑所在的位置 右边小兵出发找小 找到后给左边小兵，然后挖坑，左边小兵填坑。 左边小兵出发找大 然后给右边小兵，左边小兵挖坑，右边小兵填坑。 右边小兵出发找小，和左边小兵相遇 这里其实还进行了挖坑填坑的处理，只不过因为两个小兵相遇了，所以看不出来。 交换相遇位置和存储的key值，也就是把key填入最后的坑里 顺利完成任务了，挖坑法比上一种方法较好理解，不需要理解为什么右边先走，因为左边有坑，左边的小兵是走不了的，因此右边小兵先走是显而易见的。下面来看代码的实现 判断条件和第一种一样，两种方法其实差不多。 最后来看一种效率最高但也是最难理解的方法 3.前后指针法 我们还是定义一个在后面的指针在开始时指向最左边，一个在前面的指针指向第二个数据，也就是最左边的下一个位置，然后还是定义一个key指向最左边，让右边cur指针去找小，如果找到小了，先让左边的prev指针往右走一个，然后交换左右指针所在位置所指的数，然后让右边指针再出发去找小。最后右边指针全部走完（遍历完数组后）让左边指针所在位置所指的数和key值所指的数交换即可。听着有点抽象，下面好好画一下图。这里我们换一组便于理解的数据来画图。 cur指针出发找小，碰巧的是一开始就找到了，让prev++，那么cur和prev就在一个位置了，交换与否都一样（在写代码的时候对这里进行优化），再让cur继续找，cur找到了2，再让prev++，这样prev从1走到了2，再（交换） 然后cur继续找小，找到3停下 让prev++ 交换两者的值 cur再出发找小，找到4，然后prev++ 交换 cur再出发找到了5，继续上述步骤，此处省略，直接出结果 cur继续出发找小，没找到 交换prev和key的数 这样完成后最终我们所选的key6左边的都是比6小的，右边都是比6大的，是不是非常神奇。 这种方法的精髓就在于，我们让cur去找小的过程，如果cur找到的是大，那么prev是不会动的，只有当找到后，再让prev++，然后交换，这样做就让cur和prev之间拉开差距，而这段”差距“区间存的数，就都是比key大的数，细细体会一下。 来看代码 这里我们加了一个判断，如果++prev指向的值等于cur指向的值后，那么就不进行交换了。剩下的都和我们上面分析的思路一致，这里注意如果&&左边判断为假则不会执行右边的表达式了，因此只有在cur找到了小以后才会把prev++ 告诉自己再学亿点点！！ 快排快排，固然是很快，但就算是快排也是有缺点的，就比如我们排一个数据全部是一样的数组，或者一个接近升序的数组，我们假设我们运气很差，每次都选左边选key，恰好这个key是最大或者最小的数，那么这样的话是不是每排一次都要计算n次，那排好的时间复杂度就是O(N^2)，因此我们不能每次都选最左边做key，这里我们采用三数取中，即比较最左边，最右边和中间的数，取三个数中中间大小的那个数做key。 还有一种优化方法，当我们排序递归到小的子区间时，考虑使用插入排序，设想我们要排4个数，那如果用快排，假设我们每次key划分区间都是严格二分，那这4个数要排好就要把左边2个数和右边2个数排好，左边2个数排好要再划分成1个数和1个数，分别排好返回，右边也是一样，这样相当于15次左右递归，而且递归层数太深的话会造成栈溢出。因此我们用插入排序（用希尔排序就大题小用了这里）对区间较小的数进行直接排序 快排的非递归实现要用到我们之前写的栈，用数据结构栈模拟我们内存中的栈，对栈不太了解的可以去看一下我的这篇博客吃饭的时候也能学的栈和队列 我们先看一下代码 其实和递归的思路是一样的，我们先把左右两个数作为一段区间压入栈，然后循环，在栈不为空（也就是还有区间没有排序完成）的情况下，先取出区间右端点，再取区间左端点（栈先入后出），然后对这段区间进行排序，再将key值左边的区间和key值右边的区间进行排序即可。 快速排序的特性总结： 基本思想： 我们要排这一组数据，那么就把这段区间分成左右两部分，分出来的子部分也进行同样步骤，直到无法再分（只有一个数就相当于有序了） 然后再进行合并，也就是新开辟一块空间，比较两段小区间中的数，依次找出较小的数，放到新空间中，如果一个区间没有数了，就把另一个区间的全部数直接放到新空间，再把新空间的数据拷贝给原数组，那么就实现了排序。 来看一下代码 总之，归并排序就是选划分小区域，进行小区域排序，小区域排序好后再合并成大区域，理解这个思想后代码并不难实现。 再来看一下归并的非递归版本 我们的递归版本是怎么实现的？不断划分直到区间中只有一个数，然后排序，合并成2,4,8,16这样的大区间，那我们非递归版本是不是可以像希尔一样控制一个间隔，让间隔从1开始，对小区间进行排序，然后让间隔gap*2，对2个区间长度为2的区间排序，以此往复，直到全部排完。下面来看代码，代码中有更细节的需要注意的地方 当我们满心欢喜的开始测试代码后 debug伤我千百遍 没错，程序崩了，因为我们数组越界了，想一想这是什么原因。我们知道归并不像快排，归并是严格二分的，他会把每次的区间严格二等分，那是不是只有在数据个数n=2^k次方的时候，我们刚刚写的归并才可以正常运行呢？因为按刚刚的逻辑，我们的总个数如果不是2的次方个，那么总会有一个gap是不等分我们的数据的。因此我们需要来修改一下我们刚刚写的代码。我们想一下在begin1、end1、begin2、end2中哪些可能会越界呢？首先begin1肯定不会越界，因为begin是用i控制的，而i不会越界，剩下的三个则都存在越界风险，那么我们来分别修正他们越界的情况 如果end1越界了，那么让end1指向最后一个元素即可，如果begin2已经越界，那么第二个区间就没有处理的必要，直接让第二个区间变成不存在的区间，也就是begin>=end的情况，如果begin2没有越界而end2越界了，处理和end1一样。 把这段代码加在变量begin和end定义后，我们的非递归版本就可以完美跑起来啦。 归并排序的特性总结： 思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 简单来说，比如说原来的数据是1,1,3,4,8,6，那么新建空间下标为1的地方就要存2，下标为3的地方存1，下标为4的地方存1，下标为6的地方为1，下标为8的地方为8，当然这是绝对对应的方法，也可以用相对对应，比如这里面8是最大的数，1是最小的数，那么我们就建一个长度为8-1+1=8的数组吗，那么现在1就对应为1-1=0,8就对应为8-1=7的下标，其余的同理对应下来。 来看一下代码实现： 总体来说比较简单 计数排序的特性总结： 下面我们来看看各排序真实的所用时间，每个排序排的数组数据相同，所测单位是ms，计数排序应用场景较小不参与比武 先来看有10万个数据下各排序release版本下的耗时 可以看到快排（优化）、希尔排序、堆排、 归并属于一个量级，都很快，接下来我们把数据加到1000万个，单独看看他们四个的表现 归并稳定发力，但是记住归并是有一定空间复杂度损耗的，所以损耗空间换取效率。不同排序有不同适用空间，要因情况而定。 好啦，就先到这里吧，排序还是要好好消化的！我已经榨干了。 欢迎分享，转载请注明来源：内存溢出int PartSort2(int* a, int left, int right)//挖坑法
{
int key = a[left];
int pit = left;
while (left < right)
{
//找小
while (left < right && a[right] >= key)
{
--right;
}
a[pit] = a[right];
pit = right;
//找大
while (left < right && a[left] <= key)
{
++left;
}
a[pit] = a[left];
pit = left;
}
a[pit] = key;
return pit;
}int PartSort3(int* a, int left, int right)//前后指针
{
int prev = left, cur = left+1;
int key = left;
key = left;
while (cur <=right)
{
if (a[cur] < a[key]&&a[++prev]!=a[cur])
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[key], &a[prev]);
return prev;
}
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
return mid;
else if (a[left] > a[right])
return right;
else
return left;
}
else
{
if (a[mid] < a[right])
return mid;
else if (a[left] > a[right])
return left;
else
return right;
}
}void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
if (end - begin+1 <= 10)
{
InsertSort(a+begin, end - begin + 1);
}
else
{
int key = PartSort3(a, begin, end);
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
}
2.3.2 快速排序非递归
void QuickSortNor(int* a,int begin, int end)//非递归版本
{
ST st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int keyi=PartSort3(a, left, right);
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st, keyi - 1);
}
if (keyi + 1 < right)
{
StackPush(&st, keyi+1);
StackPush(&st, right);
}
}
StackDestory(&st);
}
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
2.4 归并排序
归并排序（MERGE-SORT）是建立在归并 *** 作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用；即先使每个子序列有序，再使子序列段间有序，再将两个有序表合并成一个有序表，称为二路归并。来画图理解一下！void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin >= end)
return;
int mid = (end + begin) / 2;
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid+1, end);
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int index = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <=end1 )
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, tmp, 0, n - 1);
}void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
}
memcpy(a, tmp, n * sizeof(int));
gap *= 2;
}
free(tmp);
} if (end1 >= n)
{
end1 = n - 1;
}
if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
if (begin2 < n && end2 >= n)
{
end2 = n - 1;
}
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
2.5 非比较排序
*** 作步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
void CountSort(int* a, int n)
{
int min, max;
min = max = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
int* tmp = (int*)calloc(range,sizeof(int));
assert(tmp);
for (int i = 0; i < n; i++)
{
tmp[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (tmp[i]--)
{
a[j++] = i + min;
}
}
free(tmp);
}
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。比如当数据中有浮点数、字符串时就不能应用，有负数可以。
2. 时间复杂度：O（N+range）
3. 空间复杂度：O(range)
4. 稳定性：稳定
3.排序算法复杂度及稳定性分析
微信扫一扫
支付宝扫一扫
评论列表（0条）