快速排序-C语言版（带图详细）
温馨提示：
本文最后更新于 2021年09月04日，已超过 965 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。
前言
哈喽，大家好，我最近在复习数据结构中的排序算法章节，今天复习到了交换排序算法中的快速排序算法，所以给大家分享一下。
一、什么是快速排序？
快速排序算法是在几种排序算法中效率最高的一个排序算法了，故称为快速排序，它的时间复杂度为：O(nlog~2~n)，相比冒泡排序算法的O(n^2^)有很大的提升。
二、算法思想
1、选取一个基准元素（一般我们将待排序序列中的第一个元素选取为基准元素）
2、将其他元素与基准元素进行比较，比基准元素大的放到基准元素的右边，比基准元素小的放到基准元素的右边。（以基准元素为中心将元素重新分成两个序列，并返回基准元素的下标）
3、将新生成的两个序列继续执行1和2两步（此处可以用递归实现）
接下来我们通过一个动图来看一下快速排序算法。
三、实例讲解
我们有一个待排序序列是：【 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】
①选取第一个元素44为基准坐标。
②以44为中心，将序列分为两部分，左边比44小，右边比44大。
③原来的序列被分成两部分，一部分比44小的是【0，基准坐标-1】，另一部分比44大的是【基准坐标+1，最后】，将这两部分继续执行①和②两步最终即可排序完成。
第一轮排序总结： 算法思想其实不难理解，那么接下来需要解决的问题就是，如何将一个序列以基准坐标分成相对有序的两部分，以及递归出口问题。
四、算法分析
1.时间复杂度
O(nlog~2~n)
2.空间复杂度
空间复杂度由于需要开辟一个临时空间来存储基准坐标所以是：O(1)
五、代码实现
#include<stdio.h>
void Print(int array[],int len){
for(int i=0;i<len;i++){
printf("%d ",array[i]);
}
printf("\n");
}
/*获取基准坐标，并相对有序（左边比基准坐标小，右边比基准坐标大）*/
int getStandard(int array[],int low,int high) {
int key = array[low]; //临时保存基准元素
while(low<high) {
//high指针从后向前遍历 ， 元素比基准元素大则指针向前移动 则比基准元素小则和基准元素交换
while(low<high && array[high]>=key){
high--;
}
if(low<high){
array[low] = array[high]; //赋值给第一个元素，因为第一个元素作为基准元素已经临时保存了，所可以直接赋值
}
//low指针从前向后遍历 ， 元素比基准元素小则指针向后移动 否则比基准元素大则和基准元素交换
while(low<high && array[low]<=key){
low++;
}
if(low<high){
array[high] = array[low]; //复制给high指针所指得位置，因为在11行已经赋值给array[low]了
}
}
array[low] = key;
return low;
}
void QuickSort(int array[],int low,int high){
if(low<high){ //递归出口
int standard = getStandard(array,low,high);
QuickSort(array,low,standard-1); //比基准元素小的部分继续调用快速排序
QuickSort(array,standard+1,high); //比基准元素大的部分继续调用快速排序
}
}
int main(){
int array[] = {3, 44, 38, 5, 47, 15, 36};
int size = sizeof(array) / sizeof(int);
printf("原始序列为：\n");
Print(array,size);
QuickSort(array,0,size-1);
printf("排序后序列为：\n");
Print(array,size);
}
六、运行结果
总结
最后，我们只需要记住快速排序的算法思想（两步）以及如何通过两个指针来实现将待排序序列分成两部分即可。
正文到此结束
- 本文标签： c语言 算法 排序
- 本文链接： https://www.it1997.com/article/52
- 版权声明： 本文由小陈没烦恼原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
相关文章
热门推荐
近期评论
-
来自： 好用的截图工具FastStone Capture 带激活码）
-
来自： 留言板
-
来自： 留言板
-
来自： 留言板
-
来自： 留言板