数据结构与算法(十九) -- 经典排序算法

一、简介

排序分为两种:

  1. 内排序: 在排序整个过程中, 待排序的所有记录全被放置在内存中

  2. 外排序: 由于排序的记录个数太多, 不能同时放置在内存, 整个排序过程需要在内外存之间多次交换数据才能进行.

二、排序算法

这里定义被排序数据的结构

//存放数据的结构体(0位置为哨兵)
typedef struct {
int r[MAXSIZE + 1];
int length;
} SqList;
//交换方法
void swap(SqList *L, int i, int j) {
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
//打印方法
void printList(SqList L) {
for (int i = 1; i <= L.length; i++) {
printf("%d ",L.r[i]);
}
}

2.1、冒泡排序

冒泡排序是一种交换排序, 它的基本思想就是: 两两比较相邻的记录的关键字, 如果反序则交换, 直到没有反序的记录为止.

2.1.1、初级冒泡排序

这是我们最开始学习冒泡排序的最基本版本, 但是它并不满足一个两两比较的排序, 它是一个基本的交换的排序.

void BubbleSort1(SqList *L) {
for (int i = 1; i <= L->length; i++) {
for (int j = i + 1; j <= L->length; j++) {
if (L->r[i] > L->r[j]) {
swap(L, i, j);
}
}
}
}

2.1.2、真正的冒泡排序

  1. 数据倒序开始, 相邻两两相互比较

  2. 将两个位置根据大小进行交换

  3. 直到达到第一个数据

  4. 此时第一数据为最小, 重新倒序两两比较, 直到到第二个数据

//冒泡排序
void BubbleSort2(SqList *L) {
for (int i = 1; i < L->length; i++) {
for (int j = L->length - 1; j >= i; j--) {
if (L->r[j] > L->r[j + 1]) {
swap(L, j, j+1);
}
}
}
}

2.1.3、冒泡排序的优化

在某些情况下, 冒泡排序进行一次后就达到了排序结果. 此时冒泡排序还会向下继续执行, 这样造成了不必要的浪费

那么我们就可以用一个变量来记录是否进行交换过. 只要这个记录表示没有交换过, 那么之前的数据也就是已经排序过的

void BubbleSort3(SqList *L) {
int flag = 1;
for (int i = 1; i < L->length && flag; i++) {
flag = 0;
for (int j = L->length - 1; j >= i; j--) {
if (L->r[j] > L->r[j + 1]) {
swap(L, j, j+1);
flag = 1;
}
}
}
}

2.2、简单选择排序

简单排序算法就是通过n-i次关键词比较, 从n-i+1个记录中找出关键字最小的记录, 并和第i(1<=i<=n)个记录进行交换

  1. 记录第1个数据i, 从第2个数据j开始遍历, 用min记录最小值, 默认为第1个数据

  2. 从j开始, 与min对比, 用min记录最小值

  3. 遍历完成后, 将i数据与min数据进行交换

  4. 重新循环, 记录第2个数据, 从第3个数据开始遍历

void SelectSort(SqList *L) {
int min;
for (int i = 1; i < L->length; i++) {
min = i;
for (int j = i + 1; j <= L->length; j++) {
if (L->r[min] > L->r[j]) {
min = j;
}
}
if (i != min) {
swap(L, i, min);
}
}
}

2.3、直接插入排序

直接插入排序算法的基本操作是将一个记录插入到已经排好序的有序表中, 从而得到一个新的记录数增1的有序表.

  1. 从第二个数据i开始倒序遍历, 此时i与i-1进行对比

  2. 如果i < i-1, 那么用临时变量temp记录 i 的值

  3. 此时j=i-1, 遍历 j in [1, i - 1], 只要比temp大值都要向后挪动, 直到碰到比temp小或者到数据头

void InsertSort(SqList *L) {
int temp, j;
for (int i = 2; i < L->length; i++) {
if (L->r[i] < L->r[i - 1]) {
temp = L->r[i];
for (j = i - 1; L->r[j] > temp; j--) {
L->r[j + 1] = L->r[j];
}
L->r[j + 1] = temp;
}
}
}

2.4、希尔排序

希尔排序是基于插入排序所得到的一个优化. 在插入排序之前, 将整个序列调整成基本有序. 然后再对全体序列进行一次直接插入排序.

希尔排序思想: 希尔排序是把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序; 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至1时,整个序列恰被分成一组, 算法结束.

例如: {2, 1, 3, 6, 4, 7, 5, 8, 9} 为基本有序, {1, 5, 9, 3, 7, 8, 2, 4, 6}不是基本有序

  1. 首先根据数据长度len得到一个增量序列 increment = len / 2 (自定义增量序列)

  2. 从第二段数据(increment)的位置i开始向后遍历

  3. 判断当前数据 i 是否小于 i - increment 的值, 如果小于则进行交换并记录i位置的值

  4. 此时需要进行插入排序, 记录当前j = i - increment, 从j倒序向前增量遍历. 进行后移

  5. 找到合适的位置放入记录的值

//希尔排序
void ShellSort(SqList *L) {
int i, j;
int increment = L->length;
do {
increment = increment / 3 + 1;
for (i = increment + 1; i < L->length; i++) {
if (L->r[i] < L->r[i - increment]) {
//插入
L->r[0] = L->r[i];
for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment) {
L->r[j + increment] = L->r[j];
}
L->r[j + increment] = L->r[0];
}
}
} while (increment > 1);
}

2.5、堆排序

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

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

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

堆排序思路:

  • 将无序序列构建称一个堆, 根据升降序需求选择大顶堆或小顶堆

  • 将堆顶元素与末尾元素交换, 将最大元素沉到数组末端

  • 重新调整结构, 使其满足堆定义, 然后继续交换堆顶元素与当前末尾元素, 反复执行调整+交换步骤, 直到整个序列有序

//堆排序
/*
* 已知L->r[s..m]中记录的关键字出L->r[s]之外均满足堆的定义
* 本函数调整L->[s]的关键字, 使L->r[s..m]成为一个大顶堆
*/
void HeapAjust(SqList *L, int s, int m) {
int temp, j;
temp = L->r[s];
for (j = 2 * s; j <= m; j *= 2) {
if (j < m && L->r[j] < L->r[j + 1]) {
++j;//记录较大元素的下标
}
if (temp >= L->r[j]) {
break;//此处根节点大于左右子节点
}
L->r[s] = L->r[j];//将最大的节点放到根节点
s = j;//交换最大节点位置与根节点位置
}
L->r[s] = temp;//将最大节点的位置更新为之前的根节点
}
void HeapSort(SqList *L) {
int i;
for (i = L->length / 2; i > 0; i++) {
HeapAjust(L, i, L->length);
}
for (i = L->length; i > 1; i--) {
swap(L, 1, i);
HeapAjust(L, 1, i - 1);
}
}

2.6、归并排序

归并排序就是利用归并的思想实现的排序方法. 他的原理是: 假设初始序列为 n 个记录, 则看成 n 个有序的子序列, 每个子序列的长度为1, 然后两两归并, 得到[n/2]个长度为2或1的有序子序列. 再两两归并... 如此重复直到得到一个长度为n的有序序列

void Merge(int SR[], int TR[], int i, int m, int n) {
int j = 0, k = 0, l = 0;
for (j = m + 1, k = i; j <= n && i <= m; k++) {
if (SR[i] < SR[j]) {
TR[k] = SR[i++];
} else {
TR[k] = SR[j++];
}
}
if (i <= m) {
for (l = 0; l <= m - i; l++) {
TR[k + l] = SR[i + l];
}
}
if (i <= n) {
for (l = 0; l <= n - i; l++) {
TR[k + l] = SR[j + l];
}
}
}
/*
* SR 待排序数组
* TR1 排序后的有序数组
* low 低位
* hight 高位
*/
void MSort(int SR[], int TR1[], int low, int hight) {
int mid;
int TR2[MAXSIZE + 1];
if (low == hight) {
TR1[low] = SR[low];
} else {
mid = (low + hight) / 2;
//递归SR[low, mid]
MSort(SR, TR2, low, mid);
//递归SR[mid+1, hight]
MSort(SR, TR2, mid + 1, hight);
//归并
Merge(SR, TR1, low, mid, hight);
}
}
void MergeSort(SqList *L) {
MSort(L->r, L->r, 1, L->length);
}

归并排序大量引用了递归, 尽管这样代码比较清晰, 但是在时间和空间上会造成损耗. 所以可以不使用递归的方法, 直接将无序数组进行分割:

void MergePass(int SR[], int TR[], int s, int length) {
int i = 1;
int j;
while (i <= length - 2 * s + 1) {
Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
i = i + 2 * s;
}
if(i < length - s + 1){
//Merge(SR,TR,1,8,9)
Merge(SR, TR, i, i+s-1, length);
}else{
//只剩下一个子序列;
for (j = i; j <=length; j++) {
TR[j] = SR[j];
}
}
}
void MergeSort2(SqList *L){
int *TR = (int *)malloc(sizeof(int) * L->length);
int k = 1;
//k的拆分变换是 1,2,4,8;
while (k < L->length) {
//将SR数组按照s=2的长度进行拆分合并,结果存储到TR数组中;
//注意:此时经过第一轮的归并排序的结果是存储到TR数组了;
MergePass(L->r, TR, k, L->length);
k = 2*k;
//将刚刚归并排序后的TR数组,按照s = 2k的长度进行拆分合并. 结果存储到L->r数组中;
//注意:因为上一轮的排序的结果是存储到TR数组,所以这次排序的数据应该是再次对TR数组排序;
MergePass(TR, L->r, k, L->length);
k = 2*k;
}
}

2.7、快速排序

快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分, 其中一部分记录的关键字均比另一部分记录的关键字小, 则可以分别对这两部分记录继续进行排序. 达到整个序列有序的目的

执行步骤:

  1. 首先取第一个数为枢轴

  2. 从高位开始倒序查找, 找到第一个小于枢轴的值i, 将枢轴位置与这个i进行交换

  3. 从高位找到一个小于枢轴的值之后, 从低位开始, 找到第一个大于枢轴的值j, 将枢轴位置与这个j进行交换

  4. 直到 i 与 j 的位置相遇, 即将原始序列分为了两个序列, 分别对这两个序列重复此操作

int Partition(SqList *L, int low, int hight) {
int pivotkey;
pivotkey = L->r[low];
while (low < hight) {
while (low < hight && L->r[hight] >= pivotkey) {
hight--;
}
swap(L, low, hight);
while (low < hight && L->r[low] <= pivotkey) {
low++;
}
swap(L, low, hight);
}
return low;
}
void QSort(SqList *L, int low, int hight) {
int pivot;
if (low < hight) {
pivot = Partition(L, low, hight);
QSort(L, low, pivot - 1);
QSort(L, pivot + 1, hight);
}
}
void QuickSort(SqList *L) {
QSort(L, 1, L->length);
}

以上是 数据结构与算法(十九) -- 经典排序算法 的全部内容， 来源链接： utcz.com/a/26584.html

回到顶部