快速排序 C/C++

简介：

我们日常学习中排序有最简单的冒泡排序，虽然很方便就可以写出来，但是时间复杂度太大 对于一些题来说很容易超时；所以便可以用快速排序
快排例题链接；

快速排序（Quicksort）：

既然称之为快速排序 那么他就是排序算法里最快的一个算法；时间复杂度为O(NlogN)（平均运行时间）。最坏的情况和冒泡排序的时间复杂度一样为O(N^2)。
Quicksort 对冒泡排序算法的一种改进。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

话不多说 开始正题！！

快排思路：

1，任意从数组里取一个数定为基准数（不要想太多 就是拿一个数作为参照系 进行对比）；
2，分区，将比这个基准数大的数全放到它的右边，小于或等于它的数全放到它的左边；
3，分而治之，重复1，2步骤，直到整个数据变成有序序列；

知道了思路那我们就开始吧！！冲啊！！！！！

逻辑过程：

**1，**如一个这样的数组 num[n]；要对他进行排序；

num[0]=18;num[1]=20;num[3]=27num[4]=41;num[5]=5;num[6]=33;num[7]=15num[8]=17;

定义两个变量 起始位置为st 末尾为en；

**2，**取第一个数为基准位， 那么第一个位置就空了 也就是0号下标的位置 然后进行比较；

基准位 op=num[0]；
num[0]空了 然后从右往左找找到比18小的数 放到 0号位置；

**3,**开始查找~~~~
8号的 17 比“op”也就是基准位的数(18)小 就放到空的位置(0号位置)
num[0]=num[8]；

4.
8号位置为空：
在从1号位置往右找比 “op”基准位数（后面简称基准） 大的数；20比 基准位数“op“（18）大 ； 把20放到空的位置（8号）；
num[8]=num[1]；

5,
1号位置为空：
从七号位置往左找比基准小的数 15小于基准（18） 把15放到空的位置（1号）；
num[1]=num[7];

6，
7号位置为空：
从2号位置往右找比基准（18）大的数； 27（2号）大于基准（18）； 把27放到空的位置（7号）；
num[7]=num[2];

8，
2号位置为空：
从6号位置往左找比基准（18）小的数； 5（5号）小于基准（18）；把5放到空的位置（2号）；
num[2]=num[5];

9，
5号位置为空：
从3号位置往右找比基准（18）大的数； 19（3号）大于基准（18）;把19放到空的位置（5号）；
Num[5]=num[3];

10，
3号位置为空：
那么就剩一个4号位置了 从4号开始找一直到5号 发现没有比基准小的数了
循环结束；

最后把基准（18）填到最后一个空里（3号）：

num[3]=op(基准)；

11.
我们发现 经过一轮排序后 基准左边的数都比基准（18）小 基准右边的数都比基准（18）大！！
这时分区就完成了！！

12， 分开的每一个区都进行上述逻辑直到整个数据变成有序序列！！

接下来就是快排的第三个思想： 分而治之！！；
调用原函数继续分区 然后再治！直到整个数据变成有序序列！！*****

	quick(num,st,i-1); //左边的所有值在调用此函数进行排序
    quick(num,i+1,en); //右的所有值在调用此函数进行排序

没学程序语言也能看懂的代码（注释超多！）

###说那么多没用 再来一段保姆式代码！！！###

#include <iostream>

using namespace std; int num[1000]; void quick(int num[],int st,int en) {
    if(st>=en)//左端点大于右端点 排序结束
        return ;
    int i=st; //左右端点赋值给 i j 进行分治
    int j=en;
    int op=num[i];   //确定基准位；基准位这时便空了  方便于下面 @注释1找到的值填到这个位置；
                 // 确定第一个位基准位比较好理解 看个人喜好哪个都可以为基准的

    while(i<j) //一切都是左端点大于右端点下进行
    {
        while(i<j&&num[j]>=op)  //从右往左查找到比基准位小的数然后结束循环         @注释1
            j--;                 //同时  j--  一个一个查 不满足循环条件 结束循环  得到的 j 的值为比基准位小的数的下标
        num[i]=num[j];            // 把找到的数填到空的那个位置 同时下标为 j 的位置就空了方便于 @注释3的值填入  @注释2
        while(i<j&&num[i]<=op)	//从左往右查找到比基准位 大 的数然后结束循环
            i++ ;             // i++ 不满足循环条件 循环结束退出得到比基准位小的数的下标
        num[j]=num[i]; 		 // 把找到的数填到 @注释2 得到的空位置  @注释3
    }					//然后循环进行 把比基准位的大的值都放在了左边 小的放在了右边；

    num[i]=op;  //把基准位的值填到循环后剩下的那个空位；
                                             // 都看到这儿了 还不三连！！？？？？
    //分治 左边和右边在进行如上排序
    quick(num,st,i-1); //左边的所有值在调用此函数进行排序
    quick(num,i+1,en); //右的所有值在调用此函数进行排序


} int main() {
    int n;
    cin>>n;  //n代表有几个数
    for(int a=0; a<n; a++)
        cin>>num[a];//输入n个数；
    quick(num,0,n-1);//调用快排函数；
    for(int a=0; a<n; a++)
        cout<<num[a]<<" ";//输出结果；
    cout<<endl;
    return 0； }

~注释可能有点多 但为了让你懂我真的煞费苦心！！QAQ
那再来一段没有注释的！；

没有注释的快排代码~

#include <iostream>

using namespace std;
int num[1000];
void quick(int num[],int st,int en)
{
    if(st>=en)
        return ;
    int i=st;
    int j=en;
    int op=num[i];
   while(i<j)
        {while(i<j&&num[j]>=op)
            j--;
        num[i]=num[j];
        while(i<j&&num[i]<=op)
            i++;
        num[j]=num[i];
    }

    num[i]=op;

    quick(num,st,i-1);
    quick(num,i+1,en);


}
int main()
{
    int n;
    cin>>n;
    for(int a=0; a<n; a++)
        cin>>num[a];
    quick(num,0,n-1);
    for(int a=0; a<n; a++)
        cout<<num[a]<<" ";
    cout<<endl;
    return 0;
}

编译结果：

看到这里那说明你已经学会了 如果还是有不懂的地方可以私信我哦~~
欢迎各位网友指点 一起学习！！！！！
爆肝之作 实属不易 给个赞呗~ 谢谢各位兄弟姐妹！！