首页 > 代码库 > [整理]快速排序

[整理]快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

/*Function:       quicksortDescription:   快速排序Calls:              swapInput:             	--v:数组	--left:数组下标	--rigt:数组下标Return:			  voidOthers:         */  void quicksort(int v[],int left,int right){		void swap(int v[],int i,int j);	if(left<right){		int i=left,j;		int x=v[i];/*第一个元素作为基准元素*/		for (j=i+1;j<=right;j++)/*从第二个元素开始从左向右依次和基准元素比较,小的元素和已比较过的大的元素相互交换位置*/		{			if(v[j]<x&&i!=j){				i++;				swap(v,i,j);			}		}		swap(v,left,i);/*基准元素和最后一个比较过的小的元素交换位置,至此,小的元素在基准元素左边,大的元素在其右边*/		quicksort(v,left,i-1);/*对小的元素区间继续重复上面步骤*/		quicksort(v,i+1,right);/*对大的元素区间继续重复上面步骤*/	}}void swap(int v[],int i,int j){	int temp=v[i];	v[i]=v[j];	v[j]=temp;}
#include <stdio.h>int main(void){   	void quicksort(int v[]);	int v[]= { 70, 30, 40, 60, 10, 20, 50, 100, 80, 90 };	int length=sizeof(v)/sizeof(int);	int i;	quicksort(v,0,length-1);	for (i=0;i<length;i++)	{		printf("%d\n",v[i]);	}	return 0;}

 

参考:

快速排序算法