当前位置: 首页> 汽车> 行情 > 快速排序

快速排序

时间:2025/7/10 9:35:22来源:https://blog.csdn.net/lihaolihao111111/article/details/140840573 浏览次数: 2次

原理

设置一个关键值,一个左值,一个右边的值,分别向右边和左边遍历,左边的找比key大的,右边的找比key小的,找到后交换两个的值,直到左和右边相遇,交换key和a[左]值,然后一直递归下去 

代码实现

void QuickSort(int* a, int left,int right)
{if (right - left < 1){return;}int begin = left, end = right;int keyi = left;while (left < right){//为什么先走right,因为keyi在左边,极端情况下,right可能//一直走到头while (right > left && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}}

时间复杂度

由于每次都是要把一个序列分成两个部分,每一个序列都要操作N次(每一次虽然都会减少),所以一般情况下的时间复杂度为O(n*logN)

但是,我们所说的时间复杂都是在最坏的情况下,当序列有序的情况下,左边的区间没有,所以这里的时间复杂度为O(N^2)

代码改进

为了应对上面的序列有序的情况,我们有以下的两种改进

随机数

在序列中随机选出一个数作为该序列中的最左值

void QuickSort(int* a, int left,int right)
{if (right - left < 1){return;}int i = rand() % (right - left);i = i + left;Swap(&a[i], &a[left]);int begin = left, end = right;int keyi = left;while (left < right){//为什么先走right,因为keyi在左边,极端情况下,right可能//一直走到头while (right > left && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}}

中位数法

选出一个中位数,作为序列的左值

int GetMid(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[mid] > a[left]){if (a[mid] < a[right]){return mid;}else //a[mid]>a[right]{if (a[right] > a[left]){return right;}else{return left;}}}else //a[mid]<a[left]{if (a[mid] > a[right]){return mid;}else if(a[left]<a[right]){return left;}else{return right;}}
}void QuickSort(int* a, int left,int right)
{if (right - left < 1){return;}int mid = GetMid(a, left, right);Swap(&a[mid], &a[left])int begin = left, end = right;int keyi = left;while (left < right){//为什么先走right,因为keyi在左边,极端情况下,right可能//一直走到头while (right > left && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}}

快速排序—前后指针法

void QuickSort1(int* a, int left, int right)
{if (right <=left){return;}int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi]){prev++;Swap(&a[prev], &a[cur]);cur++;}else{cur++;}}Swap(&a[prev], &a[keyi]);keyi = prev;QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);
}

快速排序-非递归

这里主要运用的是数据结构的栈,先插入左右区间,进行单趟排序,再插入子区间,如此循环

void QuickSort2(int* a, int left, int right)
{SL sl;SLinit(&sl);SLpush(&sl, right);SLpush(&sl, left);while (!SLempty(&sl)){int begin = SLtop(&sl);SLpop(&sl);int end = SLtop(&sl);SLpop(&sl);//单趟排序int keyi = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[keyi]){prev++;Swap(&a[prev], &a[cur]);cur++;}else{cur++;}}Swap(&a[prev], &a[keyi]);keyi = prev;if (keyi + 1 < end){SLpush(&sl, end);SLpush(&sl, keyi + 1);}if (keyi - 1 > begin){SLpush(&sl, keyi - 1);SLpush(&sl, begin);}}SLdestory(&sl);
}

关键字:快速排序

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: