数据结构进阶 - 第九章 排序

数据结构进阶 - 第9章 排序

目录

• 1. 排序基本概念
• 2. 插入类排序
  • 2.1 直接插入排序
  • 2.2 折半插入排序
  • 2.3 希尔排序
• 3. 交换类排序
  • 3.1 冒泡排序
  • 3.2 快速排序
• 4. 选择类排序
  • 4.1 简单选择排序
  • 4.2 堆排序
• 5. 归并排序
• 6. 分配类排序
  • 6.1 计数排序
  • 6.2 桶式排序
  • 6.3 基数排序
• 7. 排序算法总结

1. 排序基本概念

1.1 基本定义

排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。

1.2 排序分类

(1) 内部排序 vs 外部排序

• 内部排序：全部在内存中进行
• 外部排序：需要借助外部排序完成

(2) 排序稳定性

• 稳定排序：关键字相同的两个记录，排序前后相对位置不发生变化
• 不稳定排序：关键字相同的两个记录，排序前后相对位置可能发生变化

记忆方法：若交换或移动元素时，中间可能会隔若干个元素时（空运移动），这种排序方法必定不稳定，如希尔、简单选择、快速和堆。

2. 插入类排序

2.1 直接插入排序

算法思想

将待插入元素逐个插入到已排序的记录序列中的适当位置。

算法要点

1. **监视哨r[0]**保存待插入的记录
2. 从后往前查找应插入的位置
3. 查找与移动用同一循环完成

算法实现

void InsSort(RecordType r[], int length) {
    for (i = 2; i <= length; i++) {
        r[0] = r[i]; j = i-1;
        while (r[0].key < r[j].key) {
            r[j+1] = r[j]; j = j-1;
        }
        r[j+1] = r[0];
    }
}

性能分析

• 空间复杂度：S(n) = O(1)
• 稳定性：稳定排序

2.2 折半插入排序

算法思想

将折半查找用于在有序记录集r[1…i-1]中确定插入位置，将相应的排序法称为折半插入排序法。

算法实现

void BinSort(RecordType r[], int length) {
    for (i = 2; i <= length; ++i) {
        if(r[i].key > r[i-1].key) continue;
        x = r[i];
        low = 1; high = i-1;
        while (low <= high) {
            mid = (low+high) / 2;
            if (x.key < r[mid].key) high = mid-1;
            else low = mid+1;
        }
        for (j = i-1; j >= low; --j) r[j+1] = r[j];
        r[low] = x;
    }
}

性能分析

• 空间复杂度：S(n) = O(1)
• 稳定性：稳定排序
• 元素必须顺序存储

2.3 希尔排序

算法思想

直接插入排序的最佳性质：

1. n比较小时，基本有序
2. 元素基本有序时，缩小增量，每组元素增多，但趋于有序

改进要点

1. 将记录序列分成若干个子序列分别进行直接插入排序
2. 经过多次调整记录基本有序

算法实现

void ShellSort(RecordType r[], int length, int delta[], int n) {
    for (i = 0; i < n; ++i)
        ShellInsert(r, length, delta[i]);
}

void ShellInsert(RecordType r[], int length, int delta) {
    for (i = 1+delta; i <= length; ++i) {
        if (r[i].key < r[i-delta].key) {
            r[0] = r[i]; 
            for (j = i-delta; j > 0 && r[0].key < r[j].key; j -= delta)
                r[j+delta] = r[j];
            r[j+delta] = r[0];
        }
    }
}

性能分析

增量的取法：

• Shell提出取d=n/2, d=d/2, 直到d=1为止
• Knuth提出d=d/3+1

• 空间复杂度：S(n) = O(1)
• 元素必须顺序存储

3. 交换类排序

3.1 冒泡排序

算法思想

通过相邻两个元素进行比较，因此在互换两个相邻元素时只能消除一个逆序。

基本算法

void BubbleSort(RecordType r[], int n) {
    for (i = 1; i <= n-1; i++) {
        for (j = 1; j <= n-i; ++j)
            if (r[j].key > r[j+1].key) {
                x = r[j]; r[j] = r[j+1]; r[j+1] = x;
            }
    }
}

改进算法

void BubbleSort(RecordType r[], int n) {
    change = TRUE;
    for (i = 1; i <= n-1 && change; i++) {
        change = FALSE;
        for (j = 1; j <= n-i; ++j)
            if (r[j].key > r[j+1].key) {
                x = r[j]; r[j] = r[j+1]; r[j+1] = x;
                change = TRUE;
            }
    }
}

双向冒泡排序

void doubleBubbleSort(int a[], int n) {
    int change = TRUE; int low = 1, high = n;
    while(low < high && change) {
        change = FALSE;
        for(i = low; i < high; i++)
            if(a[i] > a[i+1]) {
                t = a[i]; a[i] = a[i+1]; a[i+1] = t; 
                change = TRUE;
            }
        if(change)
            high--;
        for(j = high; j > low; j--)
            if(a[j] < a[j-1]) {
                t = a[j]; a[j] = a[j-1]; a[j-1] = t; 
                change = TRUE;
            }
        low++;
    }
}

性能分析

• 空间复杂度：S(n) = O(1)
• 稳定性：稳定

3.2 快速排序

算法思想

由于冒泡排序扫描过程中只对相邻的两个元素进行比较，因此在互换两个相邻元素时只能消除一个逆序。

算法改进：
如果能通过所有不相邻元素的交换，消除多个逆序，则会大大加快排序的速度。

快速排序方法中的一次交换可能消除多个逆序。

快速排序算法的递归定义

1. 选取轴值，做划分

   • 从待排序记录序列中选取一个记录，其关键字设为K1，将其余关键字小于K1的记录移到前面，而将关键字大于K1的记录移到后面，使得将待排序记录序列分成两个子序列，最后将关键字为K1的记录插到其分界线的位置处。

2. 分别对分割后的两个子序列进行快速排序

   • 对分割后的两个子序列继续按上述原则进行分割，直到所有子序列的表长不超过1为止。

算法实现

void QKSort(RecordType r[], int low, int high) {
    if(low < high) {
        pos = QKPass(r, low, high);
        QKSort(r, low, pos-1);
        QKSort(r, pos+1, high);
    }
}

一次划分算法

int QKPass(RecordType r[], int left, int right) {
    x = r[left];
    low = left; high = right;
    while (low < high) {
        while(low < high && r[high].key >= x.key)
            high--;
        if (low < high) {
            r[low] = r[high]; low++;
        }
        while (low < high && r[low].key <= x.key)
            low++;
        if (low < high) {
            r[high] = r[low]; high--;
        }
    }
    r[low] = x; 
    return low;
}

性能分析

如何避免最坏情况发生？

• 选择合适的枢轴元素，比如随机选取，或取中尾的中位数。

• 空间复杂度：顺序存储

• 稳定性：不稳定 {3, 3, 1}

4. 选择类排序

4.1 简单选择排序

算法思想

第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行n-1趟简单选择排序，直到所有记录排序完成为止。

算法实现

void SelectSort(RecordType r[], int n) {
    for(i = 1; i <= n-1; ++i) {
        k = i;
        for(j = i+1; j <= n; ++j)
            if(r[j].key < r[k].key)
                k = j;
        if(k != i) {
            x = r[i]; r[i] = r[k]; r[k] = x;
        }
    }
}

性能分析

时间复杂度与元素初始排列无关

• 空间复杂度：S(n) = O(1)
• 稳定性：不稳定 {3, 3, 1}

4.2 堆排序

算法改进要点

堆排序是在简单排序的基础上，将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录。

堆的定义

待排序的记录的关键字存放在数组r[1…n]之中，将r看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，任意结点r[i]的左孩子是r[2i]，右孩子是r[2i+1]，双亲结点是r[i/2]。

满足此条件的完全二叉树为堆：

• r[i].key ≥ r[2i].key并且
• r[i].key ≥ r[2i+1].key (i=1,2,…)

如何利用堆完成排序？

1. 将待排序记录按照堆的定义建初堆，并输出堆顶元素；
2. 调整剩余的记录序列，利用筛选法将新的下标范围内的记录重新筛选建成为一个堆，再输出堆顶元素；
3. 重复执行步骤②n-1次进行筛选，新筛选成的堆会越来越小，而新筛选后面的有序关键字会越来越多，最后便得排序记录序列成为一个有序的序列。这个过程称之为堆排序。

算法实现

void HeapSort(RecordType r[], int length) {
    crt_heap(r, length);
    n = length;
    for(i = n; i >= 2; --i) {
        t = r[1]; r[1] = r[i]; r[i] = t;
        sift(r, 1, i-1);
    }
}

void crt_heap(RecordType r[], int length) {
    n = length;
    for(i = n/2; i >= 1; --i)
        sift(r, i, n);
}

筛选算法

void sift(RecordType r[], int i, int n) {
    finished = FALSE;
    while (i <= n && !finished) {
        if(r[i].key < r[i].key(r[i+1].key)) {
            if (x.key < r[mid].key) high = mid-1;
            else low = mid+1;
        }
        for (j = i-1; j >= low; --j) r[j+1] = r[j];
        r[low] = x;
    }
}

性能分析

算法分析：

1. 堆排序在最坏情况下，其时间复杂度也为O(nlogn)。
2. 堆排序与树型排序相比较，排序中只需要存放一个记录的辅助空间，因此也将堆排序称作原地排序。
3. 堆排序是一种不稳定的排序方法。 它不适用于待排序记录个数较少的情况，但对较大的文件还是很有效的。

5. 归并排序

算法思想

自顶向下的二路归并排序算法：设归并排序的当前区间是a[low…high]，则归并排序的两个步骤如下：

1. 分解：将序列a[low…high]一分为二，即求mid=(low+high)/2; 递归地对两个子序列a[low…mid]和a[mid+1…high]进行归并排序。其终结条件是子序列长度为1（因为一个元素的子表一定是有序表）。

2. 求解子问题：排序两个子序列a[low…mid]和a[mid+1…high]。

3. 合并：与分解过程相反，将已排序的两个子序列a[low…mid]和a[mid+1…high]归并为一个有序序列a[low…high]。

算法实现

归并函数

void Merge(int a[], int low, int mid, int high) {
    i = low, j = mid+1, k = 0;
    tmpa = (int *)malloc((high-low+1)*sizeof(int));
    
    while (i <= mid && j <= high)
        if (a[i] <= a[j]) { tmpa[k] = a[i]; i++; k++; }
        else              { tmpa[k] = a[j]; j++; k++; }
    
    while (i <= mid)     { tmpa[k] = a[i]; i++; k++; }
    while (j <= high)    { tmpa[k] = a[j]; j++; k++; }
    
    for (k = 0, i = low; i <= high; k++, i++) a[i] = tmpa[k];
    free(tmpa);
}

归并排序函数

void MergeSort(int a[], int low, int high) {
    if (low < high) {
        mid = (low+high)/2;
        MergeSort(a, low, mid);
        MergeSort(a, mid+1, high);
        Merge(a, low, mid, high);
    }
}

自底向上的二路归并

分治策略如下：

循环log₂n次，length依次取1、2、4、8···，log₂n。每次执行以下步骤：

1. 分解：将序列分解成length长度的若干子序列。
2. 求解子问题：将相邻的两个子序列调用Merge算法合并成一个有序序列。
3. 合并：由于整个序列存放在数组中，排序过程是就地进行的，合并步骤不需要执行任何操作。

void MergeSort(int a[], int n) {
    for (length = 1; length < n; length = 2*length)
        MergePass(a, length, n);
}

性能分析

6. 分配类排序

6.1 计数排序

分配类排序：
排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序，它们的时间复杂度可达到线性阶：O(n)。

• 箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个"箱子"（箱子个数和待排序关键字取值个数相同），依次扫描待排序的记录R[0]、R[1]、R[n-1]，把关键字等于k的记录全部装入到编号为k的箱子里（分配），然后按序号依次将各非空箱子首尾连接起来（收集）。

算法步骤

待排序序列A= (60, 74, 90, 98, 66, 84, 79, 66, 74, 88, 90, 88, 98, 66)

1. 扫描一遍后，min=60, max=98
2. 申请max-min+1个空间tmp[]，初始化为0
3. 再次扫描一遍A，对元素A[i]=x，tmp[x-min]++。
4. 遍历tmp，根据元素个数，将其赋值回A[]。

性能分析

6.2 桶式排序

【例】 要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序，需设置13个"箱子"，排序的依次将每张牌按点数放入相应的箱子里，然后依序将各箱子首尾相接，就得到了按点数整序排列的一副牌。

6.3 基数排序

多关键字排序：
以一副扑克的排序为例，规定花色与面值顺序为

• 花色：梅花 < 方块 < 红桃 < 黑桃
• 面值：A<2<3<···<10<J<Q<K

并规定花色的优先级高于面值

高位优先排序法

先按花色分成有序的四类，然后再按面值对每一类从小到大排序。该方法称为"高位优先"排序法

低位优先排序法

分配与收集交替进行，首先按面值从小到大牌成13堆（每个4张牌），再对这些牌按花色收集成4堆（每堆13张牌），这样按花色色号的次序收集到一起

链式基数排序

算法思想：
按最低位的值对记录进行初步排序，在此基础上再按次低位的值进行一步排序。依此类推，由低位到高位逐位排序，直至最高位。

void RadixSort(RecordType r[], int length) {
    n = length;
    for (i = 0; i <= n-1; ++i)
        r[i].next = i+1;
    d = keynum;
    for (i = d-1; i >= 0; --i) {
        Distribute(r, i, head, tail);
        Collect(r, head, tail);
    }
}

一趟分配算法

void Distribute(RecordType1 r[], int i, PVector head, PVector tail) {
    for (j = 0; j <= RADIX-1; ++j)
        head[j] = 0;
    p = r[0].next;
    while(p != 0) {
        j = Order(r[p], key[i]);
        if (head[j] == 0) head[j] = p;
        else r[tail[j]].next = p;
        tail[j] = p;
        p = r[p].next;
    }
}

一趟收集算法

void Collect(RecordType r[], PVector head, PVector tail) {
    j = 0;
    while(head[j] == 0) ++j;
    r[0].next = head[j]; t = tail[j];
    while (j < RADIX-1) {
        ++j;
        while (j < RADIX-1 && (head[j] == 0)) ++j;
        if (head[j] = 0) {
            t = head[j]; t = tail[j];
        }
        else r[t].next = head[j]; t = tail[j];
    }
    r[t].next = 0;
}

性能分析

n个记录，每个记录含d个关键字，每个关键字的取值范围为d个值。

链式基数排序——

时间复杂度：共d趟分配收集，每趟分配时间复杂度为n，收集时间复杂度为0®

故，T(n) = O(d(n+R))*

空间复杂度：需要2×R个列指针+n个指针域空间。

故，S(n) = O(R+n)

7. 排序算法总结

算法设计

在单链表结构上

◆ 实现冒泡（或简单选择、直接插入）排序。
◆ 给定一个数组，判断其是否构成小根堆。
◆ 给定一个数组，将其调整为小根堆。
◆ 设计算法，在某无序整型数组中，寻找第k小元素。

分治求解：快速排序思想

对于序列a[s…t]，在其中查找第k小元素的过程如下：

将a[s]作为基准划分，其对应下标为i. 3种情况：

➤ 若k=i，a[i]即为所求，返回a[i]。

➤ 若i>k，第k小的元素应在a[s…i-1]子序列中，递归在该子序列中求解并返回其结果。

➤ 若i<k，第k小的元素应在a[i+1…t]子序列中，递归在该子序列中求解并返回其结果。

快速选择算法实现

int QuickSelect(int a[], int s, int t, int k) {
    int i = s, j = t, tmp;
    if (s < t) {
        tmp = a[s];
        while (i != j) {
            while (j > i && a[j] >= tmp) j--;
            a[i] = a[j];
            while (i < j && a[i] <= tmp) i++;
            a[j] = a[i];
        }
        a[i] = tmp;
        
        if (k == i) return a[i];
        else if (i > k) return QuickSelect(a, s, i-1, k);
        else return QuickSelect(a, i+1, t, k-i);
    }
    else if (s == t && s == k)
        return a[k];
}

各种排序算法性能比较

适用场景总结

• 数据量较小：直接插入排序、简单选择排序
• 数据量较大：快速排序、堆排序、归并排序
• 数据基本有序：直接插入排序、冒泡排序
• 稳定性要求高：归并排序、基数排序
• 空间复杂度要求低：堆排序、希尔排序