C语言100题练习计划—— 快速排序果然名副其实

C语言100题练习计划——快速排序果然名副其实

古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。——苏轼

🐼本篇内容简介：

一、排序算法-->二、问题呈现-->三、源码实现-->四、输出结果展示-->五、快速排序gif动画-->六、流程分析

🥇C语言100题练习专栏计划：

目的：巩固练习C语言，增强上机、动手实践能力，交流学习！前期尽量每天更新一题，之后题量随时间的增加会有所增加。文章内容也会不断打磨优化，争取做到好、然后更好！

C Programming Language

一、快速排序算法

快速排序(Quick sort)的介绍：

快速排序是对冒泡排序的一种改进。

1. 基本思想

将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一 部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直 到所有要进行排序的数据变为有序为止。

2. 平均时间复杂度

O( n * logn )

排序算法大多为O( n * n )。快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。 理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为记做O(n * logn)或(n*log2n)。

3. 优缺点

• 优点：效率高，(一个字形容来说就是)快！
• 缺点：不稳定，不适合对象排序;

4. 算法原理步骤

① 快速排序其实用到了分治思想(见注释)，将数列分解，然后排序。

分治思想： 字面意思就是说“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并 。

② 过程步骤：任取一个值作为基准，然后将小于该基准值的数放在该数的左侧，大于该数的数放在右侧。然后就是重复地将左侧与右侧持续进行该过程，直到将其分成两个数为一组，然后比较交换。这样，就实现了排序。

5. 简单示例

以

1、3、2、4、5

为例，简单地用作图工具演示一下:

二、问题呈现

Problem Description

给定数组元素为：

3,44,38,5,47,15,36,26,27,2,46,4,19,50,48

。使用快速排序对其进行升序排序。

Input

无

Output

数组元升序排序后的结果

Sample Input

无

Sample Output

2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

三、源码实现(+注释)

#include<stdio.h>//分治思想实现//快排函数中调用partition(a, start, end); //a作为参数传给a[],start传给low,end传给highintpartition(int a[],int low,int high){int key;
    key = a[low];//以第一个位置作为基准while(low<high){while(low <high && a[high]>= key )//从右向左找比key小的值
            high--;if(low<high)
            a[low++]= a[high];while( low<high && a[low]<=key )//从左向右找比key大的值
            low++;if(low<high)
            a[high--]= a[low];}
    a[low]= key;//将循环后的得到的下一基准赋值给对应下标位置return low;//返回下标位置后，快排函数进行递归}//快速排序函数voidQuick_sort(int a[],int start,int end){int pos;if(start<end){
        pos =partition(a, start, end);//找到下标位置Quick_sort(a,start,pos-1);//递归调用 左移Quick_sort(a,pos+1,end);//递归调用 右移}return;}//主函数intmain(){int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};int len =(int)sizeof(a)/sizeof(*a);//调用快速排序函数进行排序Quick_sort(a,0,len-1);int i;//循环输出排序后的结果：for(i =0; i < len; i++)printf("%d ", a[i]);return0;}

四、输出结果展示

1.输出结果：

23451519262736384446474850--------------------------------
Process exited after 0.2509 seconds with return value 0
请按任意键继续...

2.输出结果(图示版)：

五、快速排序gif动画：

六、流程分析

1.读题

给定数组元素为：3,44,38,5,47,15,36,26,27,2,46,4,19,50,48。使用快速排序对其进行升序排序。关键点 ①给定元素内容 ②快速排序 ③升序排序

2.构思

①根据第一个关键点给定元素内容，可以先定义一个整数类型的数组对其进行存储，方便后续使用循环对其进行操作。
②第二个关键点就是快速排序，使用快速排序，思想就是将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直到所有要进行排序的数据变为有序为止，如果感觉不好理解，其实可以先看一下分治思想(简要来说，就是分而治之)，然后再去理解快速排序思想，弄明白思想了，就好办多了。
③第三个关键点升序排序，任取一个值作为基准，然后将小于该基准值的数放在该数的左侧，大于该数的数放在右侧。然后就是重复地将左侧与右侧持续进行该过程，直到将其分成两个数为一组，然后比较交换。既然是小于、大于以及重复，肯定要用到while循环，if条件语句。 解决了这些，可以实现了。

3.编程

把你所思所想，以代码的形式，写出来。

ps：这道题的方法，本文虽然只写出这一种，但是思路方法其实不止这一种，其它的方法可自行尝试一下。

作者:Code_流苏（一个喜欢古诗词和编程的Coder😊）

★喜欢的话，还请多多点赞与关注！ 感谢支持！
C语言100题练习专栏计划持续进行，欢迎评论交流学习！