欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序

程序员文章站 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);
}