算法【排序】 | 快速排序 【荷兰问题】（附代码、图解）

一、简介

快速排序是通过冒泡排序算法改进而来的；

• 有多个版本：以下是最优的版本；

1.1 时间复杂度：

总时间复杂度：O(nlogn)；

1.2 空间复杂度：

空间复杂度：O(logn)；

二、过程

2.1 步骤

• 选取一个num与最右侧的数值进行交换，且该值作为区分；
• 当数值<num时，i和左区下一个进行交换，i++，L++；
• 当数值=num时，不移动，i++；
• 当数值>num时，i和右区前一个交换，i不变，R++；
• 后继续分区，递归重复相同动作；

2.2 图解

代码

/*----------------------------------------------------------------------
	> File Name: quickSort.cpp
	> Author: Jxiepc
	> Mail: Jxiepc
	> Created Time: Thu 27 Jan 2022 10:20:32 PM CST
----------------------------------------------------------------------*/
#include <iostream>
#include <ctime>
#include <vector>
#include <unistd.h>
#include <memory>

int arr[2] = {0, 0};

typedef std::vector<int> vec;

/** 交换函数 */
void swap(vec &vc , int L, int R) {
    int tmp = vc[L];
    vc[L] = vc[R];
    vc[R] = tmp;
}

/** 分层 */
void  partition(vec &vc, int L, int R) {
    arr[0] = L-1;
    arr[1] = R;
    while(L < arr[1]) {
        if(vc[L] < vc[R]) 
            swap(vc, ++arr[0], L++);
        else if(vc[L] > vc[R])
            swap(vc, --arr[1], L);
        else 
            L++;
    }
    swap(vc, arr[1], R);
} 

/** 快排主函数 */
void quickSort(vec &vc ,  int L, int R) {
    if(L < R) {
        swap(vc, L + (rand() % (R-L + 1)), R); 
        partition(vc, L, R);        
        quickSort(vc, L,  arr[0]);      
        quickSort(vc, arr[1] + 1, R);  
    }
}



int main(int argc, char* argv[])
{
    vec vc = {6, 2, 3, 4,1, 5};
    quickSort(vc, 0, 5);
    for(int i=0; i<6; ++i)
        std::cout << vc[i] << std::endl;
    return 0;
}