做网站选哪家好,高端网站建设与发展,建设酒店网站ppt模板,提高wordpress 权重今天我们继续来讲排序部分#xff0c;顾名思义#xff0c;快速排序是一种特别高效的排序方法#xff0c;在C语言中qsort函数#xff0c;底层便是用快排所实现的#xff0c;快排适用于各个项目中#xff0c;特别的实用#xff0c;下面我们就由浅入深的全面刨析快速排序。…今天我们继续来讲排序部分顾名思义快速排序是一种特别高效的排序方法在C语言中qsort函数底层便是用快排所实现的快排适用于各个项目中特别的实用下面我们就由浅入深的全面刨析快速排序。事先声明快速排序有不同的版本今天我们讲的是hoare的版本
目录
快排的定义
hoare快排的具体实现
快排的时间复杂度
优化快速排序
三数取中
小区间优化
相遇位置比key小的问题 快排的定义
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
hoare快排的具体实现
我们先看一下排序的动态图 快排的思想与其他的排序不同其他排序的基本思想是将最大或者最小的数找出来放到某一个位置而在快排中是将一个数排到有序的位置然后将其左右分割。
快排会有keyleftright三个变量key就是当前排序的数的下标left就是左端right就是右端
我们先看一下单趟排序的逻辑
注意左右寻找比key位置大或小的数时必须从key的另一侧开始移动不然会出现排序错误的问题这个问题我们之后会具体讲到 那么我们用代码实现一下单趟排序的逻辑
void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
void quicksort(int a[],int left,int right)
{int key left;//我们假设key位于left的位置int begin left;int end right; //用begin和end记录left和right的位置//我们之后要用left和right的值,进行分割区间递归所以不能改变其值while (begin end){//右边找小while (beginenda[end] a[key]){end--;}//左边找大while (beginenda[begin] a[key]){begin;}swap(a[begin], a[end]);}swap(a[begin], a[key]);
}
既然单趟排序的逻辑我们已经清楚了那么我们下一步就该进行多次单趟排序的逻辑这样我们就能完成快排的逻辑
我们这里先用递归的思想进行实现看下面的逻辑图 以上便是快排多次进行单词排序的逻辑即快速排序的全部实现逻辑
下面我们用代码进行实现
void quicksort(int a[],int left,int right)
{if (left right){return;}int key left;//我们假设key位于left的位置int begin left;int end right; //用begin和end记录left和right的位置//我们之后要用left和right的值,进行分割区间递归所以不能改变其值while (begin end){//右边找小while (beginenda[end] a[key]){end--;}//左边找大while (beginenda[begin] a[key]){begin;}swap(a[begin], a[end]);}swap(a[begin], a[key]);key begin;//[left,key-1] key [key1,right]quicksort(a, left, key - 1);//左区间递归排序quicksort(a, key1, right);//右区间递归排序
}
这里我们还要理解一下递归终止条件
即left right 以上即快速排序的基本实现
快排的时间复杂度
我们都知道判断一个排序效率的方法就是比较其时间复杂度
那么快排的时间复杂度是多少呢
如果从代码的角度看这个时间复杂度是非常难以计算的
我们先来看快排的递归层数我们根据上面的逻辑图可以大致的发现快排是将数组类似分为二叉树的结构
因此递归的层数为logN层而在单趟排序中end和begin从两边开始走直到相遇一共走了N步
从这个角度看快排的时间复杂度为 O(NlogN)
因此快排是和堆排序希尔排序位于同一赛道的排序算法都是极其高效的算法
排序十万个数单位毫秒ms 排序一百万个数 单位毫秒ms 排序五百万个数 单位毫秒ms 可以看到当前的快排并没有想象中那么快甚至在数多的情况下和堆排序以及希尔排序还显得效率较低。 而且在排有序数组的情况下不要说一百万个数在十万个数有序数组中会发生一个大问题
1效率变低 2.由于递归层次太深每次递归都要建立新的栈帧这就会可能导致栈溢出的问题 我们来分析一下问题之前在正常情况下时间复杂度为N*logN的前提是每次都是二分递归即key位置的数都是接近中间的值此时当二分递归时递归的深度就是logN但如果按上面有序情况下递归的深度是N这就是上面问题的来源
因此我们现在的快排还是有明显的缺陷
优化快速排序
那么我们如何解决这个问题呢
避免有序情况下效率退化
我们可以改变key的选取如果我们每次都选取最左侧值为key或者最右侧值为key就会导致上面递归过深的问题所以我们不能固定选key。
1.随机选key
随机数选key虽然能够解决问题但是还是有些不靠谱毕竟是随机的
2.三数取中
最左边最右边中间选取不是最大的和最小的作key
为了保证代码的逻辑不发生变化即还从最左端的为key我们就将三数取中的值与最左边的值进行交换再执行代码逻辑。
三数取中
三数取中是取大小是中间的值然后完成最好的情况就是二分的情况即效率最高的情况
运用分支语句进行两两比较返回中间值直接放代码逻辑比较简单不作解释
int GetMid(int* a, int left, int right)
{int mid (left right) / 2;//left mid rightif (a[mid] a[left]){if (a[mid] a[right])return mid;else if (a[left] a[right])return left;elsereturn right;}else{if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn right;}
}
那么我们的快排中需要将交换left和三数取中mid的位置即加上两行代码我们其他的逻辑不发生变化
代码如下
void quicksort(int a[],int left,int right)
{if (left right){return;}//三数取中int mid GetMid(a, left, right);swap(a[mid], a[left]); int key left;//我们假设key位于left的位置int begin left;int end right; //用begin和end记录left和right的位置//我们之后要用left和right的值,进行分割区间递归所以不能改变其值while (begin end){//右边找小while (beginenda[end] a[key]){end--;}//左边找大while (beginenda[begin] a[key]){begin;}swap(a[begin], a[end]);}swap(a[begin], a[key]);key begin;//[left,key-1] key [key1,right]quicksort(a, left, key - 1);quicksort(a, key1, right);}
在优化后我们再来比较一下快排的效率 可以发现在三数取中后快排效率也有了优化而且避免了在有序情况下递归过深的问题
小区间优化
我们的快排虽然有了优化但是还有一点缺陷描述如下图所示 而我们小区间优化只需要加一个判断语句对数据个数进行判断若小于10就用其他的排序方法大于10就正常递归排序
那么我们选用其他的排序方法要用哪个比较好呢
我们有插入堆排序选择冒泡希尔排序归并排序
我们可以一一进行比较与排除
希尔排序不适用于小数据的排序堆排序虽然可以但是我们想一下没有必要为10个数再单独进行建堆不然就得不偿失了归并也是利用递归没有必要。
那么我们就剩下了冒泡选择插入
而在之前的文章中我们分析过冒泡和选择排序是远远不如插入排序的效率的
那么我们就选择插入排序
在快排的底层中小区间优化也是使用的插入排序这就是插入排序的实际应用
代码如下 //小区间优化,不再递归分割排序减少递归次数if ((right - left 1) 10){InsertSort(a left, right - left - 1);}
以上便是优化快排的全部实现
下面放上优化过快排代码
int GetMid(int* a, int left, int right)
{int mid (left right) / 2;//left mid rightif (a[mid] a[left]){if (a[mid] a[right])return mid;else if (a[left] a[right])return left;elsereturn right;}else{if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn right;}
}
void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
void quicksort(int a[],int left,int right)
{if (left right){return;}//小区间优化,不再递归分割排序减少递归次数if ((right - left 1) 10){InsertSort(a left, right - left - 1);}else{//三数取中int mid GetMid(a, left, right);swap(a[mid], a[left]); int key left;//我们假设key位于left的位置int begin left;int end right; //用begin和end记录left和right的位置//我们之后要用left和right的值,进行分割区间递归所以不能改变其值while (begin end){ //右边找小while (beginenda[end] a[key]){end--;}//左边找大while (beginenda[begin] a[key]){begin;}swap(a[begin], a[end]);}swap(a[begin], a[key]);key begin;//[left,key-1] key [key1,right]quicksort(a, left, key - 1);quicksort(a, key1, right);}
}
int main()
{int a[] { 6,1,2,7,9,3,4,5,10,8 };int sz sizeof(a) / sizeof(a[0]);quicksort(a, 0, sz - 1);for (int i 0; i sz - 1; i){printf(%d , a[i]);}return 0;
}
相遇位置比key小的问题
之前我们遗留了一个小问题就是怎么保证eft和right相遇位置的值一定比key位置小这样交换后会让key的左右两边分为比key大的和比key小的如果相遇位置比key要大的话那就让数据排序毁了。
那么如何保证相遇位置比key小呢
先说结论就是我们上面所说的
当左边作key时就让右边先走可以保证相遇位置比key小
以下即解释 以上是便是hoare排序相关问题
