快速排序

快速排序有三种写法，平均复杂度几乎相同。

我们这里给出最常见的那种，把第一个元素拎出来，然后找到它该去的地方再塞进去。

快速排序和冒泡排序都属于交换排序，都属于不稳定排序。

一趟快速排序定一个位置，并且把区间分为两部分。

int Partition(int* arr,int i,int j){ //j逆向遍历，i正向遍历 
	int temp = arr[i]; //temp存储基准值 
	while(i < j){
		//逆向遍历
		while(i < j && arr[j] >= temp) j --; //大于基准值继续遍历 
		if(i < j){ arr[i] = arr[j]; i ++;} //小于基准值左移
		//正向遍历  
		while(i < j && arr[i] <= temp) i ++; //小于基准值继续遍历 
		if(i < j){ arr[j] = arr[i]; j --;} //大于基准值右移 
	}
	arr[i] = temp; //基准值就位 
	return i; //返回基准位置，即排序区间划分点 
} 

快速排序算法：

void QuickSort(int* arr,int left,int right){
	if(left < right){
		int PivotPos = Partition(arr,left,right); //划分 
		QuickSort(arr,left,PivotPos-1);
		QuickSort(arr,PivotPos+1,right);
	}
}

代码如下：

#include<iostream>
using namespace std;

int Partition(int* arr,int i,int j){ //j逆向遍历，i正向遍历 
	int temp = arr[i]; //temp存储基准值 
	while(i < j){
		//逆向遍历
		while(i < j && arr[j] >= temp) j --; //大于基准值继续遍历 
		if(i < j){ arr[i] = arr[j]; i ++;} //小于基准值左移
		//正向遍历  
		while(i < j && arr[i] <= temp) i ++; //小于基准值继续遍历 
		if(i < j){ arr[j] = arr[i]; j --;} //大于基准值右移 
	}
	arr[i] = temp; //基准值就位 
	return i; //返回基准位置，即排序区间划分点 
} 

void QuickSort(int* arr,int left,int right){
	if(left < right){
		int PivotPos = Partition(arr,left,right); //划分 
		QuickSort(arr,left,PivotPos-1);
		QuickSort(arr,PivotPos+1,right);
	}
}

int main(){
	int arr[] = {1,5,3,4,0,8,9,7,6,2};
	for(int i = 0;i < 10;i ++) cout<<arr[i]<<" ";
	cout<<endl;
	QuickSort(arr,0,9);
	for(int i = 0;i < 10;i ++) cout<<arr[i]<<" ";
} 

运行结果：