Scott's world.

第十讲-排序-下

Word count: 1.8kReading time: 8 min
2019/08/14 Share

第十讲 排序(下)

快速排序

算法概述

分而治之

1
2
3
4
5
6
7
8
9
10
11
//伪代码
void Quicksort(ElementType A[],int N)
{
pivot = 从A[]中选一个主元;
将S = {A[] \ pivot} 分成两个独立子集
A1 = { a ∈ S | a <= pivot} 和
A2 = { a ∈ S | a >= pivot};
A[] = Quicksort(A1,N1) ∪
(pivot) ∪
Quicksort(A2,N2);
}

该算法最好情况下就是每次主元都是中分

时间复杂度为 O(NlogN)

选主元

  • 若 pivot = A[0]

    则最坏情况下时间复杂度为O(N^2)

  • 若 利用rand()取pivot

    rand()函数会增加复杂度

  • 若 取头,中,尾的中位数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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藏到右边
    //只需要考虑A[Left+1]-A[Right-2]
    retrun A[Right-1];
    }

子集划分

如果有元素正好等于pivot,我们有两个选择

  • 停下来交换
  • 继续移动指针

小规模数据的处理

  • 快速排序的问题

    • 递归会消耗过多的内存空间
    • 对小规模的数据可能还不如插入排序快
  • 解决方案

    • 当递归的数据规模充分小,则停止递归,直接调用简单排序(例如插入排序)
    • 在程序中定义一个Cutoff的阈值

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void Quicksort(ElementType A[],int Left,int Right)
{
if(Cutoff <= Right-Left){
Pivot = Median3(A,Left,Right);
i=Left;
j=Right-1;
for(; ;)
{
while(A[++i]<Pivot){}
while(A[--j]>Pivot){}
if(i<j)
Swap(&A[i],&A[j]);
else break;
}
Swap(&A[i],&A[Right-1]);
Quicksort(A, Left,i-1);
Quicksort(A,i+1,Right);
}else{
Insertion_Sort(A+Left,Right-Left+1);//插入排序
}
}

void Insertion_Sort(ElementType A[],int Left,int Right)
{
int p,temp,i;
for(i=left+1;i<=Right;p++)
{
temp=A[i];
for(p=i;p>=Left+1&&temp<A[p-1];p--)
A[p]=A[p-1];
A[p]=temp;
}
}


void Quick_sort(ElementType A[],int N)
{
Quicksort(A,0,N-1);
}
  • 也可以直接调用库函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /* 快速排序 - 直接调用库函数 */

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

表排序

间接排序

  • 定义一个指针数组作为”表”(table)

  • 物理排序

    N个数字的排列由若干个独立的环组成的

  • 复杂度分析

    • 最好情况:初始即有序

    • 最坏情况

      • 有[N/2]个环,每个环包含2个元素(向下取整)

      • 需要[3N/2]次元素移动(向下取整)

        T=O(mN),m是每个A元素的复制时间

基数排序

  • 假设我们有N个学生,他们的成绩是0到100之间的整数(于是有M= 101个不同的成绩值)。如何在线性时间内将学生按成绩排序?

  • 假设我们有N=10个整数,每个整数的值在0到999之间(于是有M = 1000个不同的值). 还有可能在线性时间内排序吗?

多关键字的排序

一副扑克牌是按2种关键字排序的

  • 主位优先(Most Significant Digit)排序

    • 为花色建4个桶
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    /* 基数排序 - 主位优先 */

    /* 假设元素最多有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 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;
    B[Di].head = tmp;
    }
    /* 下面是收集的过程 */
    i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */
    for (Di=0; Di<Radix; Di++) { /* 对于每个桶 */
    if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */
    p = B[Di].head;
    while (p) {
    tmp = p;
    p = p->next;
    A[j++] = tmp->key;
    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);
    }
  • 次位优先(Least Significant Digit)排序

    • 为面值建13个桶
    • 将结果合并然后再为花色建4个桶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/* 基数排序 - 次位优先 */

/* 假设元素最多有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) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p; p = p->next;
/* 插入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 */
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);
}

排序算法的比较

CATALOG
  1. 1. 第十讲 排序(下)
    1. 1.1. 快速排序
      1. 1.1.1. 算法概述
        1. 1.1.1.1. 选主元
        2. 1.1.1.2. 子集划分
        3. 1.1.1.3. 小规模数据的处理
      2. 1.1.2. 算法实现
    2. 1.2. 表排序
      1. 1.2.1. 基数排序
        1. 1.2.1.1. 多关键字的排序
    3. 1.3. 排序算法的比较