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

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

🐼本篇内容简介F1a;一、排序算法-->二、问题呈现-->三、源码实现-->四、输出结果展示-->五、快速排序gif动画-->六、流程分析

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

一、快速排序算法

快速排序(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传给high
int partition(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 &amp;& a[low]<=key )//从左向右找比key大的值
            low++;
        if(low<high)
            a[high--] = a[low];
    }
    a[low] = key; //将循环后的得到的下一基准赋值给对应下标位置
    return low;  //返回下标位置后，快排函数进行递归
}
//快速排序函数
void Quick_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;
}
//主函数
int main() 
{
        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]);
        return 0;
}

---

四、输出结果展示

1.输出结果：

2 3 4 5 15 19 26 27 36 38 44 46 47 48 50
--------------------------------
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题练习专栏计划持续进行，欢迎评论交流学习！