快排 QuickSort

兩邊向中間掃描法：取一個基點(diǎn)值，從左往右掃描，基點(diǎn)值左邊所有元素小于它，遇到大于基點(diǎn)值的則停下，開始從右往左掃描，右邊所有元素大于他，遇到小于基點(diǎn)值則停下，如果這時(shí)左右指針不交叉（左指針在基點(diǎn)左邊，右指針在基點(diǎn)右邊），則交換兩個指針當(dāng)前值，在每一次交換后兩個指針均向右向左移動。依次遞歸則完成排序。

取中間值為基點(diǎn)，如果遞歸調(diào)用時(shí)將j換成i，那么x取值時(shí)需要向上取整，否則會造成邊界問題

建議讀者用不同的數(shù)組根據(jù)代碼邏輯模擬 方便理解

void QuickSort(int a[] , int l , int r){if ( l >= r ) return ;int i = l - 1, j = r + 1, x = a[l + r >> 1] ; //注意x的取值與下面的函數(shù)遞歸調(diào)用的參數(shù)有關(guān)while( i < j ){while( a[++i] < x );while( a[--j] > x );if( i < j ) swap(a[i] , a[j]);}QuickSort(a , l , j);QuickSort(a , j + 1 , r);
}

void QuickSort(int a[] , int l , int r){if ( l >= r ) return ;int i = l - 1, j = r + 1, x = a[l + r + 1 >> 1] ; //注意x的取值與下面的函數(shù)遞歸調(diào)用的參數(shù)有關(guān)while( i < j ){while( a[++i] < x );while( a[--j] > x );if( i < j ) swap(a[i] , a[j]);}QuickSort(a , l , i - 1);QuickSort(a , i , r);
}