快速排序
快排屬于分治演算法
基本思想：當我們求解某些問題時，由于這些問題要處理的資料相當多，或求解程序相當復雜，使得直接求解法在時間上相當長，或者根本無法直接求出，對于這類問題，我們往往先把它分解成幾個子問題，找到求出這幾個子問題的解法后，再找到合適的方法，把它們組合成求整個問題的解法，如果這些子問題還較大，難以解決，可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止，這就是分治策略的基本思想，
總結下來即三步：
-
分成子問題
-
遞回處理子問題
-
子問題合并
快排的具體實作
-
確定分界點x，這里取 x = q[l + r >> 1]，
-
劃磁區間：我們將一堆數分為兩堆，左邊分為<=x的，右邊分為>=x，
-
遞回處理左右兩堆，
難點在于第2點，我們如何優雅而又簡單的劃磁區間，這里我們可以使用雙指標演算法（不需要開辟額外空間），
下面畫圖舉例：
具體代碼實作：
void quick_sort(int q[],int l,int r){
if(l>=r) return;//遞回的結束條件
int i = l - 1,j = r + 1,x = q[l + r >> 1];//這里 i = l - 1,j = r + 1,
//為什么要這樣,是因為下面的 ++i,--j，
// >> 1 <=> /2
// << 1 <=> *2
//(運算效率：移位 > 賦值 > 大小比較 > 加法 > 減法 > 乘法 > 取模 > 除法，)
while(i<j){
while(q[++ i]<x);//當前值<x，指標就繼續往右走，直到當前值>=x，
while(q[-- j]>x);//當前值>x，指標就繼續往左走，直到當前值<=x，
//交換兩個值 => 達到左邊都是小于x的值，右邊都是大于x的值，
//異或 ^ 騷操作（不使用額外變數）
if(i<j){
q[i] = q[i] ^ q[j];
q[j] = q[i] ^ q[j];
q[i] = q[i] ^ q[j];
}
}
//遞回處理（l，j) (j + 1, r)，
//邊界問題建議背過，
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/304786.html
標籤：其他
上一篇：pyspark dataframe資料連接（join）、轉化為pandas dataframe、基于多個欄位洗掉冗余資料
下一篇：【1】計算機網路概述