快速排序(quicksort)是分治法的典型例子，它的主要思想是將一個待排序的數(shù)組以數(shù)組的某一個元素X為軸，使這個軸的左側(cè)元素都比X大，而右側(cè)元
素都比X小(從大到小排序)。然后以這個X在變換后數(shù)組的位置i分為左右兩個子數(shù)組，再分別進行快速排序，直到子數(shù)組中只有一個元素為止。
快速排序算法如下
void quicksort(int A[], int p, int r)
{
int i;
if(p < r)
{
i = partition(A, p, r);
quicksort(A, 0, i - 1);
quicksort(A, i + 1, r);
}
}
其中partition函數(shù)將得到X所在的位置i（在這里總以數(shù)組的最后一個元素為軸）。
int partition(int A[], int p, int r)
{
int i = p - 1, j;
for(j = p; j < r; j++)
{
if(A[j] >= A[r])
{
i++;
swap(&A[i], &A[j]);
}
}
swap(&A[i + 1], &A[r]);
return i + 1;
}
由于總是選擇數(shù)組的最后一個元素做為軸，因此可能出現(xiàn)X的左邊為n - 1或接近n - 1個元素，而右邊沒有元素，或元素很少的情況，即X最大或比較大。這樣使quicksort將出現(xiàn)最壞的情況，也就是時間復(fù)雜度為
O(n^2)。因此partition可以采用隨機方式得到軸X的位置i。 這樣它的平均情況是非常好的（時間復(fù)雜度為
O(nlogn)），也就是說，最壞情況很難出現(xiàn)。
int new_random(int min, int max)
{
return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));
}
int randomize_partition(int A[], int p, int r)
{
int i = new_random(p, r);
swap(&A[i], &A[r]);
return partition(A, p, r);
}
完整的代碼如下
#include <stdio.h>
#include <stdlib.h>
void out_int_array(int data[], int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d ", data[i]);
}
printf("\n");
}
void swap(int *a, int *b)
{
int x;
x = *a;
*a = *b;
*b = x;
}
int new_random(int min, int max)
{
return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));
}
int partition(int A[], int p, int r)
{
int i = p - 1, j;
for(j = p; j < r; j++)
{
if(A[j] >= A[r])
{
i++;
swap(&A[i], &A[j]);
}
}
swap(&A[i + 1], &A[r]);
return i + 1;
}
void quicksort(int A[], int p, int r)
{
int i;
if(p < r)
{
i = partition(A, p, r);
quicksort(A, 0, i - 1);
quicksort(A, i + 1, r);
}
}
int randomize_partition(int A[], int p, int r)
{
int i = new_random(p, r);
swap(&A[i], &A[r]);
return partition(A, p, r);
}
void randomize_quicksort(int A[], int p, int r)
{
int i;
if(p < r)
{
i = randomize_partition(A, p, r);
quicksort(A, 0, i - 1);
quicksort(A, i + 1, r);
}
}
int main()
{
int A[] = {4, 1, 44, -12, 5, 125, 30};
int B[] = {4, 1, 44, -12, 5, 125, 30};
out_int_array(A, 7);
quicksort(A, 0, 6);
out_int_array(A, 7);
printf("--------------------------randomize-----------------------------\n");
srand((unsigned)time( NULL ));
randomize_quicksort(B, 0, 6);
out_int_array(B, 7);
return 0;
}
新浪微博：http://t.sina.com.cn/androidguy 昵稱：李寧_Lining