表排序

表排序(间接排序)

  • 当每一个待排序的元素都非常大，一本书，一部电影等，移动元素的代价比较大
    • 选择不移动元素而移动指向他们的下标
  • 定义一个数组作为“表”(table)
  • 例：table(以插入排序为例)
A [0] [1] [2] [3] [4] [5] [6] [7]
key f d c a g b h e
table 0 1 2 3 4 5 6 7
A [0] [1] [2] [3] [4] [5] [6] [7]
key f(d) d(f) c a g b h e
table 1 0 2 3 4 5 6 7
A [0] [1] [2] [3] [4] [5] [6] [7]
key f© d(d) c(f) a g b h e
table 2 1 0 3 4 5 6 7
......
A [0] [1] [2] [3] [4] [5] [6] [7]
key f(a) d(b) c© a(d) g(e) b(f) h(g) e(h)
table 3 5 2 1 7 0 4 6

物理排序

如果一定要按照实际的物理地址进行排序，下面的方法可在线性时间复杂度下完成

  • N个数字的排列由若干个独立的环组成
    • A[0]对应table[3]，A[3]对应table[1]，A[1]对应table[5]，A[5]对应table[0]，形成一个环
    • 独立的环对每个环进行移动操作可减少移动次数(避免无效的移动)
  • 如：在表中分出三个环，分别对每个环里面的元素按照物理排序
A [0] [1] [2] [3] [4] [5] [6] [7]
key f d c a g b h e
table 3(1) 5(1) 2(2) 1(1) 7(3) 0(1) 6(3) 4(3)
  • 令temp=table[0]=f，此时table[0]的位置空出
    • 将该位置上本来应该放置的元素移动过来，即table[0]=a，此时原来放置a的位置table[3]空出
    • 同理，将table[3]应该放置的元素d移动到table[3]，同样的table[1]空出
    • 以此类推，直到table[5]空出，此时table[5]应该放置的元素为f=temp，将临时变量放入最后的空位
A [0] [1] [2] [3] [4] [5] [6] [7]
key a b c d g f h e
table 3(1) 5(1) 2(2) 1(1) 7(3) 0(1) 6(3) 4(3)
  • 如何判断一个环的结束
    • 每访问一个空位i后，令table[i]=i
    • 当发现table[i]==i时，环结束

复杂度分析

  • 最好情况：初始即有序
  • 最坏情况：
    • 有⌊\freq{N}{2}⌋个环，每个环包含2个元素(多元环最多的情况)
      • 需要⌊3N/2⌋⌊3N/2⌋次元素移动
    • T=O(mN)T=O(mN)，m是每个A元素的复制时间(每个元素都比较大，故复制元素的时间不可忽略)

桶排序

定理：任何基于比较的排序算法，其最坏情况平均时间复杂度下界为Ω(NlogN)Ω(NlogN)

桶排序：打破NlogNNlogN的界限(并不直接进行比较)

  • 例：假设有N个学生，成绩是0到100之间的整数(于是有M=101个不同的成绩值)
    • 如何在线性时间内将学生按成绩排序
      • 此问题中数据的特殊性：学生可以有很多，但是成绩的种类就只有101种
    • 建立101个“桶”，每个桶代表一个成绩值，相同成绩的学生在对应的桶中构成链表
    • 扫描每个学生的成绩，依次将其插入到对应的桶中
    • 每个桶被初始化为一个空链表的头指针

桶排序伪代码描述

void BUcket_Sort(ElementType A[],int N){
    初始化count[];
    while(读入1个学生的成绩grade)
        将该生插入count[grade]链表;
    for(i=0;i<M;i++){
        if(count[i])
            输出整个count[i]链表;
    }
}

时间复杂度：T(N,M)=O(M+N)T(N,M)=O(M+N)

  • 每个学生结点和成绩结点都要扫描一遍
  • 当M>>NM>>N时，T(M)=O(M)T(M)=O(M)，可看做线性算法

基数排序

单关键字排序

基数排序：根据位次建桶

  • 例：假设有N=10个整数，每个整数的值在0到999之间(于是有M=1000个不同的可能值)
    • [64,8,216,512,27,729,0,1,343,125][64,8,216,512,27,729,0,1,343,125]
  • 如何在线性时间内将所有整数排序
    • 在排序的时候，次关键字对应低位，主关键字对应高位
      • 如整数的高位相对于低位而言是主关键字，低位是次关键字
    • “次位优先”(Least Significant Digit,LSD)
      • 将整数按位排序，先从低位开始排序，然后对高位进行排序(递增)
    • 将整数的进制称为“基数”
      • 建立基数个桶
      • 先按低位对元素进行排序，然后在前面的基础上对高位进行排序

时间复杂度：设元素个数为N，基数为B，LSD的趟数(最高位数)为P=\frac{log(最大元素)}{logB}

  • 一共排序P趟
  • 在每一趟排序中要对B个桶、N个元素扫描一遍
  • T=O(P(N+B))T=O(P(N+B)) (一般而言P和B可忽略不计，因此该算法是线性复杂度)
  • 额外空间复杂度：O(N+B)O(N+B)

多关键字的排序

  • 例：一副扑克牌是按两种关键字排序的
    • K0[花色]：♣️ < ♦️ < ♥️ < ♠️
    • K1[面值]：2<3<4<5<6<7<8<9<10<J<Q<K<A2<3<4<5<6<7<8<9<10<J<Q<K<A
    • 有序结果：22♣️......A♣️22♦️...A...A♦️22♥️...A...A♥️22♠️...A...A♠️
  • 此问题中主关键字为花色，此关键字为面值
    • “主位优先”(Most Significant Digit,MSD)
  • 为花色建4个桶
    • 在每个桶内排序，最后合并结果
    • 比较，用“次位优先”排序：
  • 为面值建13个桶
    • 将结果合并，然后再为花色建4个桶，再次排序
  • LSD并不是在任何情况下都比MSD快，二者各有各自的适用场合

基数排序演示

#include<cstdlib>
typedef int ElementType;

/* 基数排序 - 次位优先 */

/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10

/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
    int key;
    PtrToNode next;
};

/* 桶头结点 */
struct HeadNode {
    PtrToNode head, tail; 
};
typedef struct HeadNode Bucket[Radix];  //桶是一个头结点链表，在最后排序的时候可以通过头尾结点指针来整个插入
 
int GetDigit ( int X, int D )
{ /* 默认次位D=1, 主位D<=MaxDigit */
    int d, i;
  
    for (i=1; i<=D; i++) {
        d = X % Radix;
        X /= Radix;
    }
    return d;
}

void LSDRadixSort( ElementType A[], int N )
{ /* 基数排序 - 次位优先 */
    int D, Di, i;
    Bucket B;
    PtrToNode tmp, p, List = NULL; 
  
    for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
        B[i].head = B[i].tail = NULL;
    for (i=0; i<N; i++) { /* 将原始序列逆序存入初始链表List */
        tmp = (PtrToNode)malloc(sizeof(struct Node));
        tmp->key = A[i];
        tmp->next = List;            
        List = tmp;
    }
    /* 下面开始排序 */ 
    for (D=1; D<=MaxDigit; D++) { /* 对数据的每一位循环处理 */
        /* 下面是分配的过程 */
        p = List;
        while (p) {                    //直到List为空，分配结束
            Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
            /* 从List中摘除 */
            tmp = p; p = p->next;      //tmp指向被摘除的元素，p指向List下一个元素
            /* 插入B[Di]号桶尾 */      
            tmp->next = NULL;
            if (B[Di].head == NULL)    //桶空时的情况
                B[Di].head = B[Di].tail = tmp;
            else {
                B[Di].tail->next = tmp;
                B[Di].tail = tmp;
            }
        }
        /* 下面是收集的过程 */
        List = NULL; 
        for (Di=Radix-1; Di>=0; Di--) { /* 将每个桶的元素顺序收集入List */ //注意：这一过程是从radix-1即最大基数开始的
            if (B[Di].head) { /* 如果桶不为空 */
                /* 整桶插入List表头 */
                B[Di].tail->next = List;
                List = B[Di].head;
                B[Di].head = B[Di].tail = NULL; /* 清空桶 */
            }
        }
    }
    /* 将List倒入A[]并释放空间 */
    for (i=0; i<N; i++) {
        tmp = List;
        List = List->next;
        A[i] = tmp->key;
        free(tmp);
    } 
}

/* 基数排序 - 主位优先 */

void MSD( ElementType A[], int L, int R, int D )
{ /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */
    int Di, i, j;
    Bucket B;
    PtrToNode tmp, p, List = NULL; 
    if (D==0) return; /* 递归终止条件 */
  
    for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
        B[i].head = B[i].tail = NULL;
    for (i=L; i<=R; i++) { /* 将原始序列逆序存入初始链表List */
        tmp = (PtrToNode)malloc(sizeof(struct Node));
        tmp->key = A[i];
        tmp->next = List;
        List = tmp;
    }
    /* 下面是分配的过程 */
    p = List;
    while (p) {
        Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
        /* 从List中摘除 */
        tmp = p; p = p->next;
        /* 插入B[Di]号桶 */
        if (B[Di].head == NULL) B[Di].tail = tmp; 
        tmp->next = B[Di].head;         //注意MSD中不是插在桶尾，而是插在桶头
        B[Di].head = tmp;
    }
    /* 下面是收集的过程 */
    i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */
    for (Di=0; Di<Radix; Di++) { /* 对于每个桶 */       //MSD对每一个桶递归地进行排序
        if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */
            p = B[Di].head;
            while (p) {
                tmp = p;
                p = p->next;
                A[j++] = tmp->key;   //j最终为桶中的元素个数
                free(tmp);
            }
            /* 递归对该桶数据排序, 位数减1 */
            MSD(A, i, j-1, D-1);
            i = j; /* 为下一个桶对应的A[]左端 */
        } 
    } 
}

void MSDRadixSort( ElementType A[], int N )
{ /* 统一接口 */
    MSD(A, 0, N-1, MaxDigit); 
}

各种排序方法的比较