【算法浅析NO.00006】快速排序算法浅析 by arttnba3

原文:我的博客归档

0x00 绪论

众所周知，快速排序是所有的排序算法当中速度较快的一种，手撕快排也成为了每一位OIer的必备技能（实际上大部分人都会直接用STL的sort函数XD）
刚好今天ACM选修课布置的课后作业有一道题就是快排模板，所以作为一名不合格的OIer今天来简单讲讲什么是快速排序算法2333

0x01 基本概念

快速排序（Quick Sort），顾名思义就是很快的排序（大雾），是基于冒泡排序的一种改进的排序算法。

pre.冒泡排序（Bubble Sort）

没学过冒泡排序的可以简单地看一下，学过的直接跳过就行了
顾名思义，数据会“像泡泡一样一个一个冒出水面”，故得名冒泡排序
冒泡排序要对数组进行n-1趟遍历，故时间复杂度为O(N^2)
简单的冒泡排序代码如下：

void a3_sort(int * array, int n)
{
    
    int temp;
    for(int i=0;i<n-1;i++)
        for(int j=0;j<n-1-i;j++)
            if(array[j]>array[j+1])
            {
    
                temp = array[j];
                array[j] = array[j+1];
                array[j+1
1
2
3
4
5
6
7
8
9
10
11