【数据结构】：破译排序算法--数字世界的秩序密码（一）

一.排序算法概述

排序算法是计算机科学中非常重要的一部分，它们的主要目的是将一个数据集合（如数组或列表）中的元素按照一定的顺序（如升序或降序）重新排列。排序算法的应用非常广泛，从简单的数据整理到复杂的数据库管理系统，都离不开排序算法的支持。

1.定义和目的

定义：排序算法是指将一组数据按照特定的顺序进行排列的算法。

目的：使得数据在逻辑上或物理上按照一定的顺序进行排列，以便于后续的数据查找、处理和分析等操作。

2.排序算法的分类

排序算法可以根据不同的标准进行分类，其中最常见的分类方式是基于比较和非比较两种类型。

2.1比较排序

比较排序算法通过比较数据元素之间的大小关系来进行排序。这类算法的基本思想是：首先比较两个元素，如果它们的顺序错误就把它们交换过来；然后，对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这步做完后，最后的元素会是最大的数；接着，针对所有的元素（除了最后一个）重复以上的步骤，除了每次都比较到最后一对元素之外，每次比较的最后一对元素都是已经排好序的。这类排序算法的时间复杂度一般与数据的初始状态无关，主要取决于数据的规模。

2.2非比较排序

非比较排序算法则不依赖于元素之间的比较来进行排序。这类算法通常利用数据本身的特性（如元素的取值范围、数据的分布特性等）来设计排序算法。非比较排序算法的时间复杂度往往可以低于比较排序算法，但它们的适用范围相对较窄，且对数据的预处理要求较高。

二.插入排序算法

1.InsertSort直接插入排序

1.1.插入排序原理

• 插入排序的基本思想是将一个记录插入到已将排好序的有序表中，从而得到一个新的，记录数增加一的有序表。

• 在整个排序的过程中，始终维持着已将排好序的记录段，随着排序的过程的进行，不断增加这个有序段的长度，知道最后全部待排序的记录被插入到有序段中为止。

1.2.插入排序过程

1. 初始状态：将第一个元素视为已排序序列，剩下的元素视为未排序序列。

2. 选取元素：从未排序序列中取出第一个元素，记为当前元素。

3. 比较与移动：

   • 将当前元素与已排序序列最后一个元素进行比较。
   • 如果已排序序列最后一个元素小于当前元素，则不需要移动，直接将当前元素插入到已排序序列最后。
   • 如果已排序序列最后一个元素大于当前元素，将已排序序列最后一个元素后移一位，然后继续比较当前元素与已排序序列最后一个元素
   • 重复上述步骤，直到找到当前元素在已排序序列中的正确位置并将其插入。

4. 重复操作：从未排序序列中取出下一个元素，重复步骤2和3，直到未排序序列为空。

   

1.3.代码实现

void InsertSort(int*a,int n){for(int i=1;i<n;i++){int end=i-1;int tmp=a[i];while(end>=0){if(a[end]>tmp){a[end+1]=a[end];end--;}else{break;}}a[end+1]=tmp;}
}

1.4.复杂度和稳定性

• 时间复杂度：平均和最坏情况都是O(n^2)（当输入数组是逆序时，就是最坏情况），最好情况是O(n)（当输入数组是顺序时,就是最好情况）。
• 空间复杂度：O(1)，因为它是一种in-place排序算法。
• 稳定性：插入排序的稳定性是稳定，小的往前，大的不动。

2.ShellSort希尔排序

2.1.希尔排序原理

希尔排序是插入排序的一种更高效的改进版本，也称为缩小增量排序。希尔排序的基本思想是将待排序的数组元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的元素越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

2.2.希尔排序过程

1. 选择初始增量：选择一个初始的增量gap（步长），这个增量的选择对希尔排序的性能有很大影响。gap越大，大的数越快跳到后面，小的数越快跳到前面，常用的增量选择方式有希尔原始增量序列（N/2, N/4, …, 1）、Hibbard增量序列、Knuth增量序列、Sedgewick增量序列等。

2. 分组与排序：根据当前的增量gap，将数组分为若干个子序列，并对每个子序列进行预排序。

3. 减少增量：将增量gap减少（通常减半），然后重复步骤2，直到增量gap为1,也就是直接插入排序。

4. 最终排序：当增量gap为1时，整个数组被视为一组，进行最后一次直接插入排序，得到最终的有序序列。

   

2.3.代码实现

void ShellSort(int*a,int n){int gap=n;while(gap>1){gap/=2;for(int i=0;i<n-gap;i++){int end=i;tmp=a[i+gap];while(end>=0){if(a[end]>tmp){a[end+gap]=a[end];end-=gap;}else{break;}}a[end+gap]=tmp;}}
}

2.4.复杂度和稳定性

• 时间复杂度：希尔排序的时间复杂度依赖于增量gap的选择。在最坏情况下，时间复杂度为O(n^2) ，但在平均情况下，时间复杂度可以降到O(nlogn)到O(n^1.5)之间 。因为希尔排序时间复杂度较为复杂，所以直接记结论就可以，希尔排序时间复杂度约为O(n^1.3)。
• 空间复杂度：希尔排序是原地排序算法，空间复杂度为O(1)。
• 稳定性：希尔排序的稳定性是不稳定，比如相同的数据可能会被分配到不同的组预排序，从而打乱相同数据的原本顺序。

三.选择排序算法

1.SelectionSort简单选择排序

1.1.选择排序原理

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是：第1次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的元素中寻找最小（或最大）的元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素排完。

1.2.选择排序过程

1.设置下标：整体循环条件是左端下标（left)小于右端下标(right)，每次循环时都将最大值的下标(max)和最小值的下标(min)先设置为左端下标(left)。

2.查找下标：从左端下标（left）的下一个开始查找，找到最大值和最小值的下标。

3.交换：将最小值和左端（left）的值交换，最大值和右端（right）的值交换，如果最大值恰好在左端位置时，在最小值和左端（left）的值交换后，要先交换最大值和最小值的下标。才能再进行最大值和右端（right）的值交换。

4.重复操作：左右交换后，左端下标（left）加一，右端下标（right）减一，然后循环进行过程1,2,3。

1.3.代码实现

//交换函数
void Swap(int*a,int*b){int t=*a;*a=*b;*b=t;
}
void SelectSort(int*a,int n){//设置左端下标left,右端下标rightint left=0,right=n-1;while(left<right){//每次循环时设置最大值和最小值的下标从left开始int max=left,min=left;//循环遍历找到max，min的下标for(int i=left+1;i<n;i++){if(a[i]>a[max]){max=i;}if(a[i]<a[min]){min=i;}}//先将最左端的值和最小值交换Swap(&a[left],&a[min]);//当最大值下标等于左端下标时，max下标要变为min的下标if(left==max){max=min;}//再将最右端的值和最小端的值交换Swap(&a[right],&a[max]);//左端下标加一，右端下标减一left++;right--;}
}

1.4.复杂度和稳定性

• 时间复杂度 ： 选择排序的时间复杂度为O(n^2)，无论最好情况、最坏情况还是平均情况都如此。这是因为，即使输入数组已经是排序好的，选择排序仍然需要遍历数组来找到最小（或最大）的元素。
• 空间复杂度：选择排序的空间复杂度为O(1)，因为它只需要常数个额外的存储空间来存储临时变量。
• 稳定性：选择排序的稳定性是不稳定，比如数组【2,2,1,5,4】，第一个2和1交换后会改变原本数组中2,2,的相对位置，所以是不稳定的。

2.HeapSort堆排序

2.1.堆排序原理

堆排序(HeapSort)是一种基于比较的排序算法，其原理是利用堆这种数据结构所设计。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即每个节点总是大于或小于子节点（堆的详细讲解在我之前的文章中有讲解到，如果对堆有不了解的可以看我之前的文章）。

2.2.堆排序过程

堆排序的过程主要分为两个过程：

• 构建堆：将待排序的序列构建成最大堆（升序），此时，堆顶的根节点就是整个序列的最大值。（如果构建的是最小堆（降序），堆顶的根节点就是整个序列的最小值。）
• 堆排序：将堆顶元素最大值（或最小值）与堆的末尾元素交换，此时堆的末尾就是最大值（或最小值），然后将剩下的n-1个元素重新构建成堆，这样就会得到n个元素的次大值（或次小值），如此反复进行最后就会得到一个有序序列。

2.3.代码实现

//交换
void Swap(int*a,int*b){int t=*a;*a=*b;*b=t;
}
//向下调整
void AdjustDown(int*a,int n,int i){//参数i作为父节点，找到子节点int parent=i;int child=parent*2+1;while(child<n){//从左右子节点中选出较大的节点if(child+1<n&&a[child+1]>a[child]){child++;}//判断父子节点是否需要交换if(a[child]>a[parent]){Swap(&a[child],&a[parent]);}parent=child;child=parent*2;}
}void HeapSort(int*a,int n){//先将给定的一个数组用向下调整建堆，将数组调整成堆的形式for(int i=(n-1-1)/2;i>=0;i++){AdjustDown(a,n,i);}//每次将堆顶的元素和最后一个元素交换，从新建堆int end=n-1;while(end>=0){Swap(&a[0],&a[end]);AdjustDown(a,end,0);end--;}
}

2.4.复杂度和稳定性

• 时间复杂度：堆排序的平均时间复杂度和最坏时间复杂度均为O(n*log n)，（详细可以看我之前的文章）
• 空间复杂度：由于堆排序在构建堆和调整堆的过程中，都需要进行元素的比较和移动因此堆排序的空间复杂的是O（1），是一种原地排序算法。
• 稳定性：堆排序的稳定性是不稳定。

四.代码文件

这里附上整个代码文件：

• 头文件Sort.h
• 测试文件test.c
• 接口函数实现文件Sort.c(文件内容就是每个代码实现)

1.头文件Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>//遍历打印
void PrintArray(int* a, int n);
//插入排序
void InsertSort(int* a, int n);
//希尔排序
void ShellSort(int* a, int n);
//选择排序
void SelectSort(int* a, int n);
//交换
void Swap(int* a, int* b);
//向下调整
void AdjustDown(int* a, int n, int i);
//堆排序
void HeapSort(int* a, int n);

2.测试文件test.c

#include"sort.h"
//插入排序测试
void Inserttest() {int a[ ] = { 7,3,5,4,6};int n = (sizeof(a) / sizeof(int));InsertSort(a, n);printf("插入排序：\n");PrintArray(a, n);
}
//希尔排序测试
void Shelltest() {int a[ ] = {12,5,17,9,14,13,2,4,19};int n = (sizeof(a) / sizeof(int));ShellSort(a, n);printf("希尔排序：\n");PrintArray(a, n);
}
//选择排序测试
void Selecttest() {int a[ ] = { 3,6,4,2,11,10,5};int n = (sizeof(a) / sizeof(int));SelectSort(a, n);printf("选择排序：\n");PrintArray(a, n);
}
//堆排序测试
void Heaptest() {int a[ ] = { 3,12,7,3,1,5,24,9,8,10,2,4 };int n = (sizeof(a) / sizeof(int));HeapSort(a, n);printf("堆排序：\n");PrintArray(a, n);
}int main(){Inserttest();Shelltest();Selecttest();Heaptest();return 0;
}

3.测试结果

总结

本篇文章主要讲述了插入排序，希尔排序，选择排序和堆排序，剩下的冒泡排序，快速排序，归并排序和计数排序我将会放在下一篇文章中。
以上就是关于排序部分的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！