快速排序
注：快速排序被公认为是最快的排序方法，但是如果有某些细节处理不到位，就会导致这个排序不是快速排序了，还会相当的慢比如主元的选取，左右集合的划分方法
算法描述
主要采用分而治之、递归算法
1.在一堆数据中任意选择一个数作为主元（pivot）
2.将剩下的数据以主元为中枢，分为大于主元和小于主元的两个集合，这就是分的过程
3.接下来对左右两个集合递归进行治，递归进行相同的操作
伪码实现：
void QuickSort(ElementType A[],int N)
{
if(n<2) 当只有一个数时结束递归
pivot=从A[]中选一个主元
将S = {A[]\pivot } 分成2个独立子集：
A1= { a 属于 S| a<= pivot }和
A2= { a 属于 S| a>= pivot };
A[] =Quicksort(A1, N1)|| {pivot} || Quicksort(A2,N2);
}
虽然算法并不复杂，但是其中有很多细节需要注意
快速排序的最好情况：
每次正好中分，T(N)=O(NlogN) 只要是每次中分的分治法时间复杂度都是 nlogn
快速排序的最坏情况：
选主元直接取第0个元素
假设一开始数据集为：1 2 3 4 5 6 7 8 …n-1 n
1 2 3 4 5 6 7 8 …n-1 n
2 3 4 5 6 7 8…n-1 n
T(N) = O(N) + T(N-1) =O(N**2) 是最慢的排序方式了
选主元
取头、中、尾的中位数
如 8 、12 、3 的中位数就是8
实现代码：
ElementType Median3(ElementType A[],int Left,int Right)
{
int Center = (Left+Right)/2;
if(A[Left]>A[center])
{
Swap(&A[Left],&A[center]);
}
if(A[Left]>A[Right])
{
Swap(&A[Left],&A[Right]);
} //这两步后保证了最左边的元素一定是最小的
if(A[center]>A[Right])
{
Swap(&A[center] , &A[Right]);
}
//交换后 三者的大小关系为： A[Left]<=A[center]<=A[Right]
Swap( &A[ center ],&A[ Right-1 ]) //将picot藏到右边，即倒数第二个，因为A[Right]肯定比pivot大
//A[Left]肯定比pivot小，则相当于这两个位置的元素已经排好序了
//下一次只需要将A[Left+1]到A[Right-2] 进行排序即可
return A[Right-1]; //返回pivot
}
子集划分及快速排序具体实现
快速排序实现：
#include<bits/stdc++.h>
using namespace std;
typedef int ElementType;
void Swap(ElementType &a,ElementType &b)
{
ElementType t=a;
a = b;
b = t;
}
void output(ElementType *A,int Left,int Right)
{
for(int i=Left;i<=Right;i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
}
ElementType Median3(ElementType A[],int Left,int Right)
{
int center = (Left+Right)/2;
if(A[Left]>A[center])
{
Swap(A[Left],A[center]);
}
if(A[Left]>A[Right])
{
Swap(A[Left],A[Right]);
} //这两步后保证了最左边的元素一定是最小的
if(A[center]>A[Right])
{
Swap(A[center] , A[Right]);
}
//交换后 三者的大小关系为： A[Left]<=A[center]<=A[Right]
Swap( A[ center ],A[ Right-1 ]); //将picot藏到右边，即倒数第二个，因为A[Right]肯定比pivot大
//A[Left]肯定比pivot小，则相当于这两个位置的元素已经排好序了
//下一次只需要将A[Left+1]到A[Right-2] 进行排序即可
//output(A,Left,Right);
return A[Right-1]; //返回pivot
}
void Quicksort(ElementType *a,int Left,int Right)
{
if(Left>=Right) return; //递归结束条件，当要排序的序列只有一个元素时
int pivot=Median3(a,Left,Right); //获取数组头、中、尾三个元素的中位数作为主元
int i=Left+1;
int j=Right-2;
if(i>j) return;
while(1) //当i移动到j右边时表示扫描完所有数据了，此时i所在的位置就是主元排序好后应该所处的位置
{
while(a[i]<pivot) i++; //i一直向右移动，直到遇到的数大于主元，则需要将该元素换到主元右边去
while(a[j]>pivot) j--; //j一直向左移动，直到遇到的数小于主元，则需要将该元素换到主元左边去
if(i>j) break;
Swap(a[i],a[j]); //将大于主元的j处元素与小于主元的i处元素交换
//output(a,Left,Right);
}
Swap(a[i],a[Right-1]); //将主元交换到当前位置
//output(a,Left,Right);
Quicksort(a,Left,i-1); //递归对主元左边部分数组排序
Quicksort(a,i+1,Right); //递归对主元右边部分数组排序
return;
}
int main()
{
int n;cin>>n;
int data[n];
for(int i=0;i<n;i++)
{
cin>>data[i];
}
Quicksort(data,0,n-1);
for(int i=0;i<n;i++)
cout<<data[i]<<" ";
return 0;
}
快速排序的问题
1.用递归算法，会占用额外的系统堆栈空间，会不断的入栈、出栈,所以整个递归过程是很慢的
2.对于小规模的数据，（例如n不到100）可能还不如插入排序快
3.解决方案
当递归的数据规模充分小，则停止递归，直接调用简单排序（例如插入排序）
在程序中定义一个Cutoff的阈值，实践一下，比较不同的Cutoff对效率的影响
加上Cutoff阈值改进后的程序（快速排序与插入排序相结合）
ElementType Median3( ElementType A[], int Left, int Right )
{
int Center = (Left+Right) / 2;
if ( A[Left] > A[Center] )
Swap( &A[Left], &A[Center] );
if ( A[Left] > A[Right] )
Swap( &A[Left], &A[Right] );
if ( A[Center] > A[Right] )
Swap( &A[Center], &A[Right] );
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] */
return A[Right-1];
}
void Qsort( ElementType A[], int Left, int Right )
{ /* 核心递归函数 */
int Pivot, Cutoff, Low, High;
if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
Pivot = Median3( A, Left, Right ); /* 选基准 */
Low = Left; High = Right-1;
while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
while ( A[++Low] < Pivot ) ;
while ( A[--High] > Pivot ) ;
if ( Low < High ) Swap( &A[Low], &A[High] );
else break;
}
Swap( &A[Low], &A[Right-1] ); /* 将基准换到正确的位置 */
Qsort( A, Left, Low-1 ); /* 递归解决左边 */
Qsort( A, Low+1, Right ); /* 递归解决右边 */
}
else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */
}
void QuickSort( ElementType A[], int N )
{ /* 统一接口 */
Qsort( A, 0, N-1 );
}
c语言快速排序库函数qsort
/* 快速排序 - 直接调用库函数 */
#include <stdlib.h>
/*---------------简单整数排序--------------------*/
int compare(const void *a, const void *b)
{ /* 比较两整数。非降序排列 */
return (*(int*)a - *(int*)b);
}
/* 调用接口 */
qsort(A, N, sizeof(int), compare);
/*---------------简单整数排序--------------------*/
/*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/
struct Node {
int key1, key2;
} A[MAXN];
int compare2keys(const void *a, const void *b)
{ /* 比较两种键值：按key1非升序排列；如果key1相等，则按key2非降序排列 */
int k;
if ( ((const struct Node*)a)->key1 < ((const struct Node*)b)->key1 )
k = 1;
else if ( ((const struct Node*)a)->key1 > ((const struct Node*)b)->key1 )
k = -1;
else { /* 如果key1相等 */
if ( ((const struct Node*)a)->key2 < ((const struct Node*)b)->key2 )
k = -1;
else
k = 1;
}
return k;
}
/* 调用接口 */
qsort(A, N, sizeof(struct Node), compare2keys);
/*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/