江小南
2022/12/22阅读：35主题：萌绿
【408篇】C语言笔记-第十六章（考研必会的排序算法（上））
第一节：冒泡排序
1. 排序
排序算法分为交换类排序，插入类排序，选择类排序，归并类排序：
交换排序分为：1.冒泡排序。2.快速排序
2. 冒泡排序
基本思想：从后往前（或从前往后）两两比较相邻元素的值，若A[j-1]>A[j]（或A[j-1]<A[j]），则交换他们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置。关键字最小的元素如起泡一般逐渐往上“漂浮”直至“水面”。下一趟冒泡时，前一趟确定的最小元素不在参与比较，每一趟冒泡的结果是把序列中最小的元素放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
动画演示： https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
第二节：冒泡排序实战
1. 步骤
随机生成10个元素->打印生成的元素顺序->通过冒泡排序对元素进行排序->再次打印元素顺序。
2. 代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
ElemType *elem; // 整型指针
int TableLen; // 存储动态数组里边元素的个数，相当于之前的len
}SSTable;
// 初始化链表
void ST_Init(SSTable &ST,int len){
ST.TableLen=len;
ST.elem= (ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
int i;
srand(time(NULL));// 生成随机数
for(i=0;i<ST.TableLen;i++){
ST.elem[i]=rand()%100; // 为了让随机数在0-99之间
}
}
// 打印
void ST_print(SSTable ST){
for(int i=0;i<ST.TableLen;i++){
printf("%3d",ST.elem[i]);// 和获取数组方法一样
}
printf("\n");
}
void swap(ElemType &a,ElemType &b){
ElemType tmp;
tmp=a;
a=b;
b=tmp;
}
// 冒泡排序
void BubbleSort(ElemType A[],int n){
int i,j;
bool flag;
for(i=0;i<n-1;i++){ // i最多访问到8
flag= false;
for(j=n-1;j>i;j--){
if(A[j-1]>A[j]){
swap(A[j-1],A[j]);
flag=true;
}
}
if(flag==false){// 如果一趟比较没有发生任何交换，说明有序，提前结束排序
return;
}
}
}
int main() {
SSTable ST;
ST_Init(ST,10);
ST_print(ST);
BubbleSort(ST.elem,10);
ST_print(ST);
return 0;
}
F:\Computer\Project\practice\16\16.4-Bubbling\cmake-build-debug\16_4_Bubbling.exe
29 52 39 55 20 43 16 89 61 6
6 16 20 29 39 43 52 55 61 89
进程已结束，退出代码为 0
3. 时间复杂度与空间复杂度
时间复杂度实际就是程序运行的实际次数。内层是j>i，外层i的值是0到n-1，所以程序运行总次数是1+2+3+……+（n-1），这是等差数列求和，得到的结果是n(n-1)/2，忽略低阶项和高阶项的首项系数，时间复杂度为O( )。
由于没有使用额外空间，所以空间复杂度为O(1)。
冒泡排序考研中以选择题为主。
第三节：快速排序原理与实战
1. 基本思想
快速排序的核心是分治思想：假设我们的目的依然是从小到大的顺序排列。我们找到数组中的一个分割值，把比分割值小的数都放在数组的左边，把比分割值大的数都放在数组的右边，这样分割值的位置就被确定。数组一分为二，我们只需排前一半数组和后一半数组。复杂度直接减半。采用这种思想，不断地进行递归，最终分割得只剩下一个元素，整个序列自然就是有序的。
动画演示： https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
2. 快速排序实战
步骤：随机生成10个元素->打印生成的元素顺序->通过快速排序对元素进行排序->再次打印元素顺序。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
ElemType *elem; // 整型指针
int TableLen; // 存储动态数组里边元素的个数，相当于之前的len
}SSTable;
// 初始化链表
void ST_Init(SSTable &ST,int len){
ST.TableLen=len;
ST.elem= (ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
int i;
srand(time(NULL));// 生成随机数
for(i=0;i<ST.TableLen;i++){
ST.elem[i]=rand()%100; // 为了让随机数在0-99之间
}
}
// 打印
void ST_print(SSTable ST){
for(int i=0;i<ST.TableLen;i++){
printf("%3d",ST.elem[i]);// 和获取数组方法一样
}
printf("\n");
}
void swap(ElemType &a,ElemType &b){
ElemType tmp;
tmp=a;
a=b;
b=tmp;
}
int Partition(ElemType A[],int low,int high){
ElemType pivot=A[low]; // 首先使用左边变量存储分割值
while (low<high){
while (low<high && A[high]>=pivot ){ // 从后往前遍历，找到一个比分割值小的
high--;
}
A[low]=A[high]; // 把比分割值小的那个元素，当道A[low]
while (low<high && A[low]<=pivot ){ // 从前往后遍历，找到一个比分割值大的
low++;
}
A[high]=A[low]; // 把比分割值大的那个元素，放到A[high]，因为刚才high位置的元素已经放到low位置了
}
A[low]=pivot;
return low; // 返回分割值所在的下标
}
// 快速排序
void QuickSort(ElemType A[],int low,int high){
if(low<high){
int pivotpos=Partition(A,low,high); // 分割点左边的元素逗比分割点要小，右边的元素都比分割点大
// printf("%d\n",pivotpos);
QuickSort(A,low,pivotpos-1);
QuickSort(A,pivotpos+1,high);
}
}
int main() {
SSTable ST;
ST_Init(ST,10);
ST_print(ST);
QuickSort(ST.elem,0,9);
ST_print(ST);
return 0;
}
F:\Computer\Project\practice\16\16.6-quick\cmake-build-debug\16_6_quick.exe
55 72 33 14 44 48 47 97 73 39
14 33 39 44 47 48 55 72 73 97
进程已结束，退出代码为 0
3. 时间复杂度与空间复杂度
最好和平均时间复杂度为O( )，最差为O( )
空间复杂度是O( )，因为递归的次数是 ，而每次递归的形参都是需要占用空间的。
快速排序考研中大题概率较高。
第四节：插入排序原理及实战
1. 插入排序原理解析
插入排序分为：1.直接插入排序。2.折半插入排序。3.希尔排序。
考研选择题为主。
这里只讲直接插入排序的原理和实战。
如果一个序列只有一个数，那么该序列自然是有序的。插入序列首先将第一个数视为有序序列，然后把后面9个数视为依次要插入的序列。首先，我们通过外层循环控制要插入的数，用insertVal保存要插入的值87，我们比较arr[0]是否大于arr[1]，即3是否大于87，由于不大于，因此不发生移动，这时有序序列是3,87。接着，将数值2插入有序序列，首先将2赋给insertVal，这时判断87是否大于2，因为87大于2，所以将87向后移动，将2覆盖，然后判断3是否大于2，因为3大于2，所以3移动到原来87的位置。内层循环结束，这时将2赋给arr[0]，也就是原来3的位置。继续循环会将数依次插入有序序列，最终使整个数组有序。
动画演示： https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
2. 代码实战
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
ElemType *elem; // 整型指针
int TableLen; // 存储动态数组里边元素的个数，相当于之前的len
}SSTable;
// 初始化链表
void ST_Init(SSTable &ST,int len){
ST.TableLen=len;
ST.elem= (ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
int i;
srand(time(NULL));// 生成随机数
for(i=0;i<ST.TableLen;i++){
ST.elem[i]=rand()%100; // 为了让随机数在0-99之间
}
}
// 打印
void ST_print(SSTable ST){
for(int i=0;i<ST.TableLen;i++){
printf("%3d",ST.elem[i]);// 和获取数组方法一样
}
printf("\n");
}
// 插入排序
void InsertSort(ElemType *arr,int n){
int i,j,insertVal;
for(i=1;i<n;i++){ // 外层控制要插入的数
insertVal=arr[i]; // 先保存要插入的值
for(j=i-1;j>=0&&arr[j]>insertVal;j--){ // 内层控制比较j要大于等于0，同时arr[j]大于insertval,arr[j]位置元素往后覆盖
arr[j+1]=arr[j];
}
arr[j+1]=insertVal;
}
}
int main() {
SSTable ST;
ST_Init(ST,10);
ST_print(ST);
InsertSort(ST.elem,10);
ST_print(ST);
return 0;
}
F:\Computer\Project\practice\16\16.7-insert\cmake-build-debug\16_7_insert.exe
19 41 89 67 1 57 57 15 53 66
1 15 19 41 53 57 57 66 67 89
进程已结束，退出代码为 0
3. 时间复杂度与空间复杂度
随着有序序列不断增加，插入排序比较的次数也会增加，插入排序的执行次数也是从1加到n-1，总运行次数为n(n-1)/2，所以时间复杂度为O( )。因为未使用额外的空间，所以空间复杂度为O(1)。
如果数组本身有序，那么最好的时间复杂度是O(n)。
作者介绍