江小南

V1

2022/12/22阅读:20主题:萌绿

【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)。

分类:

后端

标签:

C++

作者介绍

江小南
V1