十大经典排序算法之快速排序

十大经典排序算法之快速排序

近些日子突然想回顾下十大经典排序算法，于是就找空余时间用c语言实现一下，就当是回顾和复习了，今天我们就来讲讲快速排序算法

      快速排序算法是十大经典排序算法其中的一个，其思想主要就是将一组没有顺序的数字，首先在这组数字里先找一个数字作为基准数，一般地都会用这组数字的第一个数或者最后一个数作为基准数。在这里我们选择这组数据的第一个数作为基准数。然后设置两个游标，我们将前游标指向第一个数，然后我们将后游标指向这组数据的最后一个数。然后从后游标往左，当找到比基准数字小的数字的时候，我们就将这个数和前游标指向的数字交换，然后前游标自增(加一，或者说前游标向后移动一位)。然后我们从前游标开始往右找，当找到比基准数字大的数的时候，我们就将这个数和后游标目前所指的数字进行交换。然后后游标自减(减一，或者说后游标向前移动一位)。然后重复上述步骤，直到后游标等于前游标的时候，此次排序结束。
      但是，要注意的是，上述排序的过程，只是将比基准数小的放在了基准数字左边，比基准数字大的，放在了基准数字右边，所以要想完全的将这组数据排序完成。我们还需要进一步排序，其实在上面我们就将数组划分成两个部分，一个部分比基准数字小的，一个部分是比基准数字大的，所以我们接下来只需要对这两个部分进行再次排序就行了，将左边的部分再次划分成两部分，直到最后不能继续划分，此时排序完成。说了这么多，可能有的同学还是不太理解，我们画个简单的示意图来辅助大家理解，如下图：

/* 经典排序算法:快速排序算法的c语言实现 */ 
#include<stdio.h>
#include<stdlib.h>
//展示数组元素的函数 
void display(int a[],int len){
	int i = 0;
	while(i<len){
		printf("%d ",a[i++]); 
	}
	printf("\n");
}

//交换两个数的函数 
void swap(int *first,int *second){
	int temp;
	temp = *first;
	*first = *second;
	*second = temp;
}

//将数组元素划分成两个部分,比基准元素大的和比基准元素小的 
int sort(int a[],int start,int end){
	 int standard = a[start];
	 int low = start;
	 int high = end;
	 while(low<high){
	 	while(low<high && a[high]>=standard){
	 		high--;
		 }
		 
		 if(low<high){
		 	swap(&a[low],&a[high]);
		 	low++;
		 }
		 
		 while(low<high && a[low]<=standard){
		 	low++;
		 }
		 
		 if(low<high){
		 	swap(&a[low],&a[high]);
		 	high--;
		 }
	 }
	a[low] = standard; 
	return low; 
}

//快速排序函数 
void quickSort(int a[],int start,int end){
	if(start<end){
		int pos = sort(a,start,end);
		quickSort(a,start,pos-1);//递归调用 
		quickSort(a,pos+1,end);//递归调用 
	}
}
int main(void){
	int len = 0;
	int *p;
	int i;
	printf("请输入排序的数组长度:\n");
	scanf("%d",&len);
	getchar();//读走输入流的回车字符
	p = (int *)malloc(sizeof(int)*len);
	printf("请输入排序的数字:\n");
	for(i = 0;i<len;i++){
		scanf("%d",&p[i]);
	}
	printf("排序前的数组:\n");
	display(p,len);
	quickSort(p,0,len-1);
	printf("排序后的数组:\n");
	display(p,len);
	free(p); //释放内存 
	return 0;
}

      简单介绍下上述代码，display函数形参有两个一个是整形数组，一个是数组的长度，这个函数的功能是将数组里的元素输出到控制台上。swap函数的功能就是交换两个数字的值。然后就是sort函数，将数组元素划分成两个部分，一个部分是比基准元素要小的部分，另外一个部分是比基准元素要大的部分。而在quickSort函数里，我们调用sort函数从而得到我们划分好了的基准元素所在的下标，然后以这个下标为界，将前面一部分数据再进行排序，后面一部分数据再进行排序直到结束。
      下面给出代码运行结果：