快速排序
程序员文章站
2022-05-23 11:08:15
...
快速排序 Quick Sort
是对起泡排序的一种改进。它的基本思路是,通过一趟排序将带排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对两部分记录继续进行排序,以达到整个序列有序。
如何将序列分成两个部分?
(1) 在序列中任取一个记录作为枢轴(支点 pivot)
(2) 重新排列其余记录
[1] 将所有比它小的记录都安置在它的位置之前,比它打的记录在它之后
[2] 由此,该枢轴记录最后所落在的位置i作为分界线,将序列分割两部分
快速排序的pivot选取是使得排序变快的关键。通常是首尾与中间元素三者取中值。
算法1 pivot选取
ElementType Median3(ElementType A[], int Left, int Right)
{
int Center = (Left + Right) / 2;
if ( A[Left] > A[Center] )
Swap( &A[Left], &A[Center] );
if ( A[Left] > A[Right] )
Swap( &A[Left], &A[Right] );
if ( A[Center] > A[Right] )
Swap( &A[Center], &A[Right] );
/* 经过三个判断处理 A[Left] <= A[Center] <= A[Right] */
Swap( &A[Center], &A[Right-1] ); /*将pivot藏在右边*/
/*只需要考虑 A[Left+1] 到 A[Right-2]*/
return A[Right-1]; /*返回pivot*/
}
算法2
void Quicksort( ElementType A[], int Left, int Right )
{
if (cuttoff < Right-Left)
{
pivot = Median3(A, Left, Right);
i = Left; j = Right-1;
for(; ;)
{
while( A[++i] < pivot ) {} // 从左往右找到首次比pivot大的值
while( A[--j] > pivot ) {} // 从右往左找到首次比pivot小的值
if ( i < j )
Swap( &A[i], &A[j] );
else
break;
}
Swap( &A[i], &A[Right-1] ); // 最后i所指向的位置存放pivot
Quicksort( A, Left, i-1 ); // 递归左边
Quicksort( A, i+1, Right ); // 递归右边
}
else
Insertion_Sort( A+Left, Right-Left+1 );
}
void Quick_Sort(ElementType A[], int N)
{
Qicksort(A, 0, N-1);
}