快速排序

• 算法描述
• • 选主元
  • 子集划分及快速排序具体实现
  • 快速排序的问题
  • c语言快速排序库函数qsort

算法描述

主要采用分而治之、递归算法
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

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排序 ---------------*/