快速排序(quicksort)是分治法的典型例子，它的主要思想是将一个待排序的数组以数组的某一个元素X为轴，使这个轴的左侧元素都比X大，而右侧元 素都比X小(从大到小排序)。然后以这个X在变换后数组的位置i分为左右两个子数组，再分别进行快速排序，直到子数组中只有一个元素为止。
快速排序算法如下
其中partition函数将得到X所在的位置i（在这里总以数组的最后一个元素为轴）。
由于总是选择数组的最后一个元素做为轴，因此可能出现X的左边为n - 1或接近n - 1个元素，而右边没有元素，或元素很少的情况，即X最大或比较大。这样使quicksort将出现最坏的情况，也就是时间复杂度为 O(n^2)。因此partition可以采用随机方式得到轴X的位置i。 这样它的平均情况是非常好的（时间复杂度为 O(nlogn)），也就是说，最坏情况很难出现。
完整的代码如下
快速排序算法如下
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 i;
if (p < r)
{
i = partition(A, p, r);
quicksort(A, 0 , i - 1 );
quicksort(A, i + 1 , r);
}
}
其中partition函数将得到X所在的位置i（在这里总以数组的最后一个元素为轴）。
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 ;
}
{
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 ;
}
由于总是选择数组的最后一个元素做为轴，因此可能出现X的左边为n - 1或接近n - 1个元素，而右边没有元素，或元素很少的情况，即X最大或比较大。这样使quicksort将出现最坏的情况，也就是时间复杂度为 O(n^2)。因此partition可以采用随机方式得到轴X的位置i。 这样它的平均情况是非常好的（时间复杂度为 O(nlogn)），也就是说，最坏情况很难出现。
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);
}
{
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 ;
}
#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 ;
}
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/format,webp/resize,h_160,m_lfit)