前后指针法
int PartSort3(int* a, int left, int right) { int prev = left;//前指针 int keyi = left; int cur = prev + 1;//后指针 while (cur <= right) { if (a[cur] < a[keyi] && a[++prev] != a[cur])//在这里prev++是因为后续的交换是需要prev的后一位 Swap(&a[prev], &a[cur]); cur++; } Swap(&a[keyi], &a[prev]); return prev; }
上述代码 思路如下
当a[cur] < a[keyi]而且a[++prev] != a[cur]都成立时两者交换
当a[cur] >= a[keyi]的时候prev就不动.只cur++
最后交换a[keyi],a[prev]即可
这样我们就保证了
prev前的值都是比keyi小的(因为如果prev的值不比keyi大prev就++了)
最后结尾时a[prev]的值是小于或等于a[keyi]的.
https://ucc.alicdn.com/images/user-upload-01/img_convert/d777bf448175dedd0b2199e9fb1e8b63.gif
上述动图应该大家能看懂了=.=,上述动图来自[十大排序]有的人图画着画着就疯了(1.5w字详细分析+动图+源码)_君違的博客-CSDN博客(声明:图已经博主同意,而且我们两人是朋友.)
快排优化
快排最差的情况就是遇到一个有序的数组,及你想要一个1234但他给你了个4321让你排序.
这是我们的快排的时间复杂度能到O(N2);
有两种优化方法.
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 left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int PartSort3(int* a, int left, int right) { int midi = GetMidIndex(a, left, right);//得到中间值 Swap(&a[midi], &a[left]);//让中间值与基准值交换,这样基准值就不是最大的也不是最小值了. int prev = left;//前指针 int keyi = left; int cur = prev + 1;//后指针 while (cur <= right) { if (a[cur] < a[keyi]) { prev++; Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[keyi], &a[prev]); return prev; } void QuickSort(int* a, int left, int right) { if (left > right) { return; } // 小区间直接插入排序控制有序 if (right - left + 1 <= 30) { InsertSort(a + left, right - left + 1); } else { int keyi = PartSort3(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } }
经过优化后的快排就是库里的快排模式了.
非递归快排
我们递归的主要目的是为了给PartSort的函数传递一个还未经历过PartSort的区间,那么我们可以通过什么来使用非递归的条件来给我们的PartSort函数传递一个没有被排序的空间呢?
void QuickSortNonR(int* a, int left, int right) { //通过栈来模拟实现我们的递归得到的区间,从而实现非递归. ST st; StackInit(&st); StackPush(&st, left); StackPush(&st, right); while (!StackEmpty(&st)) { int end = StackTop(&st);//根据上面的入栈顺序来决定这里和下面的变量以及出栈顺序. StackPop(&st); int begin = StackTop(&st); StackPop(&st); int keyi = PartSort1(a, begin, end); if (begin < keyi - 1)//左半区间. { StackPush(&st, begin);//这个和下面那个if条件句里的顺序都不能乱. StackPush(&st, keyi - 1); } if (keyi + 1 < end)//右半区间. { StackPush(&st, keyi + 1); StackPush(&st, end); } } StackDestroy(&st); }
我们只需要改变一下QuickSort这个函数即可.
如果看注释可以看懂就没必要看下面的内容了.
使用一个栈来保存我们的左右区间范围.
注意:在未进循环的时候的那次StackPush是会影响到下面的顺序的.因为栈先进先出的性质
然后得到end begin来传给PartSort来进行排序并得到基准值的位置,然后通过基准值来分为左边和右边无排序的区间.
再经过判断区间的范围后入栈
直到不符合入栈条件后无法入栈我们的栈就空了,就跳出循环结束排序.
归并排序
归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度:O(N*logN)
空间复杂度:O(N)
稳定性:稳定
归并排序需要我们先理解合并的思路:88. 合并两个有序数组这道题就使用了合并的思路=.=
合并有序数组(跑路人笔记)我在这里对这道题进行了讲解不会的同学可以看一看.
先看图吧:(注从上向下看.)
//这个是子函数,整体思路请向下翻阅找到父函数. void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; int mid = (begin + end) / 2; _MergeSort(a, begin, mid, tmp); //经历了上面的函数递归后前一个区间就只有两个数值了 _MergeSort(a, mid + 1, end, tmp); //经历了上面两个函数的归并能保证下面的区间第一次只有两个值,再分成两部分就各自有序了(单个数字被看做有序) int begin1 = begin, end1 = mid;//将一个区间分为两个 int begin2 = mid + 1, end2 = end;//同上 int index = begin;//因为递归带来的头是不一样的所以用begin作为tmp内容的头部 //下面开始归并 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2])//用a内数值进行比较是因为 { tmp[index] = a[begin1]; begin1++; index++; } else { tmp[index] = a[begin2]; begin2++; index++; } } while (begin2 <= end2)//将未归并完的数值传递过去 tmp[index++] = a[begin2++]; while (begin1 <= end1)//同上 tmp[index++] = a[begin1++]; //将tmp里的排好序的区间传递到a内,所以a内也会因为这个而部分有序 memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } void MergeSort(int* a, int n) { //大致思路:通过合并时会将两个有序数组合并成一个有序的数组来进行排序. //整体思路:通过递归将数组分为一个个的小区间(一个数字为有序),再通过一个个小区间合并为一个一个个较大的区 //间最后使整个区间有序即可. int* tmp = (int*)malloc(sizeof(int) * n);//为了防止原数组的值被覆盖而建立的临时变量 assert(tmp); _MergeSort(a, 0, n - 1, tmp);//我们需要递归解决,建立一个子函数 free(tmp); }
通过递归将数组分为足够小的区间后层层合并最终得到我们想要的有序序列.
归并排序的非递归实现
我们可以使用循环的方式来避免递归的分解和合并.
我们只需要通过循环来实现上述思路即可.
除了要控制区间越界问题其他倒是没啥了.
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); assert(tmp); int gap = 1;//用来控制区间空间 while (gap < n) { for (int k = 0; k < n; k += 2 * gap) { int begin1 = k; int end1 = begin1 + gap - 1; int begin2 = k + gap; int end2 = begin2 + gap - 1; int index = begin1; if (end1 >= n) { end1 = n - 1; } if (begin2 >= n)//如果begin2越界了就使区间不存在 { begin2 = end2 + 1; } if (end2 >= n) { end2 = n - 1; } //归并 while (begin1 <= end1 && begin2 <= end2)//有一个序列为空就停止 { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } //将剩余数据放入tmp数组 while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } } memcpy(a, tmp, sizeof(int) * n); gap *= 2; } free(tmp); }
计数排序
计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
时间复杂度:O(MAX(N,范围))
空间复杂度:O(范围)
稳定性:稳定(这个稳定其实有点存疑因为通过计数排序得到的有序数组已经不是原来的数字了,而且计数排序是真的只能排序数字一旦数字里再多带点结构体啥的就不可以用计数排序了=.=)
找个数组将我们的数字出现的次数按照下标的对应位置(优化后为对应值-最小值对应下标的位置)保存起来,再通过数组的下标规则遍历--最终得到一个有序数组.
void CountSort(int* a, int n) { //下面得到我们的最大值和最小值 int max = a[0], min = a[0]; for (int i = 0; i < n; ++i) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } //找到数据的范围 int range = max - min + 1; int* countArray = (int*)malloc(range * sizeof(int)); assert(countArray); memset(countArray, 0, sizeof(int) * range);//初始化为0也可使用calloc函数 //存放在相对位置,可以节省空间 for (int i = 0; i < n; ++i) { countArray[a[i] - min]++; } //可能存在重复的数据,有几个存几个 int index = 0; for (int i = 0; i < range; ++i) { while (countArray[i]--) { a[index++] = i + min; } } }
结尾
我还是一个利益驱使的人.希望等我学到足够多的知识后可以让我得到兴趣.