快速排序基本思想
以 6 1 2 7 9 3 4 5 10 8 按從小到大排序 為例進(jìn)行說明：
- 以6為基準(zhǔn)，小于6的放在6的左邊轧钓，大于6的放在6的右邊序厉。
- 設(shè)置兩個(gè)標(biāo)志器i=0, j=9; i在數(shù)組的最左邊，j在數(shù)組的最右邊毕箍。
- j先動(dòng)脂矫，依次比較a[j]<6，如果不成立霉晕，j--; 如果成立則j停止庭再。如果j<i，停止牺堰。
- i再動(dòng)拄轻，依次比較a[i]>6, 如果不成立，i++伟葫；如果成立i停止恨搓。如果j<i，停止筏养。
- 如果i=j,就將6與a[j]進(jìn)行交換斧抱。
如此進(jìn)行一輪：等到的結(jié)果是
3 1 2 5 4 6 9 7 10 8
6 左邊的都小于6，6右邊的都大于6渐溶。
然后再排序 3 1 2 5 4
然后再排序 9 7 10 8
代碼實(shí)現(xiàn)
#include <stdio.h>
int a[100];
int n;
void quicksort(int left, int right)
{
if (left >= right) {
return;
}
int i, j;
i=left;
j=right;
int temp = a[left]; //基準(zhǔn)數(shù)據(jù)
while (i!=j) {
while (a[j]>=temp && j>i) {
j--;
}
while (a[i]<=temp && j>i) {
i++;
}
if (i<j) {
int k = a[i];
a[i] = a[j];
a[j] = k;
}
}
a[left] = a[i];
a[i] = temp;
quicksort(left, i-1);
quicksort(i+1, right);
return;
}
int main(int argc, const char * argv[]) {
// insert code here...
scanf("%d", &n);
for (int i=0; i<n; i++) {
scanf("%d", &a[i]);
}
quicksort(0, n-1);
for (int i=0; i<n; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
總結(jié)
快速排序之所以比較快辉浦，因?yàn)橄啾让芭菖判颍看谓粨Q都是跳躍式的茎辐。每次排序都設(shè)置一個(gè)基準(zhǔn)點(diǎn)宪郊，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放在基準(zhǔn)點(diǎn)的左邊掂恕，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放在基準(zhǔn)點(diǎn)的右邊。這樣在每次交換的時(shí)候就不會(huì)像冒泡排序一樣只能在相鄰的數(shù)之間進(jìn)行交換弛槐。交換的距離也大得多了懊亡。
