C语言——十四种内部排序算法【插入排序 希尔插入 折半二分插入 二路插入 表插入排序 简单选择排序 直接选择 树形选择插入 堆排序 冒泡 快速 归并排序 基数排序 计数排序 桶排序】

文章目录：

一：插入排序

1.直接插入排序

算法演示

2.希尔排序

算法演示

3.折半插入排序（二分查找）

图解 

4.二路插入排序

算法演示

5.表插入排序

算法演示

二：选择排序

1.简单选择排序

算法演示

2.直接选择排序 

算法演示

3.树形选择排序（锦标赛排序）

算法演示

4.堆排序

算法演示

三：交换排序

1.冒泡排序

算法演示

2.快速排序

算法演示

四：归并排序

算法演示

五：基数排序

1.多关键字的排序

高优先级排序MSD

低优先级排序LSD

2.链式基数排序

六：补充两种排序

1.计数排序

动图演示

2.桶排序

示意图

七：总结

---

腾讯视频演示地址：14种排序算法动画演示让你直观感受

 

一：插入排序

1.直接插入排序

定义

插入排序（英语：Insertion Sort）是一种简单直观的排序算法

它的工作原理是通过构建有序序列

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

插入排序在实现上，通常采用in-place排序（即只需用到 {\displaystyle O(1)} {\displaystyle O(1)}的额外空间的排序）

因而在从后向前扫描过程中，需要反复把已排序元素逐步向后

挪位，为最新元素提供插入空间 

算法演示

 基本思想

将一个记录插入到已安排好序的序列中，从而得到一个新的有序序列将序列的第一个数据看成是一个有序的子序列然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序

 

import java.util.Arrays;public class Sort {public static void main(String[] args) {int arr[] = {2,1,5,3,6,4,9,8,7};int temp;for (int i=1;i<arr.length;i++){//待排元素小于有序序列的最后一个元素时，向前插入if (arr[i]<arr[i-1]){temp = arr[i];for (int j=i;j>=0;j--){if (j>0 && arr[j-1]>temp) {arr[j]=arr[j-1];}else {arr[j]=temp;break;}}}}System.out.println(Arrays.toString(arr));

2.希尔排序

定义

希尔排序，也称递减增量排序算法

是插入排序的一种更高效的改进版本

希尔排序是非稳定排序算法

算法演示

 

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动

void shell_sort(int arr[], int len) {int gap, i, j;int temp;for (gap = len >> 1; gap > 0; gap = gap >> 1)for (i = gap; i < len; i++) {temp = arr[i];for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)arr[j + gap] = arr[j];arr[j + gap] = temp;}
}

3.折半插入排序（二分查找）

原理

折半插入算法是对直接插入排序算法的改进，排序原理同直接插入算法

先折半查找元素的应该插入的位置，

后统一移动应该移动的元素

再将这个元素插入到正确的位置

区别

在插入到已排序的数据时采用来折半查找（二分查找）

取已经排好序的数组的中间元素，与插入的数据进行比较

如果比插入的数据大，那么插入的数据肯定属于前半部分

否则属于后半部分

依次不断缩小范围，确定要插入的位置

int[] arr={5,2,6,0,9}

经行折半插入排序

public class BinaryInsertSort {public static void main(String[] args){int arr[] = { 5 , 2 , 6 , 0 , 9 };   //打印排序前的数据System.out.println("排序前的数据：");for (int i = 0; i < arr.length; i++) {            System.out.print(arr[i] + " ");}//直接插入排序binaryInsertSort(arr);//打印排序后的数据System.out.println();System.out.println("排序后的数据：");for (int i = 0; i < arr.length; i++) {            System.out.print(arr[i] + " ");}                }    private static void binaryInsertSort(int arr[]){int low,high,m,temp,i,j;for(i = 1;i<arr.length;i++){//折半查找应该插入的位置low = 0;high = i-1;while(low <= high){m = (low+high)/2;if(arr[m] > arr[i])high = m - 1;elselow = m + 1;}//统一移动元素，然后将这个元素插入到正确的位置temp = arr[i];for(j=i;j>high+1;j--){arr[j] = arr[j-1];}arr[high+1] = temp;}        }
}

结果： 

图解 

初始状态：设5为有序，其中i为1，即：5 2 0 6 9第一趟排序：low为0，high为0，则中间值下标为0（（low+high）/2，下文都是如此计算），即5大于2，则插入到5前面，然后i自增。即：2 5 6 0 9第二趟排序：low为0，high为1，则中间值下标为0，即2小于6，然后low等于中间值得下标加1，继续找中间值为5小于6，则插入到5后面，然后i自增。即：2 5 6 0 9第三趟排序：low为0，high为2，则中间值下标为1，即5大于0，然后high等于中间值得下标减1，继续找中间值为2大于0，则插入到2前面，然后i自增。即：0 2 5 6 9第四趟排序：low为0，high为3，则中间值下标为1，即2小于9，然后low等于中间值得下标加上1，继续找中间值为5小于9，然后low等于中间值得下标加上1，继续找中间值为6小于9，则插入到6后面，然后i自增，即：0 2 5 6 9最终的答案为：0 2 5 6 9

4.二路插入排序

定义

是在折半插入排序的基础上对其进行改进

减少其在排序过程中移动记录的次数从而提高效率

实现思路

设置一个同存储记录的数组大小相同的数组 d

将无序表中第一个记录添加进 d[0] 的位置上

然后从无序表中第二个记录开始

同 d[0] 作比较：如果该值比 d[0] 大，则添加到其右侧；反之添加到其左侧

在这里的数组 d 可以理解成一个环状数组

算法演示

使用 2-路插入排序算法对无序表{3,1,7,5,2,4,9,6}排序的过程如下：

1.将记录 3 添加到数组 d 中：

 2.然后将 1 插入到数组 d 中，如下图所示：

3.将记录 7 插入到数组 d 中，如下图所示：

4.将记录 5 插入到数组 d 中，由于其比 7小，但是比 3 大，所以需要移动 7 的位置

然后将 5 插入，如下图所示：

5.将记录 2 插入到数组 d 中，由于比 1大，比 3 小，所以需要移动 3、7、5 的位置

然后将 2 插入，如下图所示：

6.将记录 4 插入到数组 d 中，需要移动 5 和 7 的位置，如下图所示：

7.将记录 9 插入到数组 d 中，如下图所示：

8.将记录 6 插入到数组 d 中，如下图所示：

最终存储在原数组时，从 d[7] 开始依次存储

实例：2-路插入排序算法的具体实现代码为

#include <stdio.h>
#include <stdlib.h>
void insert(int arr[], int temp[], int n)
{int i,first,final,k;first = final = 0;//分别记录temp数组中最大值和最小值的位置temp[0] = arr[0];for (i = 1; i < n; i ++){// 待插入元素比最小的元素小if (arr[i] < temp[first]){first = (first - 1 + n) % n;temp[first] = arr[i];}// 待插入元素比最大元素大else if (arr[i] > temp[final]){final = (final + 1 + n) % n;temp[final] = arr[i];}// 插入元素比最小大，比最大小else {k = (final + 1 + n) % n;//当插入值比当前值小时，需要移动当前值的位置while (temp[((k - 1) + n) % n] > arr[i]) {temp[(k + n) % n] =temp[(k - 1 + n) % n];k = (k - 1 + n) % n;}//插入该值temp[(k + n) % n] = arr[i];//因为最大值的位置改变，所以需要实时更新final的位置final = (final + 1 + n) % n;}}// 将排序记录复制到原来的顺序表里for (k = 0; k < n; k ++) {arr[k] = temp[(first + k) % n];}
}int main()
{int a[8] = {3,1,7,5,2,4,9,6};int temp[8];insert(a,temp,8);for (int i = 0; i < 8; i ++){printf("%d ", a[i]);}return 0;
}

运行结果为 

1 2 3 4 5 6 7 9

5.表插入排序

引入

前面章节中所介绍到的三种插入排序算法，其基本结构都采用数组的形式进行存储

因而无法避免排序过程中产生的数据移动的问题

如果想要从根本上解决只能改变数据的存储结构，改用链表存储

定义

即使用链表的存储结构对数据进行插入排序

在对记录按照其关键字进行排序的过程中

不需要移动记录的存储位置

只需要更改结点间指针的指向

算法演示

将无序表{49，38，76，13，27}用表插入排序的方式进行排序，其过程为：

1.首先使存储 49 的结点与表头结点构成一个初始的循环链表，完成对链表的初始化，如下表所示：

2.然后将以 38 为关键字的记录插入到循环链表中（只需要更改其链表的 next 指针即可），插入后的链表为：

3.再将以 76 为关键字的结点插入到循环链表中，插入后的链表为:

4.再将以 13 为关键字的结点插入到循环链表中，插入后的链表为：

5.最后将以 27 为关键字的结点插入到循环链表中，插入后的链表为：

6.最终形成的循环链表为：

​时间复杂度​从表插入排序的实现过程上分析，与直接插入排序相比只是避免了移动记录的过程（修改各记录结点中的指针域即可）而插入过程中同其它关键字的比较次数并没有改变，所以表插入排序算法的时间复杂度仍是O(n2)​空间复杂度表插入排序的空间复杂度是插入排序的两倍
​

#define SIZE 100
typedef struct {int rc;//记录项int next;//指针项，由于在数组中，所以只需要记录下一个结点所在数组位置的下标即可。
}SLNode;
typedef struct {SLNode r[SIZE];//存储记录的链表int length;//记录当前链表长度
}SLinkListType;

在使用数组结构表示的链表中

设定数组下标为 0 的结点作为链表的表头结点

并令其关键字取最大整数

则表插入排序的具体实现过程是：

首先将链表中数组下标为 1 的结点和表头结点构成一个循环链表

然后将后序的所有结点按照其存储的关键字的大小

依次插入到循环链表中

二：选择排序

1.简单选择排序

定义

选择排序（Selection sort）是一种简单直观的排序算法

它的工作原理首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

然后，再从剩余未排序元素中继续寻找最小（大）元素

然后放到已排序序列的末尾

以此类推，直到所有元素均排序完毕

选择排序是一种不稳定的排序方式

算法演示

void swap(int *a,int *b) //交換兩個變數
{int temp = *a;*a = *b;*b = temp;
}
void selection_sort(int arr[], int len) 
{int i,j;for (i = 0 ; i < len - 1 ; i++) {int min = i;for (j = i + 1; j < len; j++)     //走訪未排序的元素if (arr[j] < arr[min])    //找到目前最小值min = j;    //紀錄最小值swap(&arr[min], &arr[i]);    //做交換}
}

 算法的实现思想

对于具有 n 个记录的无序表遍历 n-1 次

第 i 次从无序表中第 i 个记录开始

找出后序关键字中最小的记录

然后放置在第 i 的位置上

例如对无序表{56，12，80，91，20}采用简单选择排序算法进行排序，具体过程为：

1 第一次遍历时，从下标为 1 的位置即 56 开始，找出关键字值最小的记录 12，同下标为 0 的关键字 56 交换位置：

2 第二次遍历时，从下标为 2 的位置即 56 开始，找出最小值 20，同下标为 2 的关键字 56 互换位置：

3 第三次遍历时，从下标为 3 的位置即 80 开始，找出最小值 56，同下标为 3 的关键字 80 互换位置：

4 第四次遍历时，从下标为 4 的位置即 91 开始，找出最小是 80，同下标为 4 的关键字 91 互换位置：

到此简单选择排序算法完成，无序表变为有序表

简单选择排序的实现代码为：

#include <stdio.h>
#include <stdlib.h>
#define MAX 9
//单个记录的结构体
typedef struct {int key;
}SqNote;
//记录表的结构体
typedef struct {SqNote r[MAX];int length;
}SqList;
//交换两个记录的位置
void swap(SqNote *a,SqNote *b){int key=a->key;a->key=b->key;b->key=key;
}
//查找表中关键字的最小值
int SelectMinKey(SqList *L,int i){int min=i;//从下标为 i+1 开始，一直遍历至最后一个关键字，找到最小值所在的位置while (i+1<L->length) {if (L->r[min].key>L->r[i+1].key) {min=i+1;}i++;}return min;
}
//简单选择排序算法实现函数
void SelectSort(SqList * L){for (int i=0; i<L->length; i++) {//查找第 i 的位置所要放置的最小值的位置int j=SelectMinKey(L,i);//如果 j 和 i 不相等，说明最小值不在下标为 i 的位置，需要交换if (i!=j) {swap(&(L->r[i]),&(L->r[j]));}}
}
int main() {SqList * L=(SqList*)malloc(sizeof(SqList));L->length=8;L->r[0].key=49;L->r[1].key=38;L->r[2].key=65;L->r[3].key=97;L->r[4].key=76;L->r[5].key=13;L->r[6].key=27;L->r[7].key=49;SelectSort(L);for (int i=0; i<L->length; i++) {printf("%d ",L->r[i].key);}return 0;
}

运行结果 

13 27 38 49 49 65 76 97

2.直接选择排序 

定义

直接选择排序(Straight Select Sorting) 也是一种简单的排序方法

它的基本思想是：第一次从R[0]~R[n-1]中选取最小值

与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....

第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值

与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列

算法演示

例如:给定n=8，数组R中的8个元素的排序码为(8,3,2,1,7,4,6,5),则直接选择排序的过程如下所示

由于百科不方便画出关联箭头 所以用 n -- n 表示 ：

初始状态 [ 8 3 2 1 7 4 6 5 ] 8 -- 1
第一次 [ 1 3 2 8 7 4 6 5 ] 3 -- 2
第二次 [ 1 2 3 8 7 4 6 5 ] 3 -- 3
第三次 [ 1 2 3 8 7 4 6 5 ] 8 -- 4
第四次 [ 1 2 3 4 7 8 6 5 ] 7 -- 5
第五次 [ 1 2 3 4 5 8 6 7 ] 8 -- 6
第六次 [ 1 2 3 4 5 6 8 7 ] 8 -- 7
第七次 [ 1 2 3 4 5 6 7 8 ] 排序完成

// elemtype 为所需排序的类型void SelectSort(elemtype R[], int n) {int i, j, m;elemtype t;for (i = 0; i < n - 1; i++) {m = i;for (j = i + 1; j < n; j++)if (R[j] < R[m]) m = j;if (m != i) {t = R[i];R[i] = R[m];R[m] = t;}}
}

3.树形选择排序（锦标赛排序）

定义

树形选择排序又称锦标赛排序（Tournament Sort）

是一种按照锦标赛的思想进行选择排序的方法

首先对n个记录的关键字进行两两比较

然后在n/2个较小者之间再进行两两比较

如此重复，直至选出最小的记录为止

此方法在计算机运算中，是以程序命令体现完成，最后来达到理想的排序目的

算法演示

1 首先对n个记录的关键字进行两两比较

然后在其中[n/2]（向上取整）个较小者之间再进行两两比较

如此重复，直至选出最小关键字的记录为止

8个叶子结点中依次存放排序之前的8个关键字

每个非终端结点中的关键字均等于其左、右孩子结点中

较小的那个关键字，则根结点中的关键字为叶子结点中的最小关键字

在输出最小关键字之后

根据关系的可传递性

欲选出次小关键字，仅需将叶子结点中的最小关键字

2 改为“最大值”

然后从该叶子结点开始

和其左右兄弟的关键字进行比较

修改从叶子结点到根结点的路径上各结点的关键字

则根结点的关键字即为次小值

同理，可依次选出从小到大的所有关键字

#region "树形选择排序"
/// <summary>
/// 树形选择排序，Powered By 思念天灵
/// </summary>
/// <param name="mData">待排序的数组</param>
/// <returns>已排好序的数组</returns>
public int[] TreeSelectionSort(int[] mData)
{
int TreeLong = mData.Length * 4;
int MinValue = -10000;
int[] tree = new int[TreeLong]; // 树的大小
int baseSize;
int i;
int n = mData.Length;
int max;
int maxIndex;
int treeSize;
baseSize = 1;
while (baseSize < n)
{
baseSize *= 2;
}
treeSize = baseSize * 2 - 1;
for (i = 0; i < n; i++)
{
tree[treeSize - i] = mData[i];
}
for (; i < baseSize; i++)
{
tree[treeSize - i] = MinValue;
}
// 构造一棵树
for (i = treeSize; i > 1; i -= 2)
{
tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);
}
n -= 1;
while (n != -1)
{
max = tree[1];
mData[n--] = max;
maxIndex = treeSize;
while (tree[maxIndex] != max)
{
maxIndex--;
}
tree[maxIndex] = MinValue;
while (maxIndex > 1)
{
if (maxIndex % 2 == 0)
{
tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex] : tree[maxIndex + 1]);
}
else
{
tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex] : tree[maxIndex - 1]);
}
maxIndex /= 2;
}
}
return mData;
}
#endregion

4.堆排序

定义

堆 是具有下列性质的完全二叉树：

 堆排序（Heapsort）是指利用堆这种数据结构（后面的【图解数据结构】内容会讲解分析）所设计的一种排序算法

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：

即子结点的键值或索引总是小于（或者大于）它的父节点

堆排序可以说是一种利用堆的概念来排序的选择排序

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

算法演示

创建一个堆 H[0……n-1]把堆首（最大值）和堆尾互换把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置重复步骤 2，直到堆的尺寸为 1

1.首先，将所有的数字存储在堆中2.按大顶堆构建堆，其中大顶堆的一个特性是数据将被从大到小取出，将取出的数字按照相反的顺序进行排列，数字就完成了排序3.在这里数字 5 先入堆4.数字 2 入堆5.数字 7 入堆， 7 此时是最后一个节点，与最后一个非叶子节点（也就是数字 5 ）进行比较，由于 7 大于 5 ，所以 7 和 5 交互6.按照上述的操作将所有数字入堆，然后从左到右，从上到下进行调整，构造出大顶堆7.入堆完成之后，将堆顶元素取出，将末尾元素置于堆顶，重新调整结构，使其满足堆定义8.堆顶元素数字 7 取出，末尾元素数字 4 置于堆顶，为了维护好大顶堆的定义，最后一个非叶子节点数字 5 与 4 比较，而后交换两个数字的位置9.反复执行调整+交换步骤，直到整个序列有序

三：交换排序

1.冒泡排序

定义

冒泡排序（英语：Bubble Sort）是一种简单的排序算法

它重复地走访过要排序的数列，一次比较两个元素

如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来

冒泡排序是一种稳定的排序方式

算法演示

 

#include <stdio.h>
void bubble_sort(int arr[], int len) {int i, j, temp;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}
}
int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = (int) sizeof(arr) / sizeof(*arr);bubble_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}

2.快速排序

定义

在区间中随机挑选一个元素作基准

将小于基准的元素放在基准之前

大于基准的元素放在基准之后

再分别对小数区与大数区进行排序

算法演示

 

迭代法 

typedef struct _Range {int start, end;
} Range;
Range new_Range(int s, int e) {Range r;r.start = s;r.end = e;return r;
}
void swap(int *x, int *y) {int t = *x;*x = *y;*y = t;
}
void quick_sort(int arr[], const int len) {if (len <= 0)return; // 避免len等於負值時引發段錯誤（Segment Fault）// r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素Range r[len];int p = 0;r[p++] = new_Range(0, len - 1);while (p) {Range range = r[--p];if (range.start >= range.end)continue;int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點int left = range.start, right = range.end;do{while (arr[left] < mid) ++left;   // 檢測基準點左側是否符合要求while (arr[right] > mid) --right; //檢測基準點右側是否符合要求if (left <= right){swap(&arr[left],&arr[right]);left++;right--;               // 移動指針以繼續}} while (left <= right);if (range.start < right) r[p++] = new_Range(range.start, right);if (range.end > left) r[p++] = new_Range(left, range.end);}
}

递归法 

void swap(int *x, int *y) {int t = *x;*x = *y;*y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {if (start >= end)return;int mid = arr[end];int left = start, right = end - 1;while (left < right) {while (arr[left] < mid && left < right)left++;while (arr[right] >= mid && left < right)right--;swap(&arr[left], &arr[right]);}if (arr[left] >= arr[end])swap(&arr[left], &arr[end]);elseleft++;if (left)quick_sort_recursive(arr, start, left - 1);quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {quick_sort_recursive(arr, 0, len - 1);
}

四：归并排序

定义

把数据分为两段

从两段中逐个选最小的元素移入新数据段的末尾

可从上到下或从下到上进行

算法演示

迭代法 

int min(int x, int y) {return x < y ? x : y;
}
void merge_sort(int arr[], int len) {int* a = arr;int* b = (int*) malloc(len * sizeof(int));int seg, start;for (seg = 1; seg < len; seg += seg) {for (start = 0; start < len; start += seg + seg) {int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while (start1 < end1 && start2 < end2)b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];while (start1 < end1)b[k++] = a[start1++];while (start2 < end2)b[k++] = a[start2++];}int* temp = a;a = b;b = temp;}if (a != arr) {int i;for (i = 0; i < len; i++)b[i] = a[i];b = a;}free(b);
}

递归法 

void merge_sort_recursive(int arr[], int reg[], int start, int end) {if (start >= end)return;int len = end - start, mid = (len >> 1) + start;int start1 = start, end1 = mid;int start2 = mid + 1, end2 = end;merge_sort_recursive(arr, reg, start1, end1);merge_sort_recursive(arr, reg, start2, end2);int k = start;while (start1 <= end1 && start2 <= end2)reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];while (start1 <= end1)reg[k++] = arr[start1++];while (start2 <= end2)reg[k++] = arr[start2++];for (k = start; k <= end; k++)arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {int reg[len];merge_sort_recursive(arr, reg, 0, len - 1);
}

五：基数排序

基数排序是一种非比较型整数排序算法

其原理是将整数按位数切割成不同的数字

然后按每个位数分别比较

由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数

所以基数排序也不是只能使用于整数

1.多关键字的排序

定义

很多时候，一个对象可以用多个特征值来刻画它，可以把每个特征值看做一个关键字

比如扑克牌有花色和点数这两个特征

如果所要求的顺序由多个关键字联合决定

我们就可以利用这种特征来使用多关键字排序方法

多关键字地位不是平等的，有优先级大小

如扑克牌排序

我们就可以规定花色比点数优先

也就是说无论点数多少

只要花色大的就认为它是大牌，

比如规定黑桃大于红心，红心大于梅花，梅花大于方块

多关键字排序有两种思路：高优先级：【MSD】MSD(先用高优先级的关键字进行分组)低优先级：【LSD】LSD(先用低优先级的关键字进行分组)

高优先级排序MSD

下边我们先看高优先级排序方式MSD，
比如有如下扑克牌，我们规定花色优先，花色从小到大关系如下图：方块，梅花，红心，黑桃

第一步：我们先用高优先级的关键字(花色)进行分组，如下图
我们可以想象成四个盒子，把扑克牌按照花色扔进4个盒子中。

全部分进四个盒子之后，在每个组内进行排序（每个盒子内的排序算法随意），每个盒子里边元素排好序之后入下图：

这里每个组内（盒子）的排序也可以继续采用分组的方式，在每个盒子按低优先级分组收集
保证每个组内元素排好序，再把这些排好序的各组的元素收集起来就可以了。如下图

收集好之后，如下图，就是已经排好序的游戏序列。

低优先级排序LSD

我们分析一下低优先级，还以扑克牌为例
第一步：我们先用最低优先级的关键字进行分组

第二步：分组分好之后进行收集

第三步：收集好的数据再按花色进行重新分组

第四步：把分组后数据再重新收集，就可以得到一个有序数组。

通过上边例子我们会发现，整个过程我们并没有进行排序工作，仅仅是进行了分组和收集

这个排序的创新点是它好像并没有进行任何排序

而是通过不断的分组收集

再分组再收集就完成了整个排序工作

2.链式基数排序

采用多关键字排序中的LSD方法

先对低优先级关键字排序

再按照高点的优先级关键字排序

不过基数排序在排序过程中不需要经过关键字的比较

而是借助“分配”和“收集”两种操作

对单逻辑关键字进行排序的一种内部排序方法

 

对n个记录(假设每个记录含d个关键字，每个关键字的取值范围为rd个值)进行链式基数排序的时间复杂度为d*(n+rd)
其中每一躺分配的时间复杂度为n，每一躺收集的时间复杂度为rd，整个排序需进行d躺分配和收集所需辅助空间为2*rd个队列指针，由于采用链表作存储结构，相对于其他采用顺序存储结构的排序方法而言，还增加了n个指针域的空间链式基数排序是稳定的排序比如，若关键字是十进制表示的数字，且范围在[0，999]内则可以把每一个十进制数字看成由三个关键字组成(K0, K1, K2)其中K0是百位数，K1是十位数，K2是个位数基RADIX的取值为10； 按LSD进行排序，从最低位关键字起按关键字的不同值将序列中记录“分配”到RADIX个队列中后再“收集”之如此重复d次。按这种方法实现的排序称之为基数排序以链表作存储结构的基数排序叫链式基数排序

1 #include <stdio.h>2 #include <stdlib.h>3 #include <string.h>4 5 #define DEBUG6 7 #define EQ(a, b) ((a) == (b))8 #define LT(a, b) ((a) <  (b))9 #define LQ(a, b) ((a) <= (b))10 11 //关键字项数的最大个数12 #define MAX_NUM_OF_KEY    813 //关键字基数，此时是十进制整数的基数就是1014 #define RADIX            1015 //静态链表的最大长度16 #define MAX_SPACE        1000017 18 //定义结点中的关键字类型为int19 typedef int KeyType;20 //定义结点中除关键字外的附件信息为char21 typedef char InfoType;22 23 //静态链表的结点类型24 typedef struct{25     //关键字26     KeyType    keys[MAX_NUM_OF_KEY];27     //除关键字外的其他数据项28     InfoType otheritems;29     int next;30 }SLCell;31 32 //静态链表类型33 typedef struct{34     //静态链表的可利用空间，r[0]为头结点35     SLCell r[MAX_SPACE];36     //每个记录的关键字个数37     int keynum;38     //静态链表的当前长度39     int recnum;40 }SLList;41 42 //指针数组类型43 typedef int ArrType[RADIX];44 45 void PrintSList(SLList L)46 {47     int i = 0;48     printf("下标值 ");49     for(i=0; i<=L.recnum; i++){50         printf(" %-6d", i);51     }52     printf("\n关键字 ");53     for(i=0; i<=L.recnum; i++){54         printf(" %-1d%-1d%-1d,%-2c", L.r[i].keys[2], L.r[i].keys[1], L.r[i].keys[0], L.r[i].otheritems);55     }56 //    printf("\n其他值 ");57 //    for(i=0; i<=L.recnum; i++){58 //        printf(" %-5c", L.r[i].otheritems);59 //    }60     printf("\n下一项 ");61     for(i=0; i<=L.recnum; i++){62         printf(" %-6d", L.r[i].next);63     }64     printf("\n");65     return;66 }67 68 void PrintArr(ArrType arr, int size)69 {70     int i = 0;71     for(i=0; i<size; i++){72         printf("[%d]%-2d ", i, arr[i]);73     }74     printf("\n");75 }76 77 /*78  *静态链表L的r域中记录已按(key[0],...,key[i-1])有序79  *本算法按第i个关键字keys[i]建立RADIX个子表，使同一子表中记录的keys[i]相同。80  *f[0,...,RADIX-1]和e[0,...,RADIX-1]分别指向各子表中的第一个记录和最后一个记录。81  */82 void Distribute(SLCell *r, int i, ArrType f, ArrType e)83 {84     int j = 0;85     //各子表初始化为空86     for(j=0; j<RADIX; j++)87         f[j] = e[j] = 0;88 89     int p = 0;90     for(p=r[0].next; p; p=r[p].next){91         j = r[p].keys[i];92         if(!f[j])93             f[j] = p;94         else95             r[e[j]].next = p;96         //将p所指的结点插入第j个字表中97         e[j] = p;98     }99 }
100 
101 /*
102  * 本算法按keys[i]自小到大地将f[0,...,RADIX-1]所指各子表依次链接成一个链表
103  * e[0,...,RADIX-1]为各子表的尾指针
104  */
105 void Collect(SLCell *r, int i, ArrType f, ArrType e){
106     int j = 0, t = 0;
107     //找到第一个非空子表，
108     for(j=0; !f[j]; j++);
109     //r[0].next指向第一个非空子表的第一个结点
110     r[0].next = f[j];
111     //t指向第一个非空子表的最后结点
112     t = e[j];
113     while(j<RADIX){
114         //找下一个非空子表
115         for(j+=1; !f[j]; j++);
116         //链接两个非空子表
117         if(j<RADIX && f[j]){
118             r[t].next = f[j];
119             t = e[j];
120         }
121     }
122     //t指向最后一个非空子表中的最后一个结点
123     r[t].next = 0;
124 }
125 
126 /*
127  * L是采用静态链表表示的顺序表。
128  * 对L作基数排序，使得L成为按关键字自小到大的有效静态链表，L->r[0]为头结点
129  */
130 void RadixSort(SLList *L)
131 {
132     int i = 0;
133     //将L改造成静态链表
134     for(i=0; i<L->recnum; i++)
135         L->r[i].next = i+1;
136     L->r[L->recnum].next = 0;
137 #ifdef DEBUG
138     printf("将L改造成静态链表\n");
139     PrintSList(*L);
140 #endif
141 
142     ArrType f, e;
143     //按最低位优先依次对各关键字进行分配和收集
144     for(i=0; i<L->keynum; i++){
145         //第i趟分配
146         Distribute(L->r, i, f, e);
147 #ifdef DEBUG
148         printf("第%d趟分配---------------------------------------\n");
149         PrintSList(*L);
150         printf("头指针队列:");
151         PrintArr(f, RADIX);
152         printf("尾指针队列:");
153         PrintArr(e, RADIX);
154 #endif
155         //第i躺收集
156         Collect(L->r, i, f, e);
157 #ifdef DEBUG
158         printf("第%d趟收集----\n");
159         PrintSList(*L);
160         printf("按next打印:");
161         int p = 0;
162         for(p=L->r[0].next; p; p=L->r[p].next){
163             printf("%d%d%d ", L->r[p].keys[2], L->r[p].keys[1], L->r[p].keys[0]);
164         }
165         printf("\n");
166 #endif
167     }
168 }
169 
170 int getRedFromStr(char str[], int i, SLCell *result)
171 {
172     int key = atoi(str);
173     if(key<0 || key >999){
174         printf("Error:too big!\n");
175         return -1;
176     }
177     int units = 0, tens = 0, huns = 0;
178     //百位
179     huns = key/100;
180     //十位
181     tens = (key-100*huns)/10;
182     //个位
183     units = (key-100*huns-10*tens)/1;
184     result->keys[0] = units;
185     result->keys[1] = tens;
186     result->keys[2] = huns;
187     result->otheritems = 'a'+i-1;
188     return 0;
189 }
190 
191 
192 int main(int argc, char *argv[])
193 {
194     SLList L;
195     int i = 0;
196     for(i=1; i<argc; i++){
197         if(i>MAX_SPACE)
198             break;
199         if(getRedFromStr(argv[i], i, &L.r[i]) < 0){
200             printf("Error:only 0-999!\n");
201             return -1;
202         }
203     }
204     L.keynum = 3;
205     L.recnum = i-1;
206     L.r[0].next = 0;
207     L.r[0].otheritems = '0';
208     RadixSort(&L);
209     return 0;
210 }

 

六：补充两种排序

1.计数排序

定义

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中

作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数

当输入的元素是 n 个 0 到 k 之间的整数时它的运行时间是 Θ(n + k)
计数排序不是比较排序，排序的速度快于任何比较排序算法
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1）这使得计数排序对于数据范围很大的数组，需要大量时间和内存例如：计数排序是用来排序0到100之间的数字的最好的算法但是它不适合按字母顺序排序人名但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序当然，年龄有重复时需要特殊处理（保证稳定性）这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因

动图演示

（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>void print_arr(int *arr, int n) {int i;printf("%d", arr[0]);for (i = 1; i < n; i++)printf(" %d", arr[i]);printf("\n");
}void counting_sort(int *ini_arr, int *sorted_arr, int n) {int *count_arr = (int *) malloc(sizeof(int) * 100);int i, j, k;for (k = 0; k < 100; k++)count_arr[k] = 0;for (i = 0; i < n; i++)count_arr[ini_arr[i]]++;for (k = 1; k < 100; k++)count_arr[k] += count_arr[k - 1];for (j = n; j > 0; j--)sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];free(count_arr);
}int main(int argc, char **argv) {int n = 10;int i;int *arr = (int *) malloc(sizeof(int) * n);int *sorted_arr = (int *) malloc(sizeof(int) * n);srand(time(0));for (i = 0; i < n; i++)arr[i] = rand() % 100;printf("ini_array: ");print_arr(arr, n);counting_sort(arr, sorted_arr, n);printf("sorted_array: ");print_arr(sorted_arr, n);free(arr);free(sorted_arr);return 0;
}

2.桶排序

定义

桶排序是计数排序的升级版

它利用了函数的映射关系

高效与否的关键就在于这个映射函数的确定

为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要

什么时候最快：当输入的数据可以均匀的分配到每一个桶中什么时候最慢：当输入的数据可以均匀的分配到每一个桶中

示意图

元素分布在桶中：

然后，元素在每个桶中排序：

#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;struct ListNode{explicit ListNode(int i=0):mData(i),mNext(NULL){}ListNode* mNext;int mData;
};ListNode* insert(ListNode* head,int val){ListNode dummyNode;ListNode *newNode = new ListNode(val);ListNode *pre,*curr;dummyNode.mNext = head;pre = &dummyNode;curr = head;while(NULL!=curr && curr->mData<=val){pre = curr;curr = curr->mNext;}newNode->mNext = curr;pre->mNext = newNode;return dummyNode.mNext;
}ListNode* Merge(ListNode *head1,ListNode *head2){ListNode dummyNode;ListNode *dummy = &dummyNode;while(NULL!=head1 && NULL!=head2){if(head1->mData <= head2->mData){dummy->mNext = head1;head1 = head1->mNext;}else{dummy->mNext = head2;head2 = head2->mNext;}dummy = dummy->mNext;}if(NULL!=head1) dummy->mNext = head1;if(NULL!=head2) dummy->mNext = head2;return dummyNode.mNext;
}void BucketSort(int n,int arr[]){vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));for(int i=0;i<n;++i){int index = arr[i]/BUCKET_NUM;ListNode *head = buckets.at(index);buckets.at(index) = insert(head,arr[i]);}ListNode *head = buckets.at(0);for(int i=1;i<BUCKET_NUM;++i){head = Merge(head,buckets.at(i));}for(int i=0;i<n;++i){arr[i] = head->mData;head = head->mNext;}
}

七：总结

从算法的简单性来看，可以将 7 种算法分为两类： 

简单算法：冒泡，简单选择，直接插入

改进算法：希尔，堆，归并，快速

1.从平均情况来看

显然后面 3 种改进算法要胜过希尔排序，并远远胜过前 3 种简单算法

2.从最好情况看

反而冒泡和直接插入排序更好

也就是说，如果你的待排序序列总是 基本有序

反而不应该考虑 4 种复杂的改进算法

3.从最坏情况看

堆排序和归并排序又强过快速排序以及其他简单排序

4.从空间复杂度看

归并排序强调要马跑得快，就得给马吃饱

快速排序也有相应的空间要求

反而堆排序等却都是少量索取，大量付出，对空间要求是 O(1)

如果执行算法的软件非常在乎 内存使用量 时，选择归并排序和快速排序就不是一个较好的决策了

5.总的来说

综合各项指标，经过优化的快速排序是性能最好的排序算法

但是不同的场合我们也应该考虑使用不同的算法来应对

 6.按平均时间将排序分为四类

（1）平方阶(O(n2))排序一般称为简单排序，例如直接插入、直接选择和冒泡排序（2）线性对数阶(O(nlgn))排序如快速、堆和归并排序（3）O(n1+￡)阶排序￡是介于0和1之间的常数，即0<￡<1，如希尔排序（4）线性阶(O(n))排序如桶、箱和基数排序

7.各种排序方法比较

简单排序中直接插入最好；快速排序最快；当文件为正序时直接插入和冒泡均最佳

8.影响排序效果的因素

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：①待排序的记录数目n②记录的大小(规模)③关键字的结构及其初始状态④对稳定性的要求⑤语言工具的条件⑥存储结构⑦时间和辅助空间复杂度等