C++快速排序

快速排序介绍：

基础思路：

首先快速排序是由冒泡排序所改进的，都是通过多次比较和交换来实现排序，但快速排序是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，分别对这两部分记录继续进行排序，以达到整个序列有序。

思路详解：

(1)首先我们先设定一个分界值（也就是基准），通过该分界值将数组分成左右两部分。

(2)然后我们将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

(3)左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这其实就是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

代码详细：

#include<iostream>
using namespace std;
int arr[100],n;//全局变量
void quicksort(int left,int right){
		int i,j,k,temp;
		if(left > right) return;
		temp = arr[left]; //先将基准数保存下来，这里选择左边为基准数
		i=left; j=right;
		while(i!=j){
			//先从右往左找，找到比基准数小的数
			while(arr[j] >= temp && i < j)
			    j--;
			
			//再从左往右找，找到比基准数大的数
			while(arr[i] <= temp && i < j)
			    i++;
			
			//如果是找到，而不是i和j相遇了，就交换他们的位置
			if(i < j){
				k=arr[i];
				arr[i]=arr[j];
				arr[j]=k;
			}
		}//退出时 i = j 此时将基准数和 i(或j)位置的数交换
		arr[left]=arr[i];
		arr[i]=temp;
		//交换完基准数后 继续处理左右的位置
		quicksort(left,i-1);
		quicksort(i+1,right);
		return;
}
int main(){
	int i;
	printf("数据个数:\n");
	scanf("%d",&n);
	printf("输入%d个数据:\n",n);
	for(i=0;i<n;i++)
	    scanf("%d",&arr[i]);
	quicksort(0,n-1);
	printf("排序后的数据为:\n");
	for(i=0;i<n;i++)
	    printf("%d ",arr[i]);
	printf("\n");
	return 0;
}

运行效果：

当然这里是按从小到大的顺序进行排序，我们也可以通过改变比较的大小情况，改为从大到小进行排序。

学习flag：

我会在51CTO上持续更新使用C++写的一些算法学习讲解，感谢大家的支持