第3章排序算法设计与分析
- 3.1 基本排序算法
- 3.2 进阶排序算法
  - 3.2.1 归并排序
  - 3.2.2 堆排序
include
include
include
- 3.2.4 希尔排序
3.3 线性时间排序算法
3.4 排序算法的应用
- 3.4.1 排序归约问题
  - 1、寻找不重复元素
  - 2、最大间隙问题
- 3.4.3 最优树的构造问题
  - 哈夫曼树

参考教材：《算法设计与应用》汪荣贵杨娟薛丽霞机械工业出版社

第3章排序算法设计与分析

用计算机解决实际问题，需要对问题进行抽象并建立相应的数学模型，将实际问题的求解转化为数学模型的求解。所有数学模型都建立在4中基本的数学结构基础之上。这4中结构分别为：

表示元素之间空间关系的拓扑结构。
表示元素之间运算关系的代数结构.
表示元素度量性质的测度结构。
表示元素之间次序关系的顺序结构。

排序算法以排序策略为标准，可分为插入排序、交换排序、选择排序、归并排序、计数排序等；以计算复杂度为标准，可将排序算法分为如下3中基本类型，即基本排序算法、进阶排序算法和线性时间排序算法。

3.1 基本排序算法

在本节中，讨论的时冒泡排序算法、插入排序算法和选择排序算法。

3.1.1 冒泡排序算法

基本原理：邻近的数字间两两比较，按照升序或者降序的顺序进行交换。这样一趟过后，最大或最小的数字被交换到了最后一位。然后从头开始，重复上述操作，知道在某趟冒泡处理中没有发生交换时结束。

// 冒泡排序算法
// 输入数组list及元素的个数
// 输出从小到大排好序的数组
// BubbleSort.h
using namespace std;
void swap(int &i, int &j){
    int tmp=j;
    j=i;
    i=tmp;
} 
void BubbleSort(int* list, int n){
    bool flag;
    for(int i=0;i<n-1;i++){
        flag=false;            //这一趟是否发生了交换的标识
        for(int j=0;j<n-i;j++){
            if(list[j-1]>list[j]){
                swap(list[j-1],list[j]);
                flag=true;        //这一趟发生了交换 
            }
        }
        // 如果某一趟没有发生交换，说明排序已经完成，结束算法
        if(flag==false) break; 
    }
}

//main.cpp
#include <iostream>
#include "BubbleSort.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
    int list[6]={2,8,5,7,1,6};
    BubbleSort(list,6);
    for(int i=0;i<6;i++){
        cout<<list[i]<<"\t";
    }
    return 0;
}

最优时间复杂度为O(n)，最坏时间复杂度O(n^2)

3.1.2 插入排序

常见的插入排序算法有：直接插入排序、折半插入排序、希尔排序等。

直接插入排序

基本思路：初始有序序列只有一个元素，之后每次将一个待排元素按其关键字的大小插入到已排序好的合适位置，知道无序序列中的所有元素全部插入到正确位置位置。

// 直接插入排序算法
// 输入：数组list的各个元素及数组元素的个数n
// 输出：从小到大排好序的数组
#include <iostream>
using namespace std; 
void InsertSort(int list[], int n){
    for(int i=1;i<n;i++){
        int key = list[i];
        //从后往前比较
        //注意这里的细节j>=-1，否则list[0]一直不能被更新 
        for(int j=i-1;j>=-1;j--){
            //寻找插入位置
            if(key<list[j]) {
                list[j+1]=list[j];    //向后移动元素 
            }else{
                //找到插入位置插入元素
                list[j+1]=key;
                break; 
            }
//            if(j==0&&key<list[0]){
//                list[0]=key;
//            }
        } 
    }
} 
int main(){
    int list[5]={2,1,3,4,0};
    InsertSort(list,5);
    for(int i=0;i<5;i++){
        cout<<list[i]<<"   ";
    }
    return 0;
}

最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n^2)

折半插入排序

折半插入排序，是对直接插入排序的一种改进。不同之处在于，对于前半部分已经排序好的数列，不需要像直接插入排序那样按顺序依次寻找插入点，而是采用折半查找的方式来寻找插入点，速度相较于直接插入排序较快。

// 折半插入排序算法
// 输入：数组L的各个元素及数组元素的个数n
// 输出：从小到大排好序的数组
void BInsertSort(int *L, int n) {
    //对顺序表L做折半插入排序
    int i, j, high, low, mid;
    for (i = 1; i < n; i++) {
        int temp = L[i];
        low = 0;
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (temp < L[mid]) {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        for (j = i - 1; j >= high + 1; j--) {
            L[j + 1] = L[j];
        }
        L[high + 1] = temp;
    }
}

3.1.3 选择排序

选择排序基本思想如下：每一趟从待排序列选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，如此反复执行，知道所有待排序元素都完成排序。

常见的选择排序算法有：直接选择排序、树形选择排序、堆排序。

直接选择排序

基本思路：首先从L[0]~L[n-1]中找到最小的值，然后与L[0]交换位置，… ，第i次从
L[i-1]~L[n-1]中找到最小值，与L[i-1]交换， … ，直至所有元素均完成排序。

// 直接选择排序算法
// 输入：数组L及数组元素的个数
// 输出：从小到大排好序的数组
void SelectSort(int L[], int n) {
    int min;        // min 记录当前最小的关键字
    int index;        // index 记录当前最小关键字的索引
    int temp;
    for (int i = 0; i < n - 1; i++) {
        min = L[i];
        index = i;
        for (int j = i + 1; j < n; j++) {
            if (L[j] < min) {
                min = L[i];
                index = j;
            }
        }
        //待排元素与最小关键字交换
        if (index != i) {
            temp = L[i];
            L[i] = L[index];
            L[index] = temp;
        }
    }
}

直接选择排序是对冒泡排序的一种改进。
直接选择排序是一种不稳定的排序算法，因为在排序是，不相邻的两个元素有可能发生交换，因而会改变想等元素的前、后相对位置。
直接选择排序的时间复杂度为O(n^2)

树形选择排序

事实上，在直接选择排序中，每趟的比较结果可以进一步为后续比较提供额外的信息，使后续的比较次数大大减少。属性选择排序正是利用了这点，具体做法如下：
首先将待排序记录两两分组（任意分组都可），将每组的最小值设置为它们的父结点。之后把所有这些筛选出来的父结点再两两分组，选出每组的最小值并设置为这组的父结点。一层一层筛选，知道选出根结点，即为最小值。
输出最小值之后，再根据顺序关系的可传递性，利用上次比较的结果，从被最小元素打败的结点选出次最小值。具体方法如下：将叶子结点中已输出的最小值改为INT_MAX（无穷大），然后从该位置的叶子节点开始，和其左右兄弟的值进行比较，根据比较的结果修改从叶子节点到根结点路径上各结点的值。修改结束后，则根结点的值即为次小值。以此类推，依次选出从小到大的所有元素值。

// 树形选择排序算法
// 输入：初始序列
// 输出：树形选择排序后的结果
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
//树的结构
struct BinaryTreeNode {
    bool from;        //判断来源，左true，右false
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
//构建叶子节点
BinaryTreeNode* buildList(const vector<int>& L) {
    BinaryTreeNode* btnList = new BinaryTreeNode[L.size()];
    for (int i = 0; i < L.size(); ++i) {
        btnList[i].from = true;
        btnList[i].m_nValue = L[i];
        btnList[i].m_pLeft = NULL;
        btnList[i].m_pRight = NULL;
    }
    return btnList;
}
//不足偶数时，需补充结点
BinaryTreeNode* addMaxNode(BinaryTreeNode* list, int n) {
    //最大结点
    BinaryTreeNode* maxNode = new BinaryTreeNode();        //最大结点，用于填充
    maxNode->from = true;
    maxNode->m_nValue = INT_MAX;
    maxNode->m_pLeft = NULL;
    maxNode->m_pRight = NULL;
    //复制数组
    BinaryTreeNode* childNodes = new BinaryTreeNode[n + 1];        //增加一个结点
    for (int i = 0; i < n; i++) {
        childNodes[i].from = (list+i)->from;
        childNodes[i].m_nValue = (list + i)->m_nValue;
        //cout << childNodes[i].m_nValue << endl;
        childNodes[i].m_pLeft = (list + i)->m_pLeft;
        childNodes[i].m_pRight = (list + i)->m_pRight;
    }
    childNodes[n] = *maxNode;
    delete[] list;
    list = NULL;
    return childNodes;
}
//根据左、右子树大小，创建树
BinaryTreeNode* buildTree(BinaryTreeNode* childNodes, int n) {
    if (n == 1) {
        return childNodes;
    }
    if (n % 2 == 1) {
        childNodes = addMaxNode(childNodes, n);
    }
    //创建叶子结点的父结点
    int num = n / 2 + n % 2;
    BinaryTreeNode* btnList = new BinaryTreeNode[num];
    for (int i = 0; i < num; i++) {
        btnList[i].m_pLeft = &childNodes[2 * i];
        btnList[i].m_pRight = &childNodes[2 * i + 1];
        bool less = btnList[i].m_pLeft->m_nValue <= btnList[i].m_pRight->m_nValue;
        btnList[i].from = less;
        btnList[i].m_nValue = less ? btnList[i].m_pLeft->m_nValue : btnList[i].m_pRight->m_nValue;
        //cout << btnList[i].m_nValue << "\t";
    }
    //cout << endl;
    return buildTree(btnList, num);
}
//返回树根，重新计算树
int rebuildTree(BinaryTreeNode* tree) {
    int result = tree[0].m_nValue;
    stack<BinaryTreeNode*> nodes;
    BinaryTreeNode* node = &tree[0];
    nodes.push(node);
    while (node->m_pLeft != NULL) {
        node = node->from ? node->m_pLeft : node->m_pRight;
        nodes.push(node);
    }
    node->m_nValue = INT_MAX;
    nodes.pop();
    while (!nodes.empty()) {
        node = nodes.top();
        nodes.pop();
        bool less = node->m_pLeft->m_nValue <= node->m_pRight->m_nValue;
        node->from = less;
        node->m_nValue = less ? node->m_pLeft->m_nValue : node->m_pRight->m_nValue;
    }
    return result;
}
//从上到下打印树
void printTree(BinaryTreeNode* tree) {
    BinaryTreeNode* node = &tree[0];
    queue<BinaryTreeNode*> temp1;
    queue<BinaryTreeNode*> temp2;
    temp1.push(node);
    while (!temp1.empty()) {
        node = temp1.front();
        if (node->m_pLeft != NULL && node->m_pRight != NULL) {
            temp2.push(node->m_pLeft);
            temp2.push(node->m_pRight);
        }
        temp1.pop();
        if (node->m_nValue == INT_MAX) {
            cout << "MAX" << "  ";
        }
        else {
            cout << node->m_nValue << "  ";
        }
        if (temp1.empty()) {
            cout << endl;
            temp1 = temp2;
            queue<BinaryTreeNode*> empty;
            swap(temp2, empty);
        }
    }
}

时间复杂度为O(nlogn)

3.2 进阶排序算法

3.2.1 归并排序

归并排序有分解和合并两个基本步骤组成。归并排序首先将待排序列分割成若干个互不相交的、元素数目很少的子序列。如当子序列的长度为1的时候就意味着已经排好序。因此归并排序的关键在于如何将已有序的子序列进行合并，得到完全有序的序列。可参照两有序数组合并算法。


#include <iostream>
#include <cstddef>
//将两个有序数列a[low,...,mid]和a[mid+1,...,high]合并成一个升序序列
void MergeArray(int a[], int low, int mid, int high, int temp[]) {
    //两个子序列的开始位置和结束位置
    int i = low;
    int j = mid + 1;
    int m = mid;
    int n = high;
    //新数组的开始位置
    int k = 0;
    while (i <= m && j <= n) {
        //分别从两个子序列的开始处进行比较，将两个子序列中较小的元素插入到新数组中
        if (a[i] < a[j]) {
            temp[k++] = a[i++];
        }
        else {
            temp[k++] = a[j++];
        }
    }
    //检查两个子序列里是否有剩余元素，如果有，则将该子序列中的剩余元素插入到新数组的末端
    while (i <= m) {
        temp[k++] = a[i++];
    }
    while (j <= n) {
        temp[k++] = a[j++];
    }
    // 此时k=n，将归并排序结果temp[0,...,n-1]替换到原始的数组a[low,...,high]中
    for (int i = 0; i < k; i++) {
        a[low + i] = temp[i];
    }
}
//归并排序算法，使用递归实现
void mergesort(int a[], int low, int high, int temp[]) {
    if (low < high) {
        int mid = (low + high) / 2;        //将原始数组一分为二
        mergesort(a, low, mid, temp);    //对A[low,...,mid]排序
        mergesort(a, mid + 1, high, temp);        //对A[mid+1,...,high]排序
        //对a[low,...,high]排序
        MergeArray(a, low, mid, high, temp);
    }
}
// 归并排序算法
bool MergeSort(int a[], int n) {
    int* p = new int[n];        // 申请内存空间
    if (p == NULL) {
        return false;
    }
    mergesort(a, 0, n - 1, p);
    delete[] p;
    return true;
}
int main() {
    int list[8] = { 4,3,8,5,1,6,4,9 };
    MergeSort(list, 8);
    for (int i = 0; i < 8; i++) {
        std::cout << list[i] << "\t";
    }
    return 0;
}
int main() {
    vector<int> list = { 49,38,65,97,76,13,27,49 };
    BinaryTreeNode* T = buildTree(buildList(list), list.size());
    printTree(T);
    return 0;
}

归并排序算法的时间复杂度为O(nlogn)

3.2.2 堆排序

堆排序使用一种称之为堆的数据来存储结构。堆的概念：n个元素的序列K，K，…，K称为堆。
当且仅当该序列满足如下性质：K<=K且K<=K（1<=i<=n/2,2i+1<=n）
其中，K相当于二叉树的非叶子结点，K是左孩子结点，K是右孩子结点。这叫小根堆，大根堆则将“<=”换成“>=”即可。
事实上，堆是一颗完全二叉树，且满足如下几个基本性质：

堆中的数据基于一棵完全二叉树的顺序存储，K是该树根节点，K是完全二叉树的第i个结点。如果该完全二叉树的高度为h，那么叶子节点在h层或h-1层，且h层所有的结点都连续集中在最左边。
对于小根堆来说，结点的所有与后代相关的数据都大于该结点上的数据，根结点K是数组的最小值；对于大根堆来说，结点的所有与后代相关的数据都小于该结点上的数据，根结点K是数组的最大值
二叉树左、右孩子之间没有绝对的大小关系，且堆的任意一棵子树也是堆。

下面以大根堆为例，介绍堆排序算法：

讲初始数组R[0],R[1],…,R[n-1]，建成一个大根堆，此堆为初始的无序区。
将值最大的结点R[0]（堆顶）和无序区的最后一个结点R[n-1]交换，得到新的无序区R[0],R[1],…,R[n-2]和有序区R[n-1]，满足R[0],R[1],…,R[n-2]<=R[n-1]
由于交换后的根节点R[0]可能不满足堆的特性，因此需对无序区R[0],R[1],…,R[n-2]在进行依次建堆，建堆后，将无序区R[0],R[1],…,R[n-2]中值最大的根结点R[0]与该无序区的最后一个结点R[n-2]交换，得到新的无序区R[0],R[1],…,R[n-3]和有序区R[n-2]、R[n-1]，同样也满足R[0],R[1],…,R[n-3]<=R[n-2]、R[n-1]。如此下去，直到无序区只剩下最后一个元素为止。 ```cpp // 堆排序算法 // 输入：数组A及数组元素的个数n // 输出：堆排序后的结果

include

using namespace std;

void swap(int& a, int& b) { int temp = a; a = b; b = a; }

void maxHeap(int array[], int i, int n) { int left = 2 i + 1, right = 2 i + 2; int max = i; if (left < n && array[max] < array[left]) max = left; if (right < n && array[max] < array[right]) max = right; if (max != i) { int temp = array[max]; array[max]=array[i]; array[i]=temp; maxHeap(array, max, n); } }

void heapSort(int array[], int n) { for (int i = n / 2 - 1; i >= 0; i—) maxHeap(array, i, n); for (int i = n - 1; i >= 0; i—) { int temp=array[0]; array[0]=array[i]; array[i]=temp; maxHeap(array, 0, i); } for (int i = n - 1; i >= 0; i—) { cout<<array[i]<<” “; } }

int main() { int list[8] = { 49,65,97,52,76,38,13,26 }; heapSort(list, 8);

return 0;

}

时间复杂度O(nlogn)
<a name="0PhbN"></a>
### 3.2.3 快速排序
快速排序是一种基于分治模式的递归式排序算法，它有一个问题分解的标准。在快速排序中，这个分解的标准为选主元。快速排序算法通过与主元比较的方式实现问题的分解，将数组划分成为两个子序列，其中一个子序列中的元素均小于或等于主元，另外一个子序列中的元素均大于住院。
现对数组A[s...t]进行快速排序，基本步骤如下：
1. 如果A中的元素为0个或者1个，此时认为数组A是已经排好序的，则返回。
1. 选取主元A[q]，其中s<=q<=t。
1. 将数组划分成两个集合A（所有小于或者等于A[q]的关键字集合），A（所有大于或者等于A[q]的关键字集合）。
1. 分别对AA进行划分
```cpp
// 快速排序算法 
// 输入：无序数组A[0,...,n-1]，s=0,t=n-1 
// 输出： 快速排序结果
#include <iostream>
using namespace std;
int Partition(int v[],int s,int t){
    //选择“主元”，申请辅助内存单元
    int key = v[s];
    //设立low，high为划分时序列的左右边界
    int low = s;
    int high = t;
    while(low<high){
        while(low<high&&v[high]>key){
            //把大于“主元”的关键字留在右边的子序列
            high--;        //指向前一个位置 
        }
        // 在右边子序列中，发现较小的关键字则移到左边的子序列中 
        if(low<high){
            v[low]=v[high];
            low++;
        } 
        while(low<high&&v[low]<key){
            // 把小于“主元”的关键字留在左边的子序列
            low++;        //指向后一个位置 
        }
        // 在左边子序列中，发现较大的关键字则移到右边的子序列中 
        if(low<high){
            v[high]=v[low];
            high--;
        } 
    }
    v[low]=key;        //把主元放在合适的位置
    return low;  
} 
void QuickSort(int A[],int s,int t){
    if(s<t){
        int i = Partition(A,s,t);
        QuickSort(A,s,i-1);
        QuickSort(A,i+1,t);
    }
}
int main(){
    int array[7]={27,31,12,18,54,45,28};
    QuickSort(array,0,6);
    for(int i=0;i<7;i++){
        cout<<array[i]<<"  ";
    } 
    return 0;
}

快速排序的最坏时间为O(n^2)，但就平均性能而言，它是基于元素比较的内部排序算法中速度最快者，其平均时间复杂度为O(nlogn)。快速排序在大多数情况下都表现为O(nlogn)，所以我们在选取主元的时候往往是随机选取的，这样快速排序更有可能表现出更好的性能。

3.2.4 希尔排序

希尔排序，亦称为缩小增量排序，是对直接插入排序的一种改进。

基本思想：首先将待排序列分组，在每组内进行直接插入排序，使得整个序列基本有序，然后对整个序列进行插入排序，完成对整个序列的排序。

// 希尔排序算法
// 输入：数组list及数组元素
// 输出：希尔排序后的结果
#include <iostream>
void ShellSort(int list[],int n){
    int i,j,d;
    for(d=n/2;d>=1;d/=2){
        //d为步长
        for(i=d;i<n;i++){
            // 从数组下标为d的元素开始
            // 数组内的元素直接进入插入排序
            for(j=i-d;j>=0&&list[j]>list[j+d];j-=d){
                //交换
                int temp = list[j];
                list[j]=list[j+d];
                list[j+d]=temp; 
            } 
        } 
    }
} 
int main(){
    int list[10]={49,38,49,97,76,13,27,91,55,4};
    ShellSort(list,10);
    for(int i=0;i<10;i++){
        std::cout<<list[i]<<"  ";
    }
    return 0;
}

时间复杂度为O(nlogn)

3.3 线性时间排序算法

本节介绍3中线性时间排序算法，如计数排序、桶排序和基数排序，其数据本身包含了定位特征，不用通过比较确定元素的位置，因而可以突破下界O(nlogn)，但都需要额外的空间开销，其实就是以牺牲额外的空间开销，其实就是以牺牲空间性能来换取时间性能。

3.3.1 计数排序

计数排序针对已知数量范围的数组进行排序，它通过计算一个集合中元素出现的次数来确定次序，是一种基于非比较的排序算法，效率高且稳定性好，使用于小范围集合排序。

// 计数排序算法
// 输入：待排序数组A，存储排序后的数组B，数组A的大小len，数组C的大小k
// 输出：计数排序好的结果
#include <iostream>
using namespace std;
void CountingSort(int A[],int B[],int len,int k){
    int *CountArr = new int[k];
    int i;
    //初始化数组C
    for(i=0;i<k;i++){
        CountArr[i]=0;
    } 
    //对数组A中元素出现的次数做统计
    for(int i=0;i<len;i++){
        CountArr[A[i]]++;
    } 
    //对C进行累加，得到位置信息
    for(i=1;i<k;i++){
        CountArr[i]+=CountArr[i-1];
    } 
    //使用位置信息顺序重组数组
    //从右至左保证算法的稳定性
    for(i=len-1;i>=0;i--){
        B[CountArr[A[i]]-1]=A[i];
        CountArr[A[i]]--;
    } 
} 
int main(){
    int list[7]={1,0,3,1,0,1,1};
    int res[7];
    CountingSort(list,res,7,4);
    for(int i=0;i<7;i++){
        cout<<res[i]<<"  ";
    }
    return 0;
}

时间复杂度为O(n)

3.3.2 桶排序

桶排序算法将所有待排元素（按照某种映射规则）分配到若干容量较小的有序单元（桶）中，由于各个桶之间是有序的，因此原排序问题就转化为分别对各桶中元素的排序。

// 桶排序算法
// 输入：数组a的各个元素及数组与元素的个数len
// 输出：桶排序后的结果
#include <iostream>
using namespace std;
const int arrange = 10;
//对桶排序的每趟使用冒泡算法
class Bucket {    //定义桶对象
public:
    float d;
    Bucket* next;
    Bucket() { this->d = 0, next = NULL; }
    Bucket(float d) {
        this->d = d;
        next = NULL;
    }
}bucket[10];
void link_bubble_sort(Bucket* buck) {
    float s;
    for (Bucket* p = buck; p->next != NULL; p = p->next) {
        for (Bucket* q = buck; q->next->next != NULL; q = q->next) {
            if (q->next->d > q->next->next->d) {
                s = q->next->next->d;
                q->next->next->d = q->next->d;
                q->next->d = s;
            }
        }
    }
}
//桶排序
void bucket_sort(float* a, int len) {
    //分桶
    for (int i = 0; i < len; i++) {
        Bucket* p;
        for (p = &bucket[int(a[i] / 10)]; p->next != NULL; p = p->next) {}
        p->next = new Bucket(a[i]);
    }
    //按照桶的方式输出桶内的数据
    //for (int k = 0; k < arrange; k++) {
    //    for (Bucket* q = &bucket[k]; q->next != NULL; q = q->next) {
    //        cout << q->next->d << "   ";
    //    }
    //    cout << endl;
    //}
    //对每个桶内进行排序
    for (int j = 0; j < len; j++) {
        link_bubble_sort(&bucket[j]);
    }
    for (int k = 0; k < len; k++) {
        for (Bucket* q = &bucket[k]; q->next != NULL; q = q->next) {
            cout << q->next->d << "   ";
        }
    }
    cout << endl;
}
int main() {
    float a[8] = { 46,33,95,6,64,44,60,58 };
    bucket_sort(a, 8);
    return 0;
}

对于N个待排数据、M个桶，排序平均时间复杂度为：O(N+NlogN-NlogM)
桶排序的平均时间复杂度为线性的O(N+C)，其中：C=N*(logN-logM)
通过对表达式的分析，我们可以知道最好的时间复杂度将达到O(N)，空间复杂度为O(N+M)

3.3.3 基数排序

基数排序是另一种高效的线性时间算法，该方法首先将所有待排元素统一成同样的位数长度，位数较短的数前面补零，然后将数据按位分开，从数据的最低有效位到最高有效位进行比较，依次排序，从而得到有序序列。基数排序可以采用最低有效位优先（LSD）或最高有效位优先（MSD）。基数排序是一种稳定的排序算法，事实上，只要能把元素分割成整型数，就可以应用基数排序

// Basic_sort.cpp
// 基数排序算法
// 输入：待排序数组arr，数组元素个数len，基数k，位的个数d
// 输出：基数排序后的结果
#include <iostream>
/* 基数排序后的顺序为从小到大
* arr[0,..,len-1]为待排数组，这里采用三位数
* brr[0,..,len-1]为排序后的有序数组
* w[0,..len-1]用来保存去除的每一位上的数，其每个元素均是0~k中的一个值
* crr[0,...,k]保存0,...,k中每个值出现的次数
*/
void Count_sort(int* arr, int* brr, int* w, int* crr, int len, int k) {
    int i;
    //将数组crr中的各元素置为0
    for (i = 0; i < k; i++)
        crr[i] = 0;
    //统计数组w中每个元素重复出现的个数
    for (i = 0; i < len; i++) {
        crr[w[i]]++;
    }
    //求数组w中小于等于i的元素个数
    for (i = 1; i <= k; i++) {
        crr[i] += crr[i - 1];
    }
    //把数组arr中的元素放在数组brr中的对应的位置上
    for (i = len - 1; i >= 0; i--) {
        brr[crr[w[i]] - 1] = arr[i];
        //如果有相同的元素，则放在下一个位置上
        crr[w[i]]--;
    }
    //再将数组brr中的元素复制给数组arr，这样数组arr就有序了
    for (i = 0; i < len; i++) {
        arr[i] = brr[i];
    }
}
//基数排序后的顺序为从小到大，其中参数d为元素的位数
void Basic_Sort(int* arr, int* brr, int* w, int* crr, int len, int k,int d) {
    int i, j, val = 1;
    //从低位到高位依次进行基数排序
    for (i = 1; i <= d; i++) {
        //w中保存的是数组arr中每个元素对应位上的数
        //范围在0~k之间
        for (j = 0; j < len; j++) {
            w[j] = (arr[j] / val) % 10;
        }
        //对当前位进行基数排序
        Count_sort(arr, brr, w, crr, len, k);
        val *= 10;
    }
}
int main() {
    const int len = 6;
    const int d = 3;
    const int k = 9;
    int list[len] = { 323,266,652,101,425,067 };
    int brr[len], w[len], crr[k];
    Basic_Sort(list, brr, w, crr, len, k, d);
    for (int i = 0; i < len; i++) {
        std::cout << list[i] << "   ";
    }
    return 0;
}

时间复杂度为O(dn+dk)

3.4 排序算法的应用

3.4.1 排序归约问题

所谓归约，是指解决某个问题而发明的算法正好可以用来解决另外一个问题。当使用问题B的方法来解决问题A时，其实就是将问题A归纳为问题B。

1、寻找不重复元素

在n个元素的数组A中，有多少个不重复的元素？可以先将元素进行排序，之后借助元素的次序关系解决此问题。

// 寻找不重复元素算法
// 输入：无序序列
// 输出：不重复元素的个数
// 具体算法如下：
QuickSort(A);
int count = 1;  //假设A.length()>0
for(int i=0;i<A.length();i++){
    if(A[i].compareTo(A[i+1])){
        //排序后若相邻两元素不相等，则执行下面语句
        count++;
    }
}
cout<<"不重复元素的个数："<<endl;

2、最大间隙问题

给定n个实数a，a，…，a，试求这n个实数在实数轴上相邻两个数之间的最大差值的问题，即最大间隙问题。
基本方法如下：

找出n个元素中最大和最小元素max，min，将区间[min, max]划分为等长的n-1个子区间：[min, min+len) , [min+len, min+2*len), … , (max-len, max]，每个子区间看成1个桶，用len表示每个子区间的长度，即len=(max-min)/(n-1)，此时最大间隙maxGap>=len
将n个数放入n-1个桶，每个数都属于其中一个桶。由于同时半开半闭的，因此对于同一个桶的两个数，桶内元素间的距离肯定小于len。
求解最大间隙。除最大和最小数据max和min以外的n-2个数据被放入n-1个桶中，由抽屉原理可知，至少有一个桶是空的。所以距离最远的相邻的两个数，肯定是属于两个不同的桶。于是，我们可以把每个桶都扫描一次，相邻最远的两个数，必定其中一个是某个桶里的最大值，另一个时另一个桶里的最小值。
3.4.3 最优树的构造问题
哈夫曼树
最优树又称为霍夫曼树（Huffman Tree）或哈夫曼树，是一种带权二叉树，权值越大的叶子结点里根结点越近，权值越小的叶子结点离根结点越远，具有带权路径最短的特点。

哈夫曼树具体构造方法如下：
首先，从n个元素的数组中取出两个权值最小的结点，对它们进行合并，并将合并后的新结点作为这两个结点的父结点，新结点的权值为两个被合并结点的权值的和。然后，从数组中删除这两个被合并的元素，并将合并后的新结点加入到数组中。如此下去，知道数组中只剩下一个元素位置，最终形成一课带权二叉树，即为所求的霍夫曼树。

// 霍夫曼树的构造算法
// 输入：每个叶子结点的权值
// 输出：合并后的霍夫曼树的所有结点
#include <iostream>
using namespace std;
const int n = 5;
const int m = 2 * n - 1;
const int float_max = 20;
typedef int datatype;
typedef struct {
    float weight;        //定义权重
    int parent;        //定义双亲结点在向量中的下标
    int lchild, rchild;        //定义左、右子树
}nodetype;
typedef nodetype hftree[m];        //霍夫曼树类型，数组从0号单元开始使用
hftree T;            // 霍夫曼树向量
// 霍夫曼树的构造
void huffman(hftree T,int list[],int size) {
    int i, j, p1, p2;
    float small1, small2;
    for (i = 0; i < n; i++) {        //初始化
        T[i].parent = -1;    //    无双亲，即为根结点，尚未合并过
        T[i].lchild = T[i].rchild = -1;        //左、右孩子指针置为-1
    }
    for (i = 0; i < size; i++) {
        T[i].weight = list[i];        //输入n个叶子结点的权
    }
    for (i = n; i < m; i++) {
        //进行n-1次合并，产生n-1个新结点
        p1 = p2 = -1;
        small1 = small2 = float_max;
        //float_max为float类型的最大值
        for (j = 0; j <= i-1; j++) {
            //不考虑已合并过的结点
            if (T[j].parent != -1)continue;
            //修改最小权及位置
            if (T[j].weight < small1) {
                small2 = small1;
                small1 = T[j].weight;
                p2 = p1;
                p1 = j;
            }
            else if (T[j].weight < small2) {
                //修改次小权及位置
                small2 = T[j].weight;
                p2 = j;
            }
        }
        //新根
        T[p1].parent = T[p2].parent = i;
        T[i].parent = -1;
        T[i].lchild = p1;
        T[i].rchild = p2;
        T[i].weight = small1 + small2;
        cout << small1 << "   " << small2 << endl;
        cout << "p1: " << p1 << "   p2:" << p2 << "    T[" << i << "].weight:" << T[i].weight << endl;
    }
}
int main() {
    int list[n] = { 12,3,8,5,2 };
    huffman(T, list, n);
    for (int i = 0; i < m; i++) {
        cout << T[i].weight << "  ";
    }
    return 0;
}

C++

第3章 排序算法设计与分析

第3章 排序算法设计与分析

3.1 基本排序算法

3.1.1 冒泡排序算法

3.1.2 插入排序

直接插入排序

折半插入排序

3.1.3 选择排序

直接选择排序

树形选择排序

3.2 进阶排序算法

3.2.1 归并排序

3.2.2 堆排序

include

include

include

3.2.4 希尔排序

3.3 线性时间排序算法

3.3.1 计数排序

3.3.2 桶排序

3.3.3 基数排序

3.4 排序算法的应用

3.4.1 排序归约问题

1、寻找不重复元素

2、最大间隙问题

3.4.3 最优树的构造问题

哈夫曼树

第3章排序算法设计与分析

第3章排序算法设计与分析