数据结构入门学习（全是干货）——排序算法（下）1 快速排序1.1 算法概述

快速排序采用分而治之的策略，与归并排序相似。其核心在于选择一个主元（pivot）作为分割点。

分而治之主元(pivot)=>中枢枢纽的意思

伪码描述

快速排序的最佳情况是每次都能将数组均分。

void Quicksort( ElementType A[],int N )
{
    if( N < 2 ) return;
    pivot = 从A[]中选一个主元;//主元的选择决定了快速排序到底快不快
    将S = { A[] \ pivot }将除了主元以外的元素分成两个独立子集://怎么分
    	A1 = {a属于S | a <= pivot }和A2 = {a属于S | a >= pivot };//一部分由小于等于pivot元素来组成的，另一部分由大于等于pivot元素组成
    A[] = Quicksort(A1,N1) U {pivot} U Quicksort(A2,N2);
}

什么是快速排序算法的最好情况？每次正好中分

1.2 选主元

随机选择主元：使用 rand() 函数会影响性能。取头、中、尾的中位数作为主元：例如，对于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 ] );
    //这样三步交换下来，左边一定是最小的那个
    Swap( &A[ Center ],&A[ Right-1 ] );//将pivot藏到右边(为了之后方便，先将Center放到现在需要考虑的子列的最右边)，然后就只需要考虑A[Left + 1]....A[ Right - 2]
    return A[ Right - 1];//返回pivot
}

1.3 子集划分

i和j并非C语言指针，而是指向存放位置。主元被移至最右侧。对比主元与i、j的值并进行交换，直至完成分区。

快速排序的优势：

注意事项：

如果存在与主元相等的元素：

小规模数据处理：

1.4 算法实现

void Quicksort( ElementType A[],int Left,int Right )
{
    if( Cutoff <= Right - Left ){
    Pivot = Median3( A,Left,Right );//pivot是主元的意思，在这里返回的不仅仅只是一个主元的值
    //这里的Left参数是最小值，Right参数是最大值。真正的主元被藏在了Right-1的地方
    i = Left; j = Right - 1;
    for(;;){
        while(A[ ++i ] < Pivot ){}
        while(A[ --j ] < Pivot ){}
        if( i < j)
            Swap( &A[i],&A[j] );//i < j则证明中间还有其他元素，这时候就可以调换
        //如果i > j则这个子集划分应该结束了
        else break;
    }
    Swap( &A[i],&A[Right-1]);//把藏在right-1这个位置的主元换到A[i]的位置上面去
    Quicksort(A,Left,i-1);//递归的左半部分
    Quicksort(A,i+1,Right);//递归的右半部分   
	}
	else
        Insertion_Sort(A+Left,Right-Left+1);//Right-Left+1：待排序列的总个数；A+Left：开始的地方
}

快速排序的标准接口设计

void Quick_Sort(ElementType A[], int N) 
{ 
   /* 这里写什么？如下*/
	Quicksort( A, 0, N-1 );
}

2 表排序2.1 算法概述

表排序适用于待排元素为复杂结构（如书籍）。其特点是不移动原始数据，仅移动指向它们位置的指针。

间接排序：

2.2 物理排序

N个元素可由独立环组成。环内元素依赖于其指针值，形成互不交集的独立结构。

环判断：每访问空位后，令 table[i] = i。当 table[i] == i 时，环结束。

复杂度分析：

最好情况：初始即有序。最坏情况：有N/2个环，每个环包含2个元素，移动需3N/2次。时间复杂度：T = O(mN)，m为每个元素的复制时间。3 基数排序

基于比较的排序算法其最坏时间复杂度下界为O(NlogN)。基数排序是一种非比较排序。

3.1 桶排序

基数排序是桶排序的扩展，通过数组作为指针的桶来存储数据。

count是数组，这个数组的每一个元素都是一个指针，一开始被初始化为空链表的头指针，所以一开始有101个空链表(对应了101个空的桶 )

假设一个学生考88分：先找到88这个桶，然后把学生信息插到这个链表的表头里

伪码描述
void Bucket_Sort(ElementType A[],int N)
{
    count[]初始化;
    while(读入一个学生成绩grade)
        将该生插入count[grade]链表;
    for( i=0;iif( count[i] )//桶不为空
            输出整个count[i]链表;
    }
}
桶排序算法的时间复杂度T(M, N)是多少？	T(N,M) = O(M+N)
    当M非常小的时候(例如4w个学生只有101个不同成绩值，那这个时候其实就相当于一种线性的算法)

3.2 基数排序

如果M>>N的话怎么办？

处理值在0到999之间的整数时，每位数有十种可能。

输入序列：64，8，216，512，27，729，0，1，343，125
    用"次位优先"(Least Significant Digit)=>简称LSD算法
    //什么是次位优先？假设目前手里是216，这个时候6 个位数是最次位，2 百位数是主位(有一种算法是主位优先)
    //比较先从个位数开始

步骤：

建立十个桶。

根据个位数分配到相应的桶。

根据十位数分配。

根据百位数分配。

复杂度：设元素个数为N，基数为B，LSD的趟数为P，最坏时间复杂度为：T=O(P(N+B))。

3.3 多关键字排序

基数排序适用于多关键字排序：

主位优先：为每种花色建立桶，内部排序后合并。次位优先：为面值建桶，直接合并结果，后续再根据花色建立桶。

次位优先方法效率更高，时间复杂度更低。

4 排序算法的比较

前三个算法为简单排序，时间复杂度较差，但实现简单且不需额外空间。