快速排序的基本思想是，对于输入的子数组a[p:r]，进行
(1)分解(Divide):以a[p]为基准元素将a[p:r]划分为三段a[p:q-1],a[q]和a[q+1:r].是a[p:q-1]中任何一个元素小于等于a[q],而a[q+1:r]中任何一个元素大于a[q].下表q在划分过程中确定.
(2)递归(Conquer):通过递归调用快速排序算法分别对a[p:q-1]和a[q+1,r]进行排序.
(3)合并(Merge):由于对a[p:q-1]和a[q+1:r]的排序是就地进行的,所以在a[p:q-1]和a[q+1:r]都已排好序后,不需要执行任何计算,a[p:r]就已排好序.
#include "iostream.h"
void QuickSort(int a[], int p, int r);
int Partition(int a[], int p, int r);
void print(int a[], int length);
int main(){
int a[] = {3, 5, 8, 2, 4, 7, 1};
print(a, 7);
QuickSort(a, 0, 6);
print(a, 7);
return 0;
}
void QuickSort(int a[], int p, int r)
{
if(p < r){
int q = Partition(a, p, r);
print(a, 7);
QuickSort(a, p, q-1);
print(a, 7);
QuickSort(a, q+1, r);
print(a, 7);
}
}
int Partition(int a[], int p, int r)
{
int i = p, j = r + 1;
int x = a[p];
while(true){
while(a[++i] < x && i < r);
while(a[--j] > x);
if(i >= j)
break;
//Swap(a[i], a[j]);
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
a[p] = a[j];
a[j] = x;
return j;
}
void print(int a[], int length)
{
for(int i = 0; i < length; i++){
cout << a[i] << ", ";
}
cout << endl;
}
|
