快速排序
1.基本思路
1）分解：将所需要排序的数组分为前后两部分，保证其中一部分元素均不大于另一部分的元素。
2）递归：通过递归使用快速排序，对子数组进行排序；
3）合并：合并子数组，组成原数组的一个排序。
伪代码：
quicksort（A，p，r）
if (p < r)
q = partition(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)
//分解数组，使得前部分不大于后一部分
partition(A,p,r)
x= A[r]
i =p - 1
for (j = p) to (r-1)
if (A[j] <= x)
i = i +_1
exchange (A[i], A[j])
exchange(A[i+1], A[x])
return i+1
C++代码：
//quicksort
// devide the array into two parts, the value of element in the pre-part is not
// greater than one's in post-part.
int partition(int* A, int p, int r)
{
int len = r - p;//the length of array
int x = A[r]; //utilize the A[r] as the comparer
int i = p - 1;
int temp(0);
for (int j = p; j < r ; ++j)
{
// if the value of element is below the comparer,change its position.
if (A[j] <= x)
{
i = i + 1;
//exhchange A[i],A[j];
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
//change A[r]'s position.
temp = A[i+1];
A[i+1] = A[r];
A[r] = temp;
return i + 1;
}
void quicksort(int* A, int p, int r)
{
if (p < r)
{
int q = partition(A, p, r);
quicksort(A, p, q - 1);
quicksort(A, q + 1, r);
}
}
int main()
{
int A[] = { 2,8,7,1,3,5,6,4 };
int p = 0;
int r = 7;
quicksort(A, p, r);
return 0;
}
