快速排序

　　快速排序是面试中经常问到的排序算法

　　基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，

　　则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的

　　代码如下：

　　1.swap 交换函数

void swap(int& a,int& b)
{
int temp = a;
a = b;
b = temp;
}

　 2.Partition函数—快速排序中最关键的函数

int Partition(int* list,int low,int high)
{
int pivot = list[low];
while(low=pivot)
high--;
swap(list[low],list[high]);
while(low<high&&list[low]<=pivot)
low++;
swap(list[low],list[high]);
}
return low;
}

　3.QSort函数—快速排序算法实现—递归

void QSort(int* list,int low ,int high)
{
int pivotKey;
if(low<high)
{
pivotKey = Partition(list,low,high);
QSort(list,low,pivotKey-1);
QSort(list,pivotKey+1,high);
}
}

改进算法：
　　1.优化选取枢轴

　　　　Partition函数中选取pivotKey是一个关键，如果pivotKey选取的不是中间数，效率会受到不同程度的影响

　　　　比如数组{9,1,5,8,3,7,6,2},pivotKey = 9,partition结果是最后一位，只是实现了9和2的互换

　　　　改进办法：

　　　　　　1.取随机数

　　　　　　2.三数取中:取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端、中间三个数

　　　　　　在Partition基础之上，添加、修改成如下代码：

　　 int pivotKey;
int m = low+(high-low)/2;
if(list[low]>list[high])
swap(list[low],list[high]);
if(list[m]>list[high])
swap(list[m],list[high]);
if(list[m]<list[low])
swap(list[m],list[low]);
　　 pivotKey = list[m];

　　　　　　当然也可以九数取中　　

　　2.优化不必要的交换

int Partition2(int* list,int low,int high)
{
int pivotKey;
//可以加上三数取中
pivotKey = list[low];
int temp = pivotKey;
while(low=pivotKey)
high--;
list[low] = list[high];
while(low<high&&list[low]<=pivotKey)
low++;
list[high] = list[low]
}
list[low] = temp;
return low;
}

　 3.优化小数组时的排序方案

如果数组是小数组，应该采用插入排序，如果数组较长，应该采用快速排序

void QSort1(int* list,int low,int high)
{
int pivot;
if((high-low)>MAX_LENGTH)
{
pivot = Partition(list,low,high);
QSort1(list,low,pivot-1);
QSort1(list,pivot+1,high);
}else{

    InsertSort(list);  
}  

}

4.优化递归操作

void QSort2(int *list,int low,int high)
{
int pivot;
if((high-low)>MAX_LENGTH)
{
while(low<high)
{
pivot = Partition(list,low,high);
QSort2(list,low,pivot-1);
low = pivot+1;
}
}else
{
InsertSort(list);
}
}