HzuQZH

用户名：h1810819001

访问量：32327

签　名：

等　　级
排　　名	45
经　　验	12277
参赛次数	7
文章发表	69
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

数据结构-KMP字符串模式匹配算法实现-题解(C++代码)
浏览：504

数据结构-用数组实现堆排（易处理，容易理解）
浏览：634

区间dp（动归思想）
浏览：938

你可能喜欢

数据结构-快速排序-题解(C++代码)

　　作者: HzuQZH　　　　发表时间：2019-10-31 17:34:31 浏览：811　|　评论：0　

原题链接：数据结构-快速排序

# 快速排序(Quicksort)算法
 	这个排序算法在面试题中基础遇到
 	虽然STL中有sort函数（自行了解）可以快速解决，

## 所以今天我们来了解一下快速排序算法。
快速排序算法的时间复杂度为：
	- 最优、平均O(nlogn)
	- 最差O(N^2^)

#### 快速排序算法的大致过程
	快速算法是基于递归实现，先确定一个基准数（假设取中间位置的数x=a[(l+r)/2]）。
	定义两个指针（i，j）i从头开始，j从尾开始。

![在这里插入图片描述](https://img-blog.csdnimg.cn/20191027170625105.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczODc2NA==,size_16,color_FFFFFF,t_70)
	
	当a[i]大于x时停止，当a[j]小于x时停止，判断当前i是否小于j，如果是就交换位置。
	以此类推，当i>=j时退出循环。

![在这里插入图片描述](https://img-blog.csdnimg.cn/20191027170701343.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczODc2NA==,size_16,color_FFFFFF,t_70)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20191027170727758.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczODc2NA==,size_16,color_FFFFFF,t_70)

此时的状态为
![在这里插入图片描述](https://img-blog.csdnimg.cn/20191027170833966.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczODc2NA==,size_16,color_FFFFFF,t_70)
	
	我们再分为两边进行递归处理，处理过程也是和上面一样。
	因为经过以上操作左、右两边区间的数虽然排序不同，但是他们所在的区间已经不会改变
![在这里插入图片描述](https://img-blog.csdnimg.cn/20191027170930479.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczODc2NA==,size_16,color_FFFFFF,t_70)

## 代码实现过程如下

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int a[N];
void quick_sort(int l,int r){
    if(l>=r)return ;
    int i=l-1,j=r+1,mid=a[(l+r)/2];//指定两个指针i，j，和基准数mid
    while(i<j){//这里如上所说的操作
        while(a[++i]<mid);
        while(a[--j]>mid);
        if(i<j)swap(a[i],a[j]);
    };
    quick_sort(l,j);//递归左边处理
    quick_sort(j+1,r);//递归右边处理
}
int main{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    quick_sort(0,n-1);
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

明明的随机数（C++代码）

The 3n + 1 problem （C语言代码）

矩形面积交（C语言代码）

【蟠桃记】（C语言代码）

数据结构-快速排序-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

简单的a+b （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

printf基础练习2 （C语言代码）

printf基础练习2 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

IP判断（C语言代码）

陈教主的三角形（C语言代码）

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

明明的随机数 （C++代码）

The 3n + 1 problem （C语言代码）

矩形面积交 （C语言代码）

【蟠桃记】 （C语言代码）

数据结构-快速排序-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

简单的a+b （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

printf基础练习2 （C语言代码）

printf基础练习2 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

IP判断 （C语言代码）

陈教主的三角形 （C语言代码）

明明的随机数（C++代码）

矩形面积交（C语言代码）

【蟠桃记】（C语言代码）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

C语言考试练习题_一元二次方程（C语言代码）

IP判断（C语言代码）

陈教主的三角形（C语言代码）