内部排序
文章目录
- 内部排序
- 10.1 概述
- 10.2 插入排序
- 10.2.1 直接插入排序
- 10.2.2 其他插入排序
- 10.2.2.1 折半插入排序(Binary Insertion Sort)
- 10.2.2.2 2-路插入排序(Two-Way Insertion Sort)
- 10.2.2.3 表插入排序(Table Insertion Sort)
- 10.2.3 希尔排序(Shell's Sort)
- 10.3 交换排序
- 10.3.1 冒泡排序(Bubble Sort)
- 10.3.2 快速排序(Quick Sort)
- 10.4 选择排序
- 10.4.1 简单选择排序(Simple Selection Sort)
- 10.4.2 树形选择排序(Tree Selection Sort)
- 10.4.3 堆排序(Heap Sort)
- 10.5 归并排序(Merging Sort)
- 10.6 基数排序(Radix Sorting)
- 10.6.1 多关键字的排序
- 10.6.2 链式基数排序
- 10.7 各种内部排序方法的比较讨论
10.1 概述
排序 :将一组杂乱无章的数据按一定规律顺次排列起来。即,将无序序列排成一个有序序列 (由小到大或由大到小) 的运算。
如果参加排序的数据结点包含多个数据域,那么排序往往是针对其中某个域而言。
排序方法分类 :
-
按数据存储介质: 内部排序和外部排序
- 内部排序:数据量不大、数据在内存,无需内外存交换数据
- 外部排序:数据量较大、数据在外存(文件排序) —— 外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存
-
按比较器个数: 串行排序和并行排序
- 串行排序:单处理机(同一时刻比较一对元素)
- 并行排序:多处理机(同一时刻比较多对元素)
-
按主要操作: 比较排序和基数排序
- 比较排序:用比较的方法 —— 插入排序、交换排序、选择排序、归并排序
- 基数排序:不比较元素的大小,仅仅根据元素本身的取值确定其有序位置。
-
按辅助空间: 原地排序和非原地排序
- 原地排序:辅助空间用量为O(1)的排序方法(所占的辅助存储空间与参加排序的数据量大小无关)·
- 非原地排序:辅助空间用量超过O(1的排序方法(所占的辅助存储空间与参加排序的数据量大小有关)·
-
按稳定性: 稳定排序和非稳定排序
-
稳定排序:能够使任何数值相等的元素,排序以后相对次序不变。例如:直接插入排序
-
非稳定性排序:数值相等的元素,排序以后相对次序改变。例如:简单选择排序
排序方法是否稳定,并不能衡量一个排序算法的优劣。
-
-
按自然性: 自然排序和非自然排序
- 自然排序:输入数据越有序排序的速度越快的排序方法。
- 非自然排序:输入数据越有序排序的速度慢的排序方法。
存储结构 :
-
顺序表存储:待排序的一组记录存放在地址连续的一组存储单元上。记录之间的次序关系由其存储位置决定,则实现排 序必须借助移动记录
# define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型 typedef struct { //定义每个记录(数据元素)的结构 KeyType key; //关键字 //InfoType otherinfo; //其它数据项 }RedType; typedef struct { // 定义顺序表结构 RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵 int length; //顺序表的长度 }SqList;
-
链表存储:待排序记录存放在静态链表中,记录之间的次序关系由 指针指示,则实现排序不需要移动记录,仅需修改指针即可;
-
地址存储:待排序记录本身存储在一组地址连续的存储单元内,同时另设一个指示各个记录存储位置的地址向量,在排序过 程中不移动记录本身,而移动地址向量中这些记录的“地址",在排序结束之后再按照地址向量中的值调整记录的存储位置。
10.2 插入排序
插入排序:
在有序序列中插入一个元素,保持序列有序,有序长度不断增加。
有序插入方法:
- 在插入a[i]前,数组a的前半段(a[0]~a[i-1])是有序段, 后半段(a[i]~a[n-1])是停留于输入次序的“无序段“
- 插入a[i]使a[0]~a[i-1]有序,也就是要为a[i]找到有序位置j (0≤j≤i) ,将a[i]插入在a[j]的位置上。
根据找插入位置方法不同分为:
- 顺序法定位插入位置:直接插入排序
- 二分法定位插入位置:二分插入排序
- 缩小增量多遍插入排序:希尔排序
10.2.1 直接插入排序
实现排序的基本操作有两个:
(1) “比较”序列中两个关键字的大小;
(2) “移动”记录。
#include<stdio.h>
# define MAXSIZE 20 // 设记录不超过20个
typedef int KeyType; // 设关键字为int型
typedef struct { //定义每个记录(数据元素)的结构
KeyType key; //关键字
}RedType;
typedef struct { // 定义顺序表结构
RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
int length; //顺序表的长度
}SqList;
void InsertSort(SqList* L)
{
int i, j;
for (i = 2; i <= L->length; i++)
{
if (L->r[i].key < L->r[i - 1].key) //后面比前面数小,则需要进行排序
{
L->r[0] = L->r[i]; // 复制插入元素到哨兵
//记录后移,寻找插入位置
L->r[i] = L->r[i - 1];
for (j = i - 2; L->r[0].key < L->r[j].key; j--)
{
L->r[j + 1] = L->r[j];
}
//插人到正确位置
L->r[j + 1] = L->r[0];
}
//后面数大于等于前面数,只需继续循环,比较下一个数
}
}
int main()
{
int i;
int r[7] = {32,12,24,5,16,43,20};
SqList L;
L.length = 7;
for (i = 0; i < 7; i++)
{
L.r[i + 1].key = r[i];
}
InsertSort(&L);
for (i = 0; i < 7; i++)
{
printf("%d ", L.r[i + 1].key);
}
return 0;
}
n个元素
最好情况:顺序有序
- 比较次数: ∑ i = 2 n 1 = n − 1 \sum_{i=2}^{n}1 = n-1 i=2∑n1=n−1
- 移动次数:0
- 时间复杂度 O(n)
最坏情况:逆序有序
-
比较次数(平均值): ∑ i = 2 n i = ( n + 2 ) ( n − 1 ) 2 \sum_{i=2}^{n}i = \frac{(n+2)(n-1)}{2} i=2∑ni=2(n+2)(n−1)
-
移动次数(平均值): ∑ i = 2 n ( i + 1 ) = ( n + 4 ) ( n − 1 ) 2 \sum_{i=2}^{n}(i+1) = \frac{(n+4)(n-1)}{2} i=2∑n(i+1)=2(n+4)(n−1)
-
时间复杂度 O(n2)
平均情况:
- 比较次数(平均值): ∑ i = 2 n i + 1 2 = ( n + 2 ) ( n − 1 ) 4 \sum_{i=2}^{n}\frac{i+1}{2} = \frac{(n+2)(n-1)}{4} i=2∑n2i+1=4(n+2)(n−1)
- 移动次数(平均值): ∑ i = 2 n ( i + 1 2 + 1 ) = ( n + 6 ) ( n − 1 ) 4 \sum_{i=2}^{n}(\frac{i+1}{2}+1) = \frac{(n+6)(n-1)}{4} i=2∑n(2i+1+1)=4(n+6)(n−1)
- 时间复杂度 O(n2) - 最坏的情况的一半
空间复杂度:O(1)
稳定性:稳定
原始数据越接近有序,排序速度越快
10.2.2 其他插入排序
10.2.2.1 折半插入排序(Binary Insertion Sort)
插入排序的基本操作是在一个有序表中进行查找和插入,这个==“查找“操作可利用“折半查找”==来实现,再进行插入,则称之为折半插入排序(Binary Insertion Sort)
#include<stdio.h>
# define MAXSIZE 20 // 设记录不超过20个
typedef int KeyType; // 设关键字为int型
typedef struct { //定义每个记录(数据元素)的结构
KeyType key; //关键字
}RedType;
typedef struct { // 定义顺序表结构
RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
int length; //顺序表的长度
}SqList;
void BInsertSort(SqList* L)
{
int i, j;
for (i = 2; i <= L->length; i++)
{
L->r[0] = L->r[i]; // 复制插入元素到哨兵
int low = 1;
int high = i - 1;
while (low <= high) { //在 r[low.. high]中折半查找有序插入的位置
int m = (low + high) / 2; // 折半
if (L->r[0].key < L->r[m].key) //插入点在低半区
{
high = m - 1;
}
else { //插入点在高半区
low = m + 1;
}
}//循环结束,high+1 则为插入位置
for (j = i - 1; j>=high+1; j--)
{
L->r[j + 1] = L->r[j]; //记录后移
}
L->r[high + 1] = L->r[0]; // 插入
}
}
int main()
{
int i;
int r[7] = {32,12,24,5,16,43,20};
SqList L;
L.length = 7;
for (i = 0; i < 7; i++)
{
L.r[i + 1].key = r[i];
}
BInsertSort(&L);
for (i = 0; i < 7; i++)
{
printf("%d ", L.r[i + 1].key);
}
return 0;
}
折半插入排序特点:
- 折半查找比顺序查找快,
- 关键码比较次数与待排座对象序列的初始排列无关,仅依赖于对象个数。
- 当n较大时,总关键码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差;
- 在对象的初始排列已经按关键码排好序或接近有序时,直接插入排序比折半插入排序执行的关键码比较次数要少;
- 平均性能优于直接插入排序
n个元素
折半插入排序仅减少了关键字间的比较次数,而记录的移动次数不变
时间复杂度:仍为O(n2),
空间复杂度:O(1)
稳定性:稳定
10.2.2.2 2-路插入排序(Two-Way Insertion Sort)
2- 路插入排序是在折半插入排序的基础上再改进之,其目的是减少排序过程中移动 记录的次数,但为此需要n个记录的辅助空间。
- 初始化一个与原数组一样大小的辅助数组d,并将原数组的第一个元素放入辅助数组的第一个位置。
- 将d看成是一个循环向量,并设两个指针 first 和 final分别指示排序过程中得到的有序序列中的第一个和最后一个记录在d中的位置。
- 从第二个元素开始遍历原数组,对于每个待排序元素:
- 如果待排序元素小于辅助数组的最小值,则通过移动first将其插入到最小值之前。
- 如果待排序元素大于辅助数组的最大值,则过移动final将其插入到最大值之后。
- 否则,通过移动final将大于的数值向后移动并将待排序元素插入到适当的位置。
- 处理完所有元素后,将辅助数组中的元素复制回原数组,完成排序。
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20 // 设记录不超过20个
typedef int KeyType; // 设关键字为int型
typedef struct { //定义每个记录(数据元素)的结构
KeyType key; //关键字
}RedType;
typedef struct { // 定义顺序表结构
RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
int length; //顺序表的长度
}SqList;
void TwoWayInsertSort(SqList* L) {
/* 初始化一个与原数组一样大小的辅助数组 */
RedType* d;
d = (RedType*)malloc((L->length) * sizeof(RedType));
if (d == NULL) {
return;
}
/* 设L的第1个记录为d中排好序的记录(在位置[0]) */
d[0] = L->r[1];
/* first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 */
int first, final;
first = final = 0;
int i, j;
/* 依次将L的第2个~最后1个记录插入d中 */
for (i = 2; i <= L->length; i++) {
if (L->r[i].key < d[first].key) {
/* 待插记录小于d中最小值,插到d[first]之前(不需移动d数组的元素) */
first = (first - 1 + L->length) % L->length;
d[first] = L->r[i];
}
else if (L->r[i].key > d[final].key) {
/* 待插记录大于d中最大值,插到d[final]之后(不需移动d数组的元素) */
final++;
d[final] = L->r[i];
}
else {
/* 待插记录大于d中最小值,小于d中最大值,插到d的中间(需要移动d数组的元素) */
j = final++;
while (L->r[i].key < d[j].key)
{
d[(j + 1) % L->length] = d[j];
j = (j - 1 + L->length) % L->length;
}
d[j + 1] = L->r[i];
}
}
for (i = 1; i <= L->length; i++) { // 修改循环条件
L->r[i] = d[i - 1]; // 将排序后的元素放回L中
}
for (i = 1; i <= L->length; i++) { // 输出排序后的L
printf("%d ", L->r[i].key);
}
printf("\n");
printf("在L中first: %d \n", first + 1);
printf("在L中final: %d ", final + 1);
free(d); // 释放内存
}
int main() {
int i;
int r[8] = { 49,38,65,97,76,13,27,49 };
SqList L;
L.length = 8;
for (i = 1; i <= L.length; i++) {
L.r[i].key = r[i - 1];
}
TwoWayInsertSort(&L);
return 0;
}
n个元素
时间复杂度:2-路插入排序的时间复杂度为O(n2),移动次数大约为n2/8次,尽管减少了移动次数,但并不能完全避免移动操作。
空间复杂度:需要额外的辅助数组,空间复杂度为O(n)。
10.2.2.3 表插入排序(Table Insertion Sort)
在排序过程中不移动记 录,只有改变存储结构
算法思路:
- 初始化表头结点:设数组中下标为"0"的分量为表头结点,并令表头结点记录的关键字取最大整数 MAXINT
- 表插入排序的过程:
- 首先将静态链表中数组下标为"1"的分量(结点)和表头结点构成一个循环链表
- 然后依次将下标为"2"至"n"的分量(结点)按记录关键字非递减有序插人到循环链表中
#include<stdio.h>
#include<limits.h>
#define MAXSIZE 20 // 设记录不超过20个
#define MAXVALUE INT_MAX // 定义最大值
typedef struct SLNode {
int data; // 存储数据
int link; // 存储指向下一个元素的索引
}SLNode, Table[MAXSIZE];
void TableInsertSort(Table* tb, int n)
{
//与第一个数据元素构成循环列表
(*tb)[0].link = 1; // 初始化顺序表的头结点,将其link指向第一个数据元素
int p, q; // 用于在排序过程中存储当前元素和前驱元素的索引
for (int i = 2; i < n; i++) // 从第二个元素开始遍历
{
p = (*tb)[0].link;
q = 0;
while (p != 0 && (*tb)[p].data <= (*tb)[i].data)
{
q = p; //q是p的前驱
p = (*tb)[p].link; // p更新为下一个元素的索引
}
(*tb)[i].link = (*tb)[q].link; // 将i插入到q的后面
(*tb)[q].link = i; // 更新q的link,使其指向i
}
}
int main() {
int i;
int r[9] = { 0,49,38,65,97,76,13,27,49 };
Table tb;
// 初始化表头结点:
tb[0].data = MAXVALUE;
tb[0].link = 0;
for (i = 1; i < 9; i++)
{
tb[i].data = r[i];
tb[i].link = 0;
}
TableInsertSort(&tb, 9);
for (i = 0; i < 9; i++)
{
if (tb[i].data == MAXVALUE)
{
printf("%c ", 'M');
continue;
}
printf("%d ", tb[i].data);
}
printf("\n");
for (i = 0; i < 9; i++)
{
printf("%d ", tb[i].link);
}
return 0;
}
10.2.3 希尔排序(Shell’s Sort)
又称“缩小增量排序"(Diminishing Increment Sort)
基本思想: 先将整个待排记录序列分割成为若干子序列分别进行直接插入排 序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。
- 选择一个增量序列 Dk:DM > DM-1 > … > D1 = 1 必须递减
- 对每个Dk进行“Dk-间隔”插入排序(K= M,M-1,…1)
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20 // 设记录不超过20个
typedef int KeyType; // 设关键字为int型
typedef struct { //定义每个记录(数据元素)的结构
KeyType key; //关键字
}RedType;
typedef struct { // 定义顺序表结构
RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
int length; //顺序表的长度
}SqList;
void ShellInsert(SqList* L, int dk)
{
int i, j;
for (i = dk + 1; i <= L->length; i++)// 从第dk+1个元素开始向后遍历顺序表
{
if (L->r[i].key < L->r[i - dk].key)
// 如果当前元素的key小于它dk位置前的元素的key
{
L->r[0] = L->r[i];// L->r[0]是暂存单元,暂存当前元素
for (j = i - dk; j > 0 && (L->r[0].key < L->r[j].key); j = j - dk)
{// 从当前元素向前遍历,步长为dk
L->r[j + dk] = L->r[j]; // 将比暂存元素大的元素向后移动dk个位置
}
L->r[j + dk] = L->r[0]; // 将暂存的元素插入到正确的位置
}
}
}
void ShellSort(SqList *L, int dlta[], int t)
{
int i, k;
for (k = 0; k < t; k++)
{
ShellInsert(L, dlta[k]);
printf("\n第 D%d 增量序列排序结果:\n", dlta[k]);
for (i = 1; i <= 13; i++)
{
printf("%d ", L->r[i].key);
}
}
}
int main() {
int i;
int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
SqList L;
L.length = 13;
for (i = 1; i <= L.length; i++) {
L.r[i].key = r[i - 1];
}
// 增量序列
int dlta[3] = { 5,3,1 };
ShellSort(&L, dlta, 3);
printf("\n-----------------\n");
printf("排序结果:\n");
for (i = 1; i <= 13; i++)
{
printf("%d ", L.r[i].key);
}
return 0;
}
希尔排序算法效率与增量序列的取值有关:
Hibbard增量序列
- Dk = 2 k-1 —— 相邻元素互质
- 最坏: Tworst = O(n3/2)
- 猜想: Tavg = O(n5/4)
Sedgewick增量序列
- {1,5,19,41,109,……} —— 9 * 4i - 9 * 2i + 1 或 4i - 3 * 2i + 1
- 最坏: Tworst = O(n4/3)
- 猜想: Tavg = O(n7/6)
稳定性:不稳定
时间复杂度:O(n1.25) ~ O(1.6n1.25) – 经验公式
最好:O(n)
最坏:O(n2)
最好:~O(n1.3)
空间复杂度:O(1)
不宜在链式存储结构上实现
10.3 交换排序
交换排序:两两比较,如果发生逆序则交换,直到所有记录都排好序为止。
10.3.1 冒泡排序(Bubble Sort)
基本思想: 每趟不断将记录两两比较,并按“前小后大”规则交换
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20 // 设记录不超过20个
typedef int KeyType; // 设关键字为int型
typedef struct { //定义每个记录(数据元素)的结构
KeyType key; //关键字
}RedType;
typedef struct { // 定义顺序表结构
RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
int length; //顺序表的长度
}SqList;
void bubble_sort(SqList *L)
{
int i, j;
RedType x; // 交换时临时存储
for (i = 1; i <= L->length - 1; i++) // 需要比较i趟,n个记录 总共n-1趟
{
for (j = 1; j <= L->length - i; j++) // 每一趟需要比较的次数,n个记录,比较n-i次
{
if (L->r[j].key > L->r[j + 1].key) // 比较
{
//发生逆序 - 交换
x = L->r[j];
L->r[j] = L->r[j + 1];
L->r[j + 1] = x;
}
}
printf("\n第 %d 趟排序结果:\n", i);
for (j = 1; j <= L->length; j++)
{
printf("%d ", L->r[j].key);
}
}
}
int main() {
int i;
int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
SqList L;
L.length = 13;
for (i = 1; i <= L.length; i++) {
L.r[i].key = r[i - 1];
}
bubble_sort(&L);
printf("\n-----------------\n");
printf("排序结果:\n");
for (i = 1; i <= 13; i++)
{
printf("%d ", L.r[i].key);
}
return 0;
}
改进:冒泡处理过程中,没有进行任何交换,说明序列已有序,则停止交换
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20 // 设记录不超过20个
typedef int KeyType; // 设关键字为int型
typedef struct { //定义每个记录(数据元素)的结构
KeyType key; //关键字
}RedType;
typedef struct { // 定义顺序表结构
RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
int length; //顺序表的长度
}SqList;
void bubble_sort(SqList *L)
{
int i, j;
int flag = 1;
RedType x; // 交换时临时存储
for (i = 1; (i <= L->length - 1) && (flag == 1); i++) // 需要比较i趟,n个记录 总共n-1趟
{
flag = 0;
for (j = 1; j <= L->length - i; j++) // 每一趟需要比较的次数,n个记录,比较n-i次
{
if (L->r[j].key > L->r[j + 1].key) // 比较
{
flag = 1;
//发生逆序 - 交换
x = L->r[j];
L->r[j] = L->r[j + 1];
L->r[j + 1] = x;
}
}
printf("\n第 %d 趟排序结果:\n", i);
printf("flag = %d \n", flag);
for (j = 1; j <= L->length; j++)
{
printf("%d ", L->r[j].key);
}
}
}
int main() {
int i;
int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
SqList L;
L.length = 13;
for (i = 1; i <= L.length; i++) {
L.r[i].key = r[i - 1];
}
bubble_sort(&L);
printf("\n-----------------\n");
printf("排序结果:\n");
for (i = 1; i <= 13; i++)
{
printf("%d ", L.r[i].key);
}
return 0;
}
最好情况:正序
- 比较次数:n-1
- 移动次数:0
- 时间复杂度 O(n)
最坏情况:逆序
-
比较次数(平均值): ∑ i = 1 n − 1 ( n − i ) = ( n 2 − n ) 2 \sum_{i=1}^{n-1}(n - i) = \frac{(n^2-n)}{2} i=1∑n−1(n−i)=2(n2−n)
-
移动次数(平均值): 3 ∑ i = 1 n − 1 ( n − i ) = 3 ( n 2 − n ) 2 3\sum_{i=1}^{n-1}(n - i) = \frac{3(n^2-n)}{2} 3i=1∑n−1(n−i)=23(n2−n)
-
时间复杂度 O(n2)
平均情况:
- 时间复杂度 O(n2)
空间复杂度:O(1)
稳定性:稳定
10.3.2 快速排序(Quick Sort)
基本思想:
-
任取一个元素 (如:第一个) 为中心pivot - 可以是第一个数、最后一个数、最中间一个数、任选一个数等
-
所有比它小的元素一律前放,比它大的元素一律后放形成左右两个子表;
-
对各子表重新选择中心元素并依此规则调整 【递归思想】
-
直到每个子表的元素只剩一个
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20 // 设记录不超过20个
typedef int KeyType; // 设关键字为int型
typedef struct { //定义每个记录(数据元素)的结构
KeyType key; //关键字
}RedType;
typedef struct { // 定义顺序表结构
RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
int length; //顺序表的长度
}SqList;
int Partition(SqList* L, int low, int high)
{
int pivotkey = L->r[low].key; //任取一个元素 (第一个) 为中心pivot
L->r[0] = L->r[low]; // 将中心pivot放到0处
while (low < high)
{
while (low < high && L->r[high].key >= pivotkey) // high >= 中心 ,移动high向前
{
--high;
}
L->r[low] = L->r[high]; //high < 中心, 把该值移动到low那一侧
while (low < high && L->r[low].key <= pivotkey)// low <= 中心 ,移动low向后
{
++low;
}
L->r[high] = L->r[low];//low > 中心, 把该值移动到high那一侧
}
L->r[low] = L->r[0]; // 中心放到对应位置
return low;
}
void QSort(SqList *L, int low, int high)
{
if (low < high)//长度大于1
{
int pivotloc = Partition(L, low, high); //将L.r[low .. high]一分为二
printf("low = %d, high = %d, pivotloc = %d\n", low, high, pivotloc);
for (int i = 1; i <= 13; i++)
{
printf("%d ", L->r[i].key);
}
printf("\n-----------------\n");
QSort(L, low, pivotloc - 1); //对低子表递归排序
QSort(L, pivotloc + 1, high); //对高子表递归排序,
}
}
int main() {
int i;
int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
SqList L;
L.length = 13;
for (i = 1; i <= L.length; i++) {
L.r[i].key = r[i - 1];
}
QSort(&L,1, L.length);
printf("排序结果:\n");
for (i = 1; i <= 13; i++)
{
printf("%d ", L.r[i].key);
}
return 0;
}
划分元素的选取是影响时间性能的关键
最好情况:
- 时间复杂度 O(nlogn)
最坏情况:
- 时间复杂度 O(n2)
平均情况:
- 时间复杂度:O(nlogn)
QSort():O(logn)
Partition():O(n)
空间复杂度:
平均情况:O(logn)
最坏情况:O(n)
稳定性:不稳定
快速排序不适于对原本有序或基本有序(包括正序和逆序)的记录序列进行排序,退化成冒泡排序
10.4 选择排序
10.4.1 简单选择排序(Simple Selection Sort)
基本思想: 在待排序的数据中选出最大(小)的元素放在其最终的位置。
基本操作:
- 首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换
- 再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换
- 重复上述操作,共进行n-1趟排序后,排序结束
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20 // 设记录不超过20个
typedef int KeyType; // 设关键字为int型
typedef struct { //定义每个记录(数据元素)的结构
KeyType key; //关键字
}RedType;
typedef struct { // 定义顺序表结构
RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
int length; //顺序表的长度
}SqList;
void SelectSort(SqList* L)
{
int i, j, k;
for (i = 1; i < L->length; i++)
{
k = i;
for (j = i + 1; j <= L->length; j++)
{
if (L->r[j].key < L->r[k].key)
{
k = j;
}
}
if (k != i)
{
L->r[0] = L->r[k];
L->r[k] = L->r[i];
L->r[i] = L->r[0];
}
printf("\n第 %d 次排序结果:\n", i);
for (j = 1; j <= L->length; j++)
{
printf("%d ", L->r[j].key);
}
}
}
int main() {
int i;
int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
SqList L;
L.length = 13;
for (i = 1; i <= L.length; i++) {
L.r[i].key = r[i - 1];
}
SelectSort(&L);
printf("\n-----------------\n");
printf("排序结果:\n");
for (i = 1; i <= 13; i++)
{
printf("%d ", L.r[i].key);
}
return 0;
}
时间复杂度 - O(n2):
-
移动次数
- 最好情况:0
- 最坏情况:3(n-1)
-
比较次数:
- 最好情况:O(n2)
- 最坏情况:O(n2)
- 平均情况:O(n2)
∑ i = 1 n − 1 ( n − i ) = n ( n − 1 ) 2 \sum_{i=1}^{n-1}(n - i) = \frac{n(n-1)}{2} i=1∑n−1(n−i)=2n(n−1)
空间复杂度:O(1)
稳定性:不稳定
10.4.2 树形选择排序(Tree Selection Sort)
又称锦标赛排序(Tournament Sort)
基本思想: 首先对n个记录的关键字进行两两比较,然后在 其中⌈ n / 2⌉个较小者之间再进行两两比较,如此重复,直至选出最小关键字的记录为止。
10.4.3 堆排序(Heap Sort)
若n个元素的序列{a1,a2,…, an}满足 ai ≤ a2i && ai ≤ a2i+1 则称该序列为小根堆
若n个元素的序列{a1,a2,…, an}满足 ai ≥ a2i && ai ≥ a2i+1 则称该序列为大根堆
从堆的定义可以看出,堆实质是满足如下性质的完全二叉树:二又树中任一非叶子结点均小于(大于)它的孩子结点
堆排序: 若在输出堆顶的最小值(最大值)后,使得剩余n-1个元素的序列重又建成一个堆,则得到n个元素的次小值(次大值)…如此反复,便能得到一个有序序列。【堆顶就是最小值(最大值),每次都取堆顶,就可得到一个有序序列】
堆序列需解决两个问题:
-
如何由无序序列建成一个堆?
-
单结点的二又树是堆
-
在完全二叉树中所有以叶子结点(序号i>n/2【最后一个结点是n,那么他的双亲是n/2,所以叶子结点是 > n/2】)为根的子树是堆。
-
只需依次将以序号为n/2,n/2 - 1,… 1的结点为根的子树均调整为堆即可。
-
-
如何在输出堆顶元素后,调整剩余元素为一个新的堆?
小根堆:
-
输出堆顶元素之后,以堆中最后一个元素【编号最大的元素】替代之;
-
然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换,
-
重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为“筛选
-
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20 // 设记录不超过20个
typedef int KeyType; // 设关键字为 int 型
typedef struct { //定义每个记录(数据元素)的结构
KeyType key; //关键字
}RedType;
typedef struct { // 定义顺序表结构
RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
int length; //顺序表的长度
}SqList;
typedef SqList HeapType; // 堆采用顺序表存储表示
/*大根堆*/
void HeapAdjust_big(HeapType* H, int s, int m)
{
//调整R[s]关键字,使R[s...m]成为一个大根堆
RedType rc = H->r[s];
int j;
for (j = 2 * s; j <= m; j *= 2)
{
// H->r[j]和 H->r[j + 1]分别代表H->r[s]的左子结点和右子结点,比较出两者之间最大值
if (j < m && H->r[j].key < H->r[j + 1].key)
{
++j;
}
//再和比较H->r[s]比较最大值
if (rc.key >= H->r[j].key)
{
//H->r[s]最大,即无需改动位置
break;
}
H->r[s] = H->r[j];
s = j;
}
H->r[s] = rc;//插入
}
/*小根堆*/
void HeapAdjust_small(HeapType* H, int s, int m)
{
//调整R[s]关键字,使R[s...m]成为一个小根堆
RedType rc = H->r[s];
int j;
for (j = 2 * s; j <= m; j *= 2)
{
if (j < m && H->r[j].key > H->r[j + 1].key)
{
++j;
}
if (rc.key <= H->r[j].key)
{
break;
}
H->r[s] = H->r[j];
s = j;
}
H->r[s] = rc;
}
void HeapSort(HeapType* H)
{
//对顺序表H进行堆排序
int i;
for (i = H->length / 2; i > 0; i--) //建初始堆 从 i = H->length / 2 往前到1
{
HeapAdjust_small(H, i, H->length);
}
for (i = H->length; i > 1; i--) //进行n-1趟排序
{
printf("%d ", H->r[1].key);
//根与最后一个元素交换
H->r[0] = H->r[i];
H->r[i] = H->r[1];
H->r[1] = H->r[0];
//对R[1]到R[i-1]重新建堆
HeapAdjust_small(H, 1, i-1);
}
}
int main() {
int i;
int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
HeapType H;
H.length = 13;
for (i = 1; i <= H.length; i++) {
H.r[i].key = r[i - 1];
}
printf("排序结果:\n");
HeapSort(&H);
return 0;
}
时间复杂度:
- 初始堆化所需时间不超过O(n)
- 排序阶段(不含初始堆化)
- 一次重新堆化所需时间不超过O(logn)
- n-1次循环所需时间不超过O(nlogn)
- Tw(n)=0(n)+ O(nlogn)= O(nlogn) —— 最好情况、最坏情况、平均情况
空间复杂度:O(1)
稳定性:不稳定
不适用于待排序记录个数n较少的情况,但对于n较大的文件还是很有效的。
10.5 归并排序(Merging Sort)
基本思想:将两个或两个以上的有序子序列“归并”为一个有序序列,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题 分(divide) 成一些小的问题然后递归求解,而 治(conquer) 的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
通常采用2-路归并排序:将两个位置相邻的有序子序列R[l…]m]和R[m+1…]n] 归并为一个有序序列R[l…n]
整个归并排序仅需 ⌈log2n⌉ 趟
#include<stdio.h>
#include<stdlib.h>
void Merge(int* arr, int left, int mid, int right) {
int* temp = (int*)malloc((right - left + 1) * sizeof(int));
/*
i => [left, mid]
j => [mid + 1, right]
*/
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = left, k = 0; i <= right; i++, k++) {
arr[i] = temp[k];
}
free(temp);
}
void MergeSort(int* arr, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
void printArray(int* arr, int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = { 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
MergeSort(arr, 0, n - 1);
printArray(arr, n);
return 0;
}
时间复杂度:O(nlogn) —— 最好情况、最坏情况、平均情况
空间复杂度:O(n)
稳定性:稳定
10.6 基数排序(Radix Sorting)
10.6.1 多关键字的排序
基本步骤:
- 确定每个关键字的优先级
- 对每个关键字进行排序
- 根据优先级合并排序结果
关键字的次序:K0, K1, … , Kd-1
最主位关键字:K0
最次位关键字:Kd-1
最高位优先 (Most Significant Digit first)法,简称 MSD 法
-
先对最主位关键字 K0 进行排序,将序列分成若干子序列,每个子序 列中的记录都具有相同的K0值,
-
然后分别就每个子序列对关键字 K1 进行排序,按K1值 不同再分成若干更小的子序列,
-
依次重复,
-
直至对 Kd-2 进行排序之后得到的每一子序列 中的记录都具有相同的关键字(K0, K1, … , Kd-2),
-
而后分别每个子序列对 Kd-1 进行排 序,最后将所有子序列依次联接在一起成为一个有序序列
最低位优先 (Least Significant Digit first) 法,简称 LSD 法
- 从最次位关键字 Kd-1 起进行排序。
- 然后再对高一位的关键字 Kd-2 进行排序,
- 依次重复,
- 直至对 K0 进行排序后便成 为一个有序序列
/*--------------使用LSD基数排序算法---------------*/
/* K 由 3个关键字(K0,0K1 ,K2)组成,其中 K0 是百位数,K1 是十位数,K2 是个位数;*/
#include<stdio.h>
#include<stdlib.h>
// 定义最大数字的位数
#define MAX_DIGITS 3 // 3位数字,百位、十位、个位
// 定义桶的大小
#define BUCKET_SIZE 10 // 10个桶,分别对应0-9
/**
* 函数:分配数据到桶中
* @param data 要排序的数据数组
* @param bucket 桶数组,用于统计每个数字出现的次数
* @param n 数据数组的长度
* @param digit 当前正在处理的位数(1、10、100)
*/
void distribute(int* data, int* bucket, int n, int digit) {
int i;
// 遍历数据数组,统计每个数字在当前位数上的值
for (i = 0; i < n; i++) {
// 计算当前数字在当前位数上的值
int index = (data[i] / digit) % 10;
// 将该值对应的桶计数加1
bucket[index]++;
}
}
/**
* 函数:收集数据从桶中
* @param data 要排序的数据数组
* @param bucket 桶数组,用于统计每个数字出现的次数
* @param temp 临时数组,用于存储收集的数据
* @param n 数据数组的长度
* @param digit 当前正在处理的位数(1、10、100)
*/
void collect(int* data, int* bucket, int* temp, int n, int digit) {
int i, j = 0;
// 遍历桶数组,收集数据
for (i = 0; i < BUCKET_SIZE; i++) {
// 循环直到该桶的计数为0
while (bucket[i] > 0) {
// 遍历数据数组,找到对应的数字
for (int k = 0; k < n; k++) {
// 如果当前数字在当前位数上的值与桶的索引相等
if ((data[k] / digit) % 10 == i) {
// 将该数字收集到临时数组中
temp[j] = data[k];
j++;
// 将桶的计数减1
bucket[i]--;
}
}
}
}
// 将收集的数据复制回原始数据数组
for (i = 0; i < n; i++) {
data[i] = temp[i];
}
}
// 函数:基数排序
void radixSort(int* data, int n) {
int digit = 1;
int* temp = (int*)malloc(n * sizeof(int));
int bucket[BUCKET_SIZE] = { 0 };
// 进行MAX_DIGITS次分配和收集
for (int i = 0; i < MAX_DIGITS; i++) {
// 分配数据到桶中
distribute(data, bucket, n, digit);
// 收集数据从桶中
collect(data, bucket, temp, n, digit);
// 将位数乘以10(下一位)
digit *= 10;
// 重置桶数组
for (int j = 0; j < BUCKET_SIZE; j++) {
bucket[j] = 0;
}
// 打印当前的数据状态
printf("第 %d 趟分配 + 收集后的数据:\n", i);
for (int i = 0; i < n; i++) {
printf("%d ", data[i]);
}
printf("\n");
}
}
// 主函数
int main() {
int data[] = { 278, 109, 63, 930, 589, 184, 505, 269, 8, 83};
int n = sizeof(data) / sizeof(data[0]);
radixSort(data, n);
return 0;
}
10.6.2 链式基数排序
基数排序是借助 “分配“和“收集“ 两种操作对单逻辑关键字进行排序,并用链表作存储结构 的一种内部排序 方法。
基本步骤:
- 将数据分成多个桶,每个桶对应一个基数位
- 对每个桶进行排序,使用链表存储排序结果
- 迭代基数位,重复步骤1和2,直到所有基数位完成
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构,包含数据和指向下一个节点的指针
typedef struct Node {
int data;
struct Node* next;
} Node;
// 定义链表结构,包含头节点和尾节点
typedef struct List {
Node* head;
Node* tail;
} List;
// 初始化链表函数,设置头节点和尾节点为NULL
void initList(List* list) {
list->head = NULL;
list->tail = NULL;
}
// 插入节点到链表末尾
void insertNode(List* list, int data) {
// 分配新节点的内存
Node* newNode = (Node*)malloc(sizeof(Node));
// 设置新节点的数据
newNode->data = data;
// 置新节点的下一个节点为NULL
newNode->next = NULL;
// 如果链表为空,设置新节点为头节点和尾节点
if (list->head == NULL) {
// 设置头节点为新节点
list->head = newNode;
// 设置尾节点为新节点
list->tail = newNode;
}
// 如果链表不为空,插入新节点到尾节点后面
else {
// 设置尾节点的下一个节点为新节点
list->tail->next = newNode;
// 更新尾节点为新节点
list->tail = newNode;
}
}
// 打印链表
void printList(List* list) {
// 从头节点开始遍历链表
Node* current = list->head;
// 遍历链表,直到到达NULL
while (current != NULL) {
// 打印当前节点的数据
printf("%d ", current->data);
// 移动到下一个节点
current = current->next;
}
printf("\n");
}
// 分配节点到桶中的函数
void allocateNodes(List* list, List* bucket, int digit) {
// 分配节点到桶中
Node* current = list->head; // 从头节点开始遍历链表
while (current != NULL) {
// 计算当前节点的数据在当前位数上的值
int index = (current->data / digit) % 10;
// 将当前节点插入到对应的桶中
insertNode(&bucket[index], current->data);
// 移动到下一个节点
current = current->next;
}
}
// 收集节点从桶中的函数
void collectNodes(List* list, List* bucket) {
// 收集节点从桶中
list->head = NULL;// 重置头节点为NULL
list->tail = NULL;// 重置尾节点为NULL
for (int j = 0; j < 10; j++) {
// 从每个桶中收集节点
Node* current = bucket[j].head;// 从桶的头节点开始遍历
while (current != NULL) {
// 将当前节点插入到链表中
insertNode(list, current->data);
// 移动到下一个节点
current = current->next;
}
// 初始化每个桶
initList(&bucket[j]);
}
}
// 基数排序函数
void radixSort(List* list) {
int digit = 1; // 初始化位数为个位(1)
List bucket[10]; // 定义10个桶,用于存储不同位数的数据
for (int i = 0; i < 10; i++) {
// 初始化每个桶
initList(&bucket[i]);
}
// 进行3次分配和收集(针对3位数字)
for (int i = 0; i < 3; i++) {
// 分配节点到桶中
allocateNodes(list, bucket, digit);
// 收集节点从桶中
collectNodes(list, bucket);
// 将位数乘以10(下一位)
digit *= 10;
// 打印当前的数据状态
printf("第 %d 趟分配 + 收集后的数据:\n", i + 1);
printList(list);
}
}
int main() {
List list;
initList(&list);
int r[] = { 614,738,921,485,637,101,215,530,790,306 };
int i;
int n = sizeof(r) / sizeof(r[0]);
for (i = 0; i < n; i++)
{
insertNode(&list, r[i]);
}
// 插入示例数据
printf("原始数据:\n");
printList(&list);
radixSort(&list);
return 0;
}
适用范围:多关键字排序可以处理多种数据类型,而链式基数排序仅适用于整数或字符串数据。
时间复杂度: O(k*(n+m))
k:关键字个数,
m:关键字取值范围为m个值
空间复杂度: O(n+m)
稳定性: 稳定
10.7 各种内部排序方法的比较讨论
一、时间性能
-
按平均的时间性能来分,有三类排序方法:·
-
时间复杂度为O(nlogn)的方法有: 快速排序、堆排序和归并排序,其中以快速排序为最好
-
时间复杂度为O(n2)的有: 直接插入排序、冒泡排序和简单选择排序,其中以直接插入为最好
-
时间复杂度为O(n)的排序方法只有: 基数排序。
-
-
当待排记录序列按关键字顺序有序时,直接插入排序和冒泡排序达到O(n)的时间复杂度;
而对于快速排序而言,这是最不好的情况,此时的时间性能退化为O(n2),因此是应该尽量避免的情况。
二、空间性能:指的是排序过程中所需的辅助空间大小
-
所有的简单排序方法(包括:直接插入、冒泡和简单选择)和堆排序的空间复杂度为O(1)
-
快速排序为O(logn),为栈所需的辅助空间
-
归并排序所需辅助空间最多,其空间复杂度为O(n)
-
链式基数排序需附设队列首尾指针,则空间复杂度为O(rd)
参考:
教材:严蔚敏《数据结构》(C语言版).pdf
视频:
数据结构与算法基础(青岛大学-王卓)
表插入排序算法实现
博客:
2-路插入排序详解