C语言数据结构与算法笔记（排序算法）

🕗 发布于 2024-03-19 09:05 c语言 数据结构 排序算法

排序算法

基础排序

冒泡排序

核心为交换，通过不断进行交换，将大的元素一点一点往后移，每一轮最大的元素排到对应的位置上，形成有序。
设数组长度为N，过程为:

共进行N轮排序
每一轮排序从数组的最左边开始，两两元素进行比较，左边元素大于右边元素，就交换两个元素的位置，否则不变。
每轮排序都会将剩余元素中最大的一个推到最右边，下次排序就不再考虑对应位置的元素。

注意交换不能直接进行，需要中间元素。
实际上排序不需要N轮，N-1轮即可，最后一轮只有一个元素未排序。

// 冒泡排序
void BubbleSort(int arr[], int size)
{
    for(int i = 0; i < size-1 ;++i) // 减1是不考虑最后一次交换
    {
        for(int j = 0 ; j < size - i - 1; ++j )
        {
            if(arr[j] > arr[j+1])
            {
                int tmp = arr[j]; // 加入中间元素tmp进行交换
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

int main()
{
    int size = 7;
    int arr1[] = {2,4,1,7,4,9,3};
    BubbleSort(arr1, size);
    for(int i = 0 ; i < size;++i)
    {
        printf("%d ", arr1[i]);
    }
}

优化：如果整轮排序中没有出现任何交换，则说明数组是有序的，内层循环中加入标记
没有发生任何交换，则flag一定是1，数组有序

// 改进：没有出现交换则已经有序
void BubbleSort1(int arr[], int size)
{
    for(int i = 0 ; i < size - 1; ++i)
    {
        _Bool flag = 1; // 加入标记
        for(int j = 0 ; j < size - 1 - i; ++j)
        {   
            int tmp =arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
        if(flag)
        {
            break;
        }
    }
}

排序稳定性，大小相同的两个元素在排序前和排序后的先后顺序不变，则排序算法就是稳定的。比如以上的冒泡排序法只会在前者大于后者的情况下才会发生交换，不会影响到相等的两个元素。

插入排序

类似于斗地主的插牌。默认一开始只有第一张牌是有序的，剩余部分进行遍历，然后插到前面对应的位置上。
设数组长度为N

一共进行N轮排序
每轮排序会从后面依次选择一个元素，与前面已经处于有序的元素，从后往前比较，直到遇到一个不大于当前元素的元素，将当前元素插入到此元素的前面。
插入元素后，后续元素则全部后移一位。
当后面所有元素全部遍历完成，全部插入到对应位置之后结束排序。

// 插入排序
void InsertSort(int arr[], int size)
{
    for(int i = 1; i < size -1; ++i) // 从第2个元素开始
    {
        int tmp = arr[i], j = i;
        while (j > 0 && arr[j-1] > tmp) // 只要j>0并且前一个元素大于当前元素
        {
            arr[j] = arr[j-1]; // 交换前一个元素
            j--;
        }
        arr[j] = tmp;
    }
}
int main()
{
    int arr1[] = {2,1,8,5,6,4};
    InsertSort(arr1, 6);
    printArray(arr1, 6);     
}

改进：寻找插入位置上逐个比较，花费时间长，如果前面一部分元素已经是有序状态，可以考虑使用二分搜索算法来查找对应的插入位置，节省插入点的时间。

// 二分搜索法
int BinarySearch(int arr[], int left, int right, int target)
{
    int mid;
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(target == arr[mid])
        {
            return mid + 1;
        }
        else if (target < arr[mid])
        {
            right = mid - 1; // 目标值小于中间的值，往左边去找
        }
        else
        {
            left = mid + 1; // 往右边去找
        }
    }
    return left; // 二分划分范围，left就是插入的位置
}
// 改进的插入排序
void InsertSort1(int arr[], int size)
{
    for(int i = 0 ; i < size; ++i)
    {
        int tmp = arr[i];
        int j = BinarySearch(arr,0,size-1,arr[i]); // 二分搜索查找插入的位置
        for( int k = i ; k > j; k--)
        {
            arr[k] = arr[k-1]; // 往后移
        }
        arr[j] = tmp;
    }
}

算法稳定性，在优化前的插入排序，实际上是不断向前寻找一个不大于待插入元素的元素，相等时只会插入到其后面，不会修改相等元素的顺序；而改进后的二分搜索法，可能会将两个连续相等元素分割开来。

选择排序

每次都去后面找一个最小的放到前面。
设数组长度为N

共进行N轮排序
每轮排序会从后面的所有元素中寻找一个最小的元素，与已经排序好的下一个位置进行互换
进行N轮交换后，得到有序数组

// 选择排序
void SelectSort(int arr[], int size)
{
    for(int i = 0 ; i < size - 1; ++i) // N-1轮排序
    {
        int min = i ; // 记录当前最小的元素，默认是剩余元素中的第一个
        for(int j = i + 1; j < size;++j)
        {
            if(arr[min] > arr[j])
            {
                min = j; 
            }
            int tmp = arr[i]; // 找出最小元素之后，开始交换
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
}
// 打印
void printArray(int arr[],int size)
{
    for(int i = 0 ; i < size;++i)
    {
        printf("%d ", arr[i]);
    }
}
int main()
{
    int arr1[] = {2,9,6,8,3,6,5};
    SelectSort(arr1 , 7);
    printArray(arr1, 7);
}

改进：因为每次需要选一个最小的，不妨顺便选个最大的，小的往左边丢，大的往右边丢。

// 交换
void swap(int* a, int*b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
// 优化的选择排序
void SelectSort1(int arr[], int size)
{
    int left=0, right = size - 1; // 假设左右排好序，往中间缩小
    while (left < right)
    {
        int max = right, min = left;
        for(int i = left; i < right; ++i)
        {
            // 同时找最大和最小的
            if(arr[i] < arr[min])
            {
                min = i;
            }
            if(arr[i] > arr[max])
            {
                max = i;
            }
        }
        swap(&arr[max], &arr[right]); // 先把大的换到右边
        // 大的换到右边之后，有可能被换出来的是最小的，需要判断以下
        // 如果遍历完最小的是当前右边排序的第一个元素
        // 将min换到那个位置
        if(min == right)
        {
            min = max;
        }
        swap(&arr[min], &arr[left]);
        left++;
        right--;
    }  
}

稳定性：由于每次寻找的是最小的元素，向前插入时会发生交换操作，当存在两个连续相等元素，破坏了原有的顺序。不稳定的。

比较三种基础排序

冒泡排序（优化后）

最好情况时间复杂度：O(n)，本身是有序的，只需要一次遍历。
最坏情况时间复杂度：O(n^2)，倒序。
空间复杂度：O(1)，只需要一个变量存储需要交换的变量
稳定
插入排序
最好情况时间复杂度：O(n)，本身是有序的，插入的位置也是同样的位置，不变动任何元素
最坏情况时间复杂度：O(n^2)，倒序。
空间复杂度：O(1)，只需要一个变量存储抽出来的元素
稳定
选择排序
最好情况时间复杂度：O(n^2)，即使数组本身是有序的，每一轮还得将剩余部分依次找完才确定最小的元素
最坏情况时间复杂度：O(n^2)
空间复杂度：每一轮需要记录最小元素位置，空间复杂度为O(1)
不稳定

进阶排序

快速排序

快速排序是冒泡排序的进阶版，由于冒泡排序是对相邻元素进行比较和交换，每次只能移动一个位置，效率相对较低；而快速排序是从两端向中间进行，一轮就可将较小的元素交换到左边，较大的元素交换到右边。

实际上每一轮目的就是将较大的丢到基准右边，较小的丢到基准左边

一开始排序为整个数组
排序之前，以第一个元素作为基准
从最右边向左看，依次将每一个元素与基准元素进行比较，如果该元素比基准元素小，就与左边遍历位置上的元素（一开始为基准元素位置）进行交换，保留右边当前遍历的位置
交换后，转为从左边往右开始遍历元素，如果发现比基准元素大，则与之前保留右边遍历的位置上元素进行交换，同样保留左边当前遍历的位置
当左右遍历撞到一起，本轮快速排序完成，中间的位置元素就是基准元素
以基准位置为中心，划分左右两边，同样方式进行

代码实现

// 快速排序
void QuickSort(int arr[], int start, int end)
{
    if(start >= end) // 不满足初始位置则返回
    {
        return;
    }
    int left = start, right = end; // 定义两个指向左右两个端点的指针
    int pivot = arr[left]; // 预先确定基准点为左端第一个元素
    while (left < right)
    {
        while(left < right && arr[right] >= pivot)
        {
            right--;// 从右往左看
        }
        arr[left] = arr[right]; // 比基准值小就放到左边去
        while (left < right&& arr[left]  <= pivot)
        {
            left++; // 从左往右看
        }
        arr[right] = arr[left]; // 比基准值大就放到右边
        arr[left] =pivot; //相遇位置即为基准存放的位置
    }
    QuickSort(arr, start , left-1); //划分基准左边
    QuickSort(arr, left+1, end); // 划分基准右边， 再次进行快速排序
}

测试

int main()
{
    int arr1[]= {9,3,6,3,4,8,1,2};
    QuickSort(arr1, 0 , 8);
    for(int i = 0; i < 8 ; ++i)
    {
        printf("%d ", arr1[i]);
    }
}

双轴快速排序

快速排序的升级版，双轴快速排序，可对大数组进行。如果遇到数组完全倒序的情况
在这里插入图片描述
每一轮需要完整遍历整个范围，每一轮最大或最小的元素被推向两边，则此完全倒序情况快速排序退化为冒泡排序。为解决这种极端情况，再添加一个基准元素，使得数组可分为三段。

分为三段后，每轮双轴排序结束后对三段继续进行双轴快速排序。该适用于那些量比较大的数组。

首先取出首元素和尾元素作为两个基准，对其进行比较，若基准1大于基准2，先交换两个基准。
在这里插入图片描述
需要创建三个指针

从橙色指针所指元素开始进行判断，

小于基准1，那需要先将蓝色指针向后移，把元素交换到蓝色指针那去，然后橙色指针也向后移动
不小于基准1且不大于基准2，直接把橙色指针向前移动即可
大于基准2，需要丢到右边去，先将右边指针左移，不断向前找到一个比基准2小的，进行交换
橙色指针与绿色指针之间即为待排序区域

代码实现：

void swap(int* a, int*b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void dualPivotQuickSort(int arr[], int start, int end)
{
    if(start >= end)
    {
        return; // 结束条件
    }
    if(arr[start] > arr[end]) // 首尾两个基准比较
    {
        swap(&arr[start], &arr[end]); // 大的换到后面
    }
    int pivot1 = arr[start], pivot2 = arr[end]; // 取出两个基准元素
    int left = start, right = end, mid = left + 1; // 分三个区域，三个指针
    while (mid < right)
    {
        if(arr[mid] < pivot1) // mid所指向元素小于基准1，需要放到最左边
        {
            swap(&arr[++left], &arr[mid++]); // 和最左边交换，left 和 mid向前移动
        }
        else if(arr[mid] <= pivot2) // 不小于基准1但小于基准2，在中间
        {
            mid++; // 本身在中间，向前移动以缩小范围
        }
        else // 右边的情况
        {
            while (arr[--right] > pivot2 && right > mid); // 先移动右边指针，需要右边位置来存放需要换过来的元素
            
            if(mid >= right)
            {
                break; // 剩余元素找完，没有比基准2小的，可直接结束
            }
            swap(&arr[mid], &arr[right]); // 还有剩余元素，找到比基准2小的，直接交换   
        }
    } 
    swap(&arr[left], &arr[start]); // 基准1与left交换，基准1左边元素都比其小
    swap(&arr[right],&arr[end]); // 基准2与right交换，基准2右边元素都比其大
    // 继续对剩下三个区域双轴快速排序
    dualPivotQuickSort(arr, start,left-1);
    dualPivotQuickSort(arr, left+1, right-1);
    dualPivotQuickSort(arr, right+1, end);
}

    dualPivotQuickSort(arr1, 0, 8);
    for(int i = 0; i < 8 ; ++i)
    {
        printf("%d ", arr1[i]);
    }

希尔排序（缩小增量排序）

直接插入排序的进阶版，极端情况会出现让所有已排序元素后移的情况（比如刚好要插入的是一个特别小的元素），为解决这种问题，对整个数组按照步长进行分组，优先比较距离较远的元素。

步长是由一个增量序列，当增量序列一般使用 $\frac{n}{2}、\frac{n}{4}、\frac{n}{8}...、1$ 这样的序列。
设数组长度为N，详细过程为:

求出最初步长,n/2
整个数组按照步长进行分组，两两一组（n为奇数，第一组有三个元素）
分别在分组内插入排序
排序后，将步长/2，重新分组，重复上述步骤，直到步长为1，插入排序最后一遍结束

插入排序后，小的元素尽可能地向前走，缩小步长，4/2=2

代码实现

// 希尔排序
void shellSort(int arr[], int size)
{
    int delta = size / 2;
    while (delta >= 1) // 使用之前的插入排序，此时需要考虑分组
    {
        for(int i = delta; i < size; ++i) // 从delta开始，前delta个组的第一个元素默认是有序状态
        {
            int j = i, tmp = arr[i]; // 依然是把待插入的先抽出来
            while (j >= delta && arr[j - delta] > tmp) 
            {
                // 需要按步长往回走，所以是j-delta，j必须大于等于delta才可以,j-delta小于0说明前面没有元素
                arr[j] = arr[j - delta];
                j -= delta;
            }
            arr[j] = tmp;
        }
        delta /= 2; // 分组插排结束之后，再计算步长
    }
} 
int main()
{
    int arr[] = {3,5,7,2,9,0,6,1,8,4};
    shellSort(arr, 10);
    for(int i = 0 ; i < 10; ++i)
    {
        printf("%d ", arr[i]);
    }
}

尽管有循环多次，但时间复杂度比O(n^2)小，小的元素往左靠。希尔排序不稳定，因为按步长分组，有可能相邻得两个相同元素，后者在自己组内被换到前面去。

堆排序

选择排序一种，但能比选择排序更快。
小根堆（小顶堆），对一棵不完全二叉树，树中父亲结点都比孩子结点小；大根堆（大顶堆）树中父亲结点都比孩子节点大。
堆是一棵完全二叉树，数组来表示
在这里插入图片描述
构建一个堆，将一个无序的数组依次输入，最后存放的序列是一个按顺序排放的序列。

但仍需要额外O(n)的空间作为堆，可以对其进一步优化，减少空间上的占用。直接对给定的数组进行堆的构建
设数组长度为N

将给定数组调整为大顶堆
进行N轮选择，每次选择大顶堆顶端元素从数组末尾开始向前存放（交换堆顶和堆的最后一个元素）
交换完成后，重新对堆的根节点进行调整，使其继续满足大顶堆的性质
当N轮结束后，得到从小到大的数组

原文地址：https://blog.csdn.net/DarlingLSA/article/details/136698098

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：MySQL面试题之基础夯实
下一篇：爬虫加密算法

UML概述、类图关系及连接线表示
继承和实现体现的是一种类与类、或者类与接口间的纵向关系;依赖关联聚合组合体现的是类与类、类与接口间的引用，即横向关系;这几种关系，所表现的强弱程度依次为：组合 > 聚合 > 关联 >
阅读更多2024-11-17
131. HTML标签遮挡Canvas画布事件
HTML元素标签外面div父元素遮挡了Canvas画布鼠标事件，会造成相机控件的旋转、缩放等操作无效，也有可能会影响你的射线拾取,等等任何与canvas画布有关的鼠标事件都有可能收到影响，不过这算是普
阅读更多2024-11-17
Scala-字符串（拼接、printf格式化输出等）-用法详解
Scala-字符串（拼接、printf格式化输出等）用法
阅读更多2024-11-17
c++原型模式（Prototype Pattern）
每个原型类实现自己的克隆方法，从而确保了对象的正确复制。
阅读更多2024-11-17
问题大集-01-kafka问题
1、Windows下启动单机kafka出现：系统找不到指定路径解决：是kafka不能识别本机的java环境（JVM），故需要指定java路径，进入kafka路径下的\bin\windows，找到：ka
阅读更多2024-11-17
【点云上采样】最近邻插值上采样算法增加点云密度
传感器采集到的点云比较稀疏，毕竟价位在那，好的太贵，买便宜的点又太稀，需要增加点云数据。
阅读更多2024-11-17
阮一峰科技爱好者周刊（第 325 期）推荐工具：一个基于 Next.js 的博客和 CMS 系统
近期，阮一峰在科技爱好者周刊第 325 期中推荐了一款开源工具——ReactPress，ReactPress一个基于 Next.js 的博客和 CMS 系统，可查看 demo站点。（@fecommun
阅读更多2024-11-17
js识别二维码
将二维码转换为链接
阅读更多2024-11-17
C 语言【单链表】
‌数据域用于存储实际的数据，而指针域则存储指向下一个节点的地址。单链表的特点包括动态存储、非连续存储、易于插入和删除。节点可以定义成一个结构体，每个节点中包含一个数据和下一个节点的地址。上面的结构体定
阅读更多2024-11-17
校园求职招聘系统（程序+数据库+报告）
基于Spring Boot框架实现的校园求职招聘系统，系统包含两种角色：管理员、用户,系统分为前台和后台两大模块
阅读更多2024-11-17