浙江大学数据结构 快速排序 C语言_浙大版c语言程序设计排序

一 算法概述

快速排序的核心思想是 分而治之

其思路就是在一堆元素中选取一个主元（pivot），将元素中小于主元的划为一个子集， 大于主元的划为另一个子集，递归地再将两个子集进行划分，直到最后划分的子集中只有一个元素，就完成了排序。

那么快速排序就分成了两个核心问题，一是对于主元的选取，二是对于子集的划分。

二 主元的选取

对于主元的选取，一个很自然的想法是，每次都选取集合中的第一个元素，但如果待排数组本身就是从小到大的（或者已经是高度有序的），那么每次都只能划分出大于主元的一个子集，这样的时间复杂度就会达到O(n^2)，是非常慢的。

当然，我们为了避免这种情况的发生，也可以利用随机函数在数组中随机取出一个值作为主元，但每次集合的划分都调用一次随机函数也势必会造成时间的浪费。

如果选取主元是能使集合恰好等分的元素，可以时算法的时间复杂度达到最快O(nlogn)（数量为n的数组进行logn次划分，而每次划分都要用线性时间复杂度O(n)的算法分出两个子集）

所以我们可以在数组中选取某几个位置的数，取出他们的中位数，这样就可以得到一个比较靠近中位数的主元。

例如，我们可以选取头中尾三个位置的数，取其中位数。

int median3(int a[], int left, int right)
{
	int mid = (left + right) / 2;
	
	if(a[left] > a[mid])
		swap(&a[left], &a[mid]);
	if(a[left] > a[right])
		swap(&a[left], &a[right]);
	if(a[mid] > a[right])
		swap(&a[mid], &a[right]);
		
	swap(&a[mid], &a[right - 1]);
	return a[right - 1];
}

在上面的代码中，我们用三个if语句将a[left]，a[mid]，a[right]，中的元素从大到小排列，这还没有完，我们又接着交换了a[mid]与a[right-1]（倒数第二个元素）的位置，这是为了便于我们接下来对子集进行划分。

三 子集的划分

对于子集的划分，我们可以采用两个指针 i , j ，一个从头开始向后走，一个从尾开始向前走，当头指针碰到大于pivot的元素会停止，这时尾指针向前直到碰到小于pivot的元素，然后交换两个指针指向的元素，重复这样的操作直到指针 i > j，这时我们就可以把 i 位置元素与pivot交换，就完成了一次子集划分，即pivot前的元素都小于pivot，后面的都大于pivot。

因为在media3函数中，我们已经将头和尾放入了小于pivot和大于pivot的元素，又将pivot放到了right - 1的位置所以在划分子集时就可以从left + 1和right - 2位置开始。 

这时我们就可以明白为什么要把pivot移到right - 2这个位置：将pivot剥离出来方便 i 和 j 进行移动。当然，我们也可以将pivot移到left + 1这个位置，这样最后pivot就应该放到 j 的位置上，i 和 j 的初始值也要改变。

#include <stdio.h>
#include <stdlib.h>
 
void swap(int* a, int* b)
{
	int t = *a;
	*a = *b;
	*b = t;
}
 
int median3(int a[], int left, int right)
{
	int mid = (left + right) / 2;
	
	if(a[left] > a[mid])
		swap(&a[left], &a[mid]);
	if(a[left] > a[right])
		swap(&a[left], &a[right]);
	if(a[mid] > a[right])
		swap(&a[mid], &a[right]);
		
	swap(&a[mid], &a[right - 1]);
//	swap(&a[mid], &a[left + 1]);
	return a[right - 1];
//	return a[left + 1];
}
 
void quicksort(int a[], int left, int right)
{
	if(left < right)
	{
		int pivot = median3(a, left, right);
		int i = left;
//		int i = left + 1;
		int j = right - 1;
//		int j = right;
 
		while(1)
		{
			while(i < right - 1 && a[++i] < pivot);
//			while(i < right - 1 && a[++i] <= pivot);
			while(j > 0 && a[--j] > pivot);
//			while(j > 0 && a[--j] >= pivot)
			if(i < j)
				swap(&a[i], &a[j]);
			else
				break;			
		}
		swap(&a[i], &a[right - 1]);
//		swap(&a[j], &a[left + 1]);
		
		quicksort(a, left, i - 1);
//		quicksort(a, left, j - 1);
		quicksort(a, i + 1, right);
//		quicksort(a, j + 1, right);
	}
}
 
void quick_sort(int a[], int n)
{
	quicksort(a, 0, n - 1);
}
 
int main()
{
	int a[] = {3,2,1,5,6,4};
	quick_sort(a, sizeof(a) / sizeof(int));
	for(int i = 0; i < sizeof(a) / sizeof(int); i++)
		printf("%d ", a[i]);
	printf("\n");
	
	return 0;
}

需要注意的一点：如果pivot的位置为数组中的第一个元素，在进入while循环之后一定要限定 j 大于零(j = right - 1 = 0, --j = -1)不然会发生数组越界，同时要保证 i 不能越过主元，要是主要与他后面的元素交换了位置就可能出错。

参考数组1，2，数组中只有两个元素left = 0, right = 1，经过median3函数后，数组仍为1，2，pivot = 1，i = 0， j = 0，进入while循环之后，i 会越过pivot指到 2，而 j 会变成 -1，这时我们教会元素就会发生数组越界，所以要限定 j > 0，但是这样还不够，交换之后数组就会变成2，1所以要限定 i < right - 1。（课件中的代码因为在元素数量足够小是使用了简单排序，所以没有这个问题）。

还有一个很重要的问题：如果元素等于pivot要不要做交换，我们可以考虑极端情况，即数组中所有元素都等于pivot。

1.不做交换即while(a[++i] <= pivot && i < right - 1) ，这样做的好处是在极端情况下减少了交换次数，坏处是由于没有交换 i 会一直后移到pivot之前，会形成主元选取中的第一种选取的情况，只产生一个小于pivot的子集，使得时间复杂度达到了O(n^2)。

2.做交换，交换的缺点显而易见，会在极端情况下从头交换到尾，但相较于不做交换，它有很大的优势就是在极端情况下可以使pivot最后位于一个中间位置，提高了排列效率。

综合上述我们一般要做交换，while循环中的条件设置为nums[i] < pivot，nums[j] > pivot。