学步园

快速排序是一种排序方法，使用快速排序对n个数字进行排序，在最坏情况下对运算时间为O(n*n)。但是由于平均情况下，运算时间比较低为O(nlgn)，并且可以实现就地排序，所以 快速排序是经常用到的比较实用的排序方法。

快速排序使用分治的方法进行排序。对于长度为n的数组A[]，快速排序依据数组元素的大小，把小于A[n-1]和大于A[n-1]的部分分为两部分分别排序。采用递归的方法完成排序。其过程如下：

quick_sort(int a[], int p, int r)

if p < r

        then 

            q = partition(a,p,r)

            quick_sort(a,p,q-1)

            quick_sort(a,q+1,r)

其中partition（即分组）的过程如下：

partition(int a[],int p, int r)

       i = p-1,x = a[r]

       for j=p---->r

              if a[j] <= a[r]

              then 

                    i++

                    swap(a[j],a[i])

      swap(a[i+1],a[r])

      return i+1;

C代码如下：

#include <stdio.h>


void swap(int * x,int * y)
{
	int temp;
	temp = *x;
	*x = *y;
	*y = temp;
}

int partition(int a[],int p,int r)
{
	int i = 0,j = 0;
	i = p-1;
	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;
}
/*-------------------------------*/
/* Fun:快速排序 */
/* param: a[] (i/o) array to sort*/
/* param: p (i) first index of a[]*/
/* param: r (i) last index of a[]*/
void quick_sort(int a[],int p,int r)
{
	if(p<r)
	{
		int q = partition(a,p,r);
		quick_sort(a,p,q-1);
		quick_sort(a,q+1,r);
	}
}

void output(int a[],int length)
{
	int i = 0;
	for(i = 0; i < length; i++)
	{
		printf("%d\t",a[i]);
	}
}

int main()
{
	int a[] = {3,5,8,3,1,6,9,3,5};
	quick_sort(a,0,sizeof(a)/sizeof(a[0])-1);
	output(a,sizeof(a)/sizeof(a[0]));
}