【C语言/数据结构】排序(快速排序及多种优化|递归及非递归版本)
🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482
(图片来源网络,侵删)
目录
交换排序
快速排序
hoare版代码呈现
快排优化
(图片来源网络,侵删)
三数取中法
小区间优化
挖坑法
前后指针版本
非递归版本快排
前言
💬 hello! 各位铁子们大家好哇。
(图片来源网络,侵删)
今日更新了快速排序的内容
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
交换排序
快速排序
快排的过程图如下:
hoare版代码呈现
void QuickSort(int* a, int begin,int end) { if (begin >= end) { return; } int left = begin, right =end; int keyi = begin; while (left = a[keyi]) { right--; } //左边找大 while (left
如果左边做key,R先走。
如果右边做key,L先走。
快排优化
- 三数取中法选key
- 递归到小的子区间时,可以考虑使用插入排序
三数取中法
快排对于有序的数据,效率不是很高。
如上图,我们前面的快排是固定选key的,也就是左边第一幅图,效率很低。理想情况下,每一次都二分,这样效率就能提高。这时就用到三数取中法。
三数取中法指三个数里面取中间大小的数,然后将他与key交换位置,让这个中间大小的数作key。
完整代码如下:
int GetMidi(int* a, int begin, int end) { int midi = (begin + end) / 2; //begin end midi三个数中选中位数 if (a[begin] a[end]) return begin; else return end; } else { if (a[midi] > a[end]) return midi; else if (a[begin] = end) return; int midi = GetMidi(a, begin, end); Swap(&a[midi], &a[begin]); int left = begin, right = end; int keyi = begin; while (left = a[keyi]) { right--; } //左边找大 while (left分析:挖坑法其实跟hoare版本比没啥提升,只不过更易理解,本质上没变。但不同的版本,单趟排序后的结果可能会不同。
前后指针版本
分析:
- cur遇到比key大的值,cur++
- cur遇到比key小的值,++prev,交换prev和cur位置的值,++cur
代码实现
//前后指针法 int PartSort3(int* a, int begin, int end) { int midi = GetMidi(a, begin, end); Swap(&a[midi], &a[begin]); int keyi = begin; int prev = begin; int cur = prev + 1; while (cur a = NULL; pst->capacity = 0; pst->top = 0; //pst->top = -1; } void STDestroy(ST* pst) { free(pst->a); pst->a = NULL; pst->capacity = pst->top = 0; } //栈顶插入删除 void STPush(ST* pst, STDataType x) { assert(pst); if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; } STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; } bool STEmpty(ST* pst) { assert(pst); //if (pst->top == 0) //{ // return true; //} //else //{ // return false; //} return pst->top == 0; }非递归代码实现:
void QuickSortNonR(int* a, int begin, int end) { ST s; STInit(&s); STPush(&s, end); STPush(&s, begin); while (!STEmpty(&s)) { int left = STTop(&s); STPop(&s); int right = STTop(&s); STPop(&s); int keyi = PartSort3(a, left, right); // [left,keyi-1] keyi [keyi+1,right] if (keyi+1分析:栈是后进先出,这里用栈是模拟递归的过程。先模拟递归左边,像二叉树递归那样,先入右边的数,再入左边,这样出的时候就先出左边的,然后就可以模拟先往左边递归了。
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。
还没有评论,来说两句吧...