Dotcpp  >  编程教程  >  排序算法  >  快速排序算法实例详解

快速排序算法实例详解

点击打开在线编译器,边学边练

1. 复杂度与稳定性

算法时间复杂度

最坏情况:O(n^2)

最好情况:O(nlogn)

平均情况:O(nlogn)

 

稳定性:不稳定排序

2. 过程介绍

快速排序是考察次数最多的排序,无论是在大学专业课的期末考试,还是在公司的面试测试题目中,快速排序都极大的被使用,在实际中快速排序也极大的被使用,如STL中的sort底层就是一个快速排序。

首先在数组中选择一个基准点,然后分别从数组的两端扫描数组,设两个指示标志(low指向起始位置,high指向末尾),首先从后半部分开始,如果发现有元素比该基准点的值小,就交换low和high位置的值,然后从前半部分开始扫描,发现有元素大于基准点的值,就交换low和high位置的值,如此往复循环,直到low>=high,然后把基准点的值放到high这个位置。一次排序就完成了。

以后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。

3.图示过程

可以看出,在第四躺时已经达到顺序,但是任还是会继续计算几趟直到完成全部运算

第一趟

70

50

30

20

10

70

40

60

第二趟

60

50

30

20

10

40

70

70

第三趟

40

50

30

20

10

60

70

70

第四趟

10

20

30

40

50

60

70

70

第五趟

10

20

30

40

50

60

70

70

4. 相关的代码

#include<iostream>
using namespace std;
 
void qucik_sort(int a[],int low,int high) {
    int i,j,temp;
    i=low;
    j=high;
    if(low<high) {
        temp=a[low];    //设置枢轴
        while(i!=j) {
            while(j>i&&a[j]>=temp) {
                --j;
            }
            if(i<j) {
                a[i]=a[j];
                ++i;
            }
 
            while(i<j&&a[i]<temp) {
                ++i;
            }
            if(i<j) {
                a[j]=a[i];
                --j;
            }
        }
        a[i]=temp;
        qucik_sort(a,low,i-1);
        qucik_sort(a,i+1,high);
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=8;
    qucik_sort(a,0,n-1);
    for(int i=0; i<n; i++) {
        cout<<a[i]<<' ';
    }
    return 0;
}



知识点标签:排序


本文固定URL:https://www.dotcpp.com/course/165

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数据结构教程
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 C++STL库教程(附带题库)
第六章 串、数组、矩阵和广义表
第七章 树
第八章 图
第九章 查找算法
第十章 排序算法
第十一章 算法和竞赛
第十二章 后记
Dotcpp在线编译      (登录可减少运行等待时间)