网站空间服务器费用,物联网设计大赛官网,手机做直播官方网站,wordpress迁移500快速排序的基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法
其基本思想为#xff1a;
任取待排序元素序列中的某元素作为基准值#xff0c;按照该排序码将待排序集合分割成两子序列#xff0c;左子序列中所有元素均小于基准值#xff0c;右序列中所…快速排序的基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法
其基本思想为
任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if(right - left 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div1, right)QuickSort(array, div1, right);
}
上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
划分区间的常见方式
将区间按照基准值划分为左右两半部分的常见方式有三种
hoare方法挖坑法前后指针法
三种方法是排key左右区间的不同整体快排的思想是递归
1.hoare方法 https://img-blog.csdnimg.cn/07ddcfdc56874b2a9d12f585534ac87e.gif#pic_center
1.1图示
定义left和right来找大和找小 right先走找大left再走找小找到交换 继续找大找小 相遇停下来和key交换 1.2为什么相遇位置一定比key小
这里我们有一个问题为什么相遇位置一定比key小
因为右边先走 相遇有两种情况 right遇left - left先走right没有遇到比key小的一直走直到遇到left停下来left存的是比key小的值left遇right - right先走left没有遇到比key大的一直走直到遇到right停下来right存的是比key大的值所以我们得出一个结论左边做key右边先走右边做key左边先走 如果左边有序右边也有序整体就有序了
那么如何让左右有序呢
类似二叉树递归左树和右树 第一遍排序后的left和right的范围是[begin,keyi-1]keyi[keyi1,end]
然后继续递归直到这个区间只有一个值或者不存在
1.3代码示例
//hoare方法
int PartSort1(int*a,int begin,int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;while (left right){//右边找小while (left right a[right] a[keyi]){--right;}//左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;return keyi;
}
2.挖坑法 https://img-blog.csdnimg.cn/c2dde0e21f32461fb43db524559ca36d.gif#pic_center
2.1图示 right找小left找大right先走找到小和坑位交换然后left走left找到大之后和坑位交换交替进行直到相遇 他们一定会相遇到坑的位置
相遇之后将key的值放到坑位中这时候key左边就是比key小的key右边就是比key大的 2.2代码示例
我们写一个挖坑法的函数来排keyi左右的数据
先用三数取中方法得到keyi定义一个key保存keyi的值定义一个坑位holei先放到begin
右边找小填到左边的坑里右边成为新的坑左边找大填到右边的坑里左边成为新的坑 相遇后将key放到坑里返回坑的下标
//挖坑法
int PartSort2(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int key a[begin];int holei begin;while (begin end){//右边找小while (begin end a[end] key)--end;a[holei] a[end];holei end;//左边找大while (begin end a[begin] key)begin;a[holei] a[begin];holei begin;}//相遇a[holei] key;return holei;
}
3.前后指针法 https://img-blog.csdnimg.cn/8baec430614e47dfa382926553830c14.gif#pic_center
3.1图示 prev要不就是紧跟cur要不prev和cur之间就是比key大的值
3.2代码示例
//前后指针法
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, cur begin 1;while (cur end){//if (a[cur] a[keyi])//{// prev;// Swap(a[prev], a[cur]);// cur;//}//else// cur;if (a[cur] a[keyi] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[keyi], a[prev]);keyi prev;return keyi;
}
4.快速排序优化
三数取中法选key 递归到小的子区间时可以考虑使用插入排序
4.1三数取中方法
这里我们的key默认取的是第一个数但是这种情况有个弊端不能保证key一定是那个中间值可能是最小的也可能是最大的
但是理想情况下key选中间值是效率最高的每次都是二分
这里就有一个方法能很好的解决这个问题三数取中
我们写一个取中函数将中间值与begin交换还是将key给到begin
int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else{if (a[midi] a[end])return midi;else if (a[end] a[begin])return begin;elsereturn end;}
}
三数取中可以排除掉最坏的情况相对而言可以提高效率
4.2小区间优化
如果是满二叉树最后一层占50%的节点倒数第二层占25%倒数第三层占12.5% 假设我们要对这五个数排序就需要调用六次递归这代价是非常大的 我们可以使用插入排序插入排序对局部的适应性是很好的所以我们在这个区间缩小的一定范围的时候就可以使用插入排序
一般选择最后三到四层因为最后三层就占据了将就90%的递归将最后三层的递归消除是能够明显提高效率的
剩下的区间不一定是从0开始的也有可能是后半段所以这里插入排序从begin开始 总代码
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
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--;}elsebreak;}a[end 1] tmp;}
}
int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else{if (a[midi] a[end])return midi;else if (a[end] a[begin])return begin;elsereturn end;}
}
//hoare方法
int PartSort1(int*a,int begin,int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;while (left right){//右边找小while (left right a[right] a[keyi]){--right;}//左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;return keyi;
}
//挖坑法
int PartSort2(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int key a[begin];int holei begin;while (begin end){//右边找小while (begin end a[end] key)--end;a[holei] a[end];holei end;//左边找大while (begin end a[begin] key)begin;a[holei] a[begin];holei begin;}//相遇a[holei] key;return holei;
}
//前后指针法
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, cur begin 1;while (cur end){//if (a[cur] a[keyi])//{// prev;// Swap(a[prev], a[cur]);// cur;//}//else// cur;if (a[cur] a[keyi] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[keyi], a[prev]);keyi prev;return keyi;
}
//快排
void QuickSort(int* a, int begin, int end)
{if (begin end)return;if (end - begin 1 10)InsertSort(a begin, end - begin 1);else{//hoare法//int keyi PratSort1(a, begin, end);//int keyi PartSort2(a, begin, end);int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}
}
int main()
{int a[] { 9,8,7,6,6,5,4,3,2,1,10,14,12,11,15 };int n sizeof(a) / sizeof(a[0]);QuickSort(a, 0, n - 1);for (int i 0; i n; i){printf(%d , a[i]);}return 0;
}
