快速排序(quick sort) C ~

快速排序性能好坏主要在于主元的选取。

下面有两种选主元的方式:

(1) : 每次选取当前序列的第一个元素

(2):选取选取当前序列的首元素、中间元素、尾元素的中位数.

核心：每次给主元找到准确的排序位置（效率高的原因也就在于每次找的的都是准确的位置）。

(1) 选取首元素为基准（主元）的实现：

#include<stdio.h>
int a[101];

void sort(int a[], int left, int right)
	{
		int i, j;
		int tmp;
		if(left > right)
			return ;
		tmp = a[left];
		i = left;
		j = right;
		int t;
		while(i != j){
			while(a[j] >= tmp && i < j)
				j--;
			while(a[i] <= tmp && i < j)
				i++;
			t = a[j];
			a[j] = a[i];
			a[i] = t;		
		}
		a[left] = a[j];
		a[j] = tmp;
		sort(a, left, j-1);
		sort(a, j+1, right);
	}
void quick_sort(int a[], int n)
	{
		sort(a, 0, n-1);		
	}	
	
int main()
	{
		int n, i;
		scanf("%d",&n);
		for(i = 0; i < n; i++ ){
			scanf("%d",&a[i]);
		}
		quick_sort(a, n);
		for(i = 0; i < n; i++ ){
			printf("%d ", a[i]);
		}
		return 0;
	}

（2）选取中位数为基准数据的实现:

#include<stdio.h>
#define MAX 100
void swap(int *a, int *b)
	{
		int tmp;
		tmp = *a;
		*a = *b;
		*b = tmp;
	}
int get_pivot(int a[], int left, int right) //选 主元  就是把 left, right , mid 按照从小到大排序 并把 中间值 返回当做主元
	{
		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[left], &a[mid]);
		return a[left];				
	}	
void sort(int a[], int left, int right)
	{
		if(left > right) //不能少 
			return ;
		int pivot = get_pivot(a, left, right);
		int i, j;
		i = left;
		j = right;
		
		while(i != j){
			while(a[j] >= pivot && i < j)//主语 这两个while语句的顺序 很重要 不能调换
				j--;
			while(a[i] <= pivot && i < j)// 主元选取在left 则每次必须是从right端 开始 查询 也就是 j先-- 找合适的
				i++;		     //然后在i++  (位置不可调换)
			if(i < j)	
				swap(&a[i], &a[j]);	
		}
		//出来时一定是 i == j 
		swap(&a[j], &a[left]); //找到 主元的合适位置
		sort(a, left, j-1);//递归 处理左半边
		sort(a, j+1, right);//递归处理右半边
		
		return ;		 
	}	
void quick_sort(int a[], int n)//提供 优雅的 接口
	{
		sort(a, 0, n-1);	
	}	
	
int main()
	{
		int a[MAX];
		int n, i;
		scanf("%d",&n);
		for(i = 0; i < n ; i++ ){
			scanf("%d",&a[i]);
		}
		quick_sort(a, n);
		for(i = 0; i < n; i++ ){
			printf("%d ",a[i]);
		}
		
		return 0;
	}