4.2 快速排序

快速排序的原理：

比如有3个数4 7 2，我们把4作为关键字，把比4小的数排在4左边，把比4大的数排在4右边，最后的结果就为2 4 7。同理，当数很多的时候：

第一步：我们可以选择第一个数为关键字，把比关键字小的排在关键字左边，把比关键字大的排在关键字右边。

第二步：将关键字左边的数再次进行快速排序。

第三步：将关键字右边的数再次进行快速排序。

当a[j]>k的时候，j--，指标往前移动，知道a[j]<k的时候停止

当a[j]<k的时候才交换,把小的数交换到关键字k的左边,a[i]和a[j]交换

 

当a[i]<k的时候，i++,直到a[i]>=k的时候才交换

当a[i]>=k的时候，交换a[i]和a[j]。 

#include<iostream>
using namespace std;
int a[8] = {7,1,3,8,12,11,2,9};
int n = 8;
int t= 0;
void swap(int &a, int  &b)
{
 	int tmp = a;
 	a = b;
 	b = tmp;
}
void quicksort(int a[],int s, int e)
{
	if(s >= e) return;//边界条件不能忘了 
	int k = a[s];
	cout << "交换次数" << ++t <<": " << endl;
	cout << "关键字："  << k << endl; 
	int i = s;
	int j = e;
	while(i != j)
	{
		while(i < j && k <= a[j])  j--;
		swap(a[i],a[j]);
		while(i < j && k >= a[i]) i++;
		swap(a[i],a[j]);
	}

	for(int i = 0; i < n; ++i)
		cout << a[i] << " ";
	cout << endl;
	quicksort(a,s,i-1);
	quicksort(a,i+1,e);
}

int main()
{
	quicksort(a,0,n-1);
	for(int i = 0; i < n; ++i)
	{
		cout << a[i] << " ";
    } 
    cout << endl;
    return 0;
} 

快速排序存在一个最坏时间复杂度，即当数据全部 为有序的时候，此时关键字左边或者右边就不需要再用快速排序，每次都是从头开始快速排序，复杂度为O(n^2).所以采用快速排序的时候最好要将数据打乱，并且快速排序不是一个稳定的排序，归并排序是稳定的排序。