一、快速排序

• 基本思想：通过一组排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据小，然后再按此方法对这部分数据分别进行快速排序，整个排序过程可以递归进行，以此使所有数据变成有序序列。
• 算法思想：基于分治策略
  • 分解：先从数列中取出一个元素作为基准元素。以此基准元素为标准，将序列分解为两个子序列，使小于或等于基准元素的子序列在左侧，大于等于基准子序列的在右侧
  • 治理：对两个子序列进行快速快速排序
  • 合并：将排好序的的两个子序列合并在一起
• 时间复杂度：n log n

二、AcWing模板

模板题：AcWing 785. 快速排序

//
// Created by zk on 2021/6/1.
//
#include <iostream>
using namespace std;

const int N = 1000010;
int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r){
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid);
    merge_sort(q, mid+1, r);

    int k = 0;
    int i = l;
    int j = mid + 1;
    while(i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k ++] = q[j++];

    while(i <= mid) tmp[k ++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(i=l, j=0; i<=r; i++, j++) q[i] = tmp[j];
}

int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &q[i]);

    merge_sort(q, 0, n-1);

    for(int i=0; i<n; i++) printf("%d ", q[i]);

    return 0;
}

三、趣学数据结构版

#include<iostream>
using namespace std;

int Partition(int r[],int low,int high)//划分函数
{
    int i=low,j=high,pivot=r[low];//基准元素
    while(i<j)
    {
        while(i<j&&r[j]>pivot) j--;//向左扫描
        if(i<j)
            swap(r[i++],r[j]);//r[i]和r[j]交换后i+1右移一位
        while(i<j&&r[i]<=pivot) i++;//向右扫描
        if(i<j)
            swap(r[i],r[j--]);//r[i]和r[j]交换 后j-1左移一位
    }
    return i;//返回最终划分完成后基准元素所在的位置
}

int Partition2(int r[],int low,int high)//划分函数
{
    int i=low,j=high,pivot=r[low];//基准元素
    while(i<j)
    {
        while(i<j&&r[j]>pivot) j--;//向左扫描
        while(i<j&&r[i]<=pivot) i++;//向右扫描
        if(i<j)
            swap(r[i++],r[j--]);//r[i]和r[j]交换
    }
    if(r[i]>pivot)
    {
        swap(r[i-1],r[low]);//r[i-1]和r[low]交换
        return i-1;//返回最终划分完成后基准元素所在的位置
    }
    swap(r[i],r[low]);//r[i]和r[low]交换
    return i;//返回最终划分完成后基准元素所在的位置
}

void QuickSort(int R[],int low,int high)//实现快排算法
{
    int mid;
    if(low<high)
    {
        mid=Partition(R,low,high); //基准位置
//        for(int i=low;i<=high;i++)
//          cout<<R[i]<<" ";
//        cout<<endl;
        QuickSort(R,low,mid-1);//左区间递归快排
        QuickSort(R,mid+1,high);//右区间递归快排
    }
}

int main()
{
    int a[100];
    int i,n;
    cout<<"请先输入要排序的数据的个数：";
    cin>>n;
    cout<<"请输入要排序的数据：";
    for(i=0;i<n;i++)
        cin>>a[i];
    cout<<endl;
    QuickSort(a,0,n-1);
    cout<<"排序后的序列为："<<endl;
    for(i=0;i<n;i++)
        cout<<a[i]<<" " ;
    cout<<endl;
    return 0;
}

四、陈越版

更加专业

1. 直接调用库函数

/* 快速排序 - 直接调用库函数 */

#include <stdlib.h>

/*---------------简单整数排序--------------------*/
int compare(const void *a, const void *b)
{ /* 比较两整数。非降序排列 */
    return (*(int*)a - *(int*)b);
}
/* 调用接口 */ 
qsort(A, N, sizeof(int), compare);
/*---------------简单整数排序--------------------*/


/*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/
struct Node {
    int key1, key2;
} A[MAXN];
 
int compare2keys(const void *a, const void *b)
{ /* 比较两种键值：按key1非升序排列；如果key1相等，则按key2非降序排列 */
    int k;
    if ( ((const struct Node*)a)->key1 < ((const struct Node*)b)->key1 )
        k = 1;
    else if ( ((const struct Node*)a)->key1 > ((const struct Node*)b)->key1 )
        k = -1;
    else { /* 如果key1相等 */
        if ( ((const struct Node*)a)->key2 < ((const struct Node*)b)->key2 )
            k = -1;
        else
            k = 1;
    }
    return k;
}
/* 调用接口 */ 
qsort(A, N, sizeof(struct Node), compare2keys);
/*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/

2. 自实现

/* 快速排序 */

ElementType Median3( ElementType A[], int Left, int Right )
{ 
    int Center = (Left+Right) / 2;
    if ( A[Left] > A[Center] )
        Swap( &A[Left], &A[Center] );
    if ( A[Left] > A[Right] )
        Swap( &A[Left], &A[Right] );
    if ( A[Center] > A[Right] )
        Swap( &A[Center], &A[Right] );
    /* 此时A[Left] <= A[Center] <= A[Right] */
    Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
    /* 只需要考虑A[Left+1] … A[Right-2] */
    return  A[Right-1];  /* 返回基准Pivot */
}

void Qsort( ElementType A[], int Left, int Right )
{ /* 核心递归函数 */ 
     int Pivot, Cutoff, Low, High;
      
     if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
          Pivot = Median3( A, Left, Right ); /* 选基准 */ 
          Low = Left; High = Right-1;
          while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
               while ( A[++Low] < Pivot ) ;
               while ( A[--High] > Pivot ) ;
               if ( Low < High ) Swap( &A[Low], &A[High] );
               else break;
          }
          Swap( &A[Low], &A[Right-1] );   /* 将基准换到正确的位置 */ 
          Qsort( A, Left, Low-1 );    /* 递归解决左边 */ 
          Qsort( A, Low+1, Right );   /* 递归解决右边 */  
     }
     else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */ 
}

void QuickSort( ElementType A[], int N )
{ /* 统一接口 */
     Qsort( A, 0, N-1 );
}

五、 可视化展示

1. Data Structure Visualization: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
   quick sort
   

   Data Structure Visualization.png

2. VisuAlgo: https://visualgo.net/zh
   quick sort
   

   VisuAlgo.png

3. algorithm-visualizer: https://algorithm-visualizer.org/
   Quicksort
   
   algorithm-visualizer.png