快速排序基本思想
以 6 1 2 7 9 3 4 5 10 8 按从小到大排序 为例进行说明：
- 以6为基准，小于6的放在6的左边，大于6的放在6的右边。
- 设置两个标志器i=0, j=9; i在数组的最左边，j在数组的最右边。
- j先动，依次比较a[j]<6，如果不成立，j--; 如果成立则j停止。如果j<i，停止。
- i再动，依次比较a[i]>6, 如果不成立，i++；如果成立i停止。如果j<i，停止。
- 如果i=j,就将6与a[j]进行交换。
如此进行一轮：等到的结果是
3 1 2 5 4 6 9 7 10 8
6 左边的都小于6，6右边的都大于6。
然后再排序 3 1 2 5 4
然后再排序 9 7 10 8
代码实现
#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]; //基准数据
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;
}
总结
快速排序之所以比较快，因为相比冒泡排序，每次交换都是跳跃式的。每次排序都设置一个基准点，将小于等于基准点的数全部放在基准点的左边，将大于等于基准点的数全部放在基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换。交换的距离也大得多了。
