C/C++ 数据结构与算法【排序】 常见7大排序详细解析【日常学习，考研必备】带图+详细代码

ops/2025/1/15 0:26:56/

常见7种排序算法

算法复杂度

在这里插入图片描述
在这里插入图片描述

1、冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换位置。这个过程持续对数列的末尾进行，直到整个数列都排序完成。

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N)
空间复杂度：O(1)

在这里插入图片描述

/* 冒泡排序 */
void BubbleSort(int arr[], int len) // arr： 需要排序的数组； length： 数组长度 注： int cnt = sizeof(a) / sizeof(a[0]);获取数组长度
{for (int i = 0; i < len; i++){for (int j = 0; j < len -  i - 1; j++){if (arr[j] > arr[j + 1]){int temp;temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}}
}

2、选择排序

选择排序是一种简单直观的排序算法，其基本原理是每一次从待排序的数组里找到最小值（最大值）的下标，然后将最小值（最大值）跟待排序数组的第一个进行交换，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。反复的进行这样的过程直到待排序的数组全部有序。

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N^2)
空间复杂度：O(1)

在这里插入图片描述

// 自定义方法：交换两个变量的值
void swap(int *a,int *b) 
{int temp = *a;*a = *b;*b = temp;
}
/* 选择排序 */
void SelectSort(int arr[], int len)
{int i,j;for (i = 0 ; i < len - 1 ; i++) {int min = i;for (j = i + 1; j < len; j++) {    //  遍历未排序的元素if (arr[j] < arr[min]) {  //  找到目前最小值min = j;   // 记录最小值}}swap(&arr[min], &arr[i]);    //做交换/*if (index != i)  // 不用自定义函数时可以用选择下面方式进行交换{temp = arr[i];arr[i] = arr[index];arr[index] = temp;}*/}
}

3、插入排序

插入排序是一种简单的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

例如要将数组arr = [4,2,8,0,5,1]排序，可以将4看做是一个有序序列，将[2,8,0,5,1]看做一个无序序列。

无序序列中2比4小，于是将2插入到4的左边，此时有序序列变成了[2,4]，无序序列变成了[8,0,5,1]。无序序列中8比4大，于是将8插入到4的右边，有序序列变成了[2,4,8],无序序列变成了[0,5,1]。以此类推，最终数组按照从小到大排序。该算法的时间复杂度为O(n^2)。

插入排序算法的原理如下：

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

3.如果该元素（已排序）大于新元素，将该元素移到下一位置；

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5.将新元素插入到该位置后；

6.重复步骤2~5。

时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
      最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)
在这里插入图片描述

/* 插入排序 */
void InsertSort(int arr[], int len){int i,j,key;for (i = 1;i < len;i++){key = arr[i];j = i - 1;while((j >= 0) && (arr[j] > key)) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

4、希尔排序

希尔排序是一种改进的插入排序算法，它的基本思想是将待排序的数组按照一定的间隔进行分组，对每组使用插入排序算法进行排序，然后缩小间隔，再对分组进行排序，直到间隔为1为止。

逐渐减小间隔大小的方法有助于提高排序过程的效率，可以减少比较和交换的次数。这是希尔排序算法的一个关键特点。

时间复杂度平均：O(N^1.3)
空间复杂度：O(1)

在这里插入图片描述

//希尔排序
void ShellSort(int arr[], int len)
{int gap = len;while (gap > 1){//每次对gap折半操作gap = gap / 2;//单趟排序for (int i = 0; i < len - gap; ++i){int end = i;int tem = arr[end + gap];while (end >= 0){if (tem < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tem;}}
}

5、归并排序

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子 序列中只有一个数据时），就对子序列进行归并。

归并指的是把两个排好序的子序列合并成一个 有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

（1）递归实现归并排序

// 合并两个子数组函数
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组int* L = (int*)malloc(n1 * sizeof(int));int* R = (int*)malloc(n2 * sizeof(int));// 将数据复制到临时数组L[]和R[]for (int i = 0; i < n1; i++)L[i] = arr[left + i];for (int j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];// 合并临时数组回到arr[left..right]int i = 0; // 初始化第一个子数组的索引int j = 0; // 初始化第二个子数组的索引int k = left; // 初始化合并子数组的索引while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 复制L[]剩余的元素，如果有while (i < n1) {arr[k] = L[i];i++;k++;}// 复制R[]剩余的元素，如果有while (j < n2) {arr[k] = R[j];j++;k++;}free(L);free(R);
}// 归并排序函数
void merge_sort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;// 对每一半进行排序merge_sort(arr, left, mid);merge_sort(arr, mid + 1, right);// 合并排好序的两半merge(arr, left, mid, right);}
}

（2）非递归实现归并排序

// 非递归实现归并排序
void mergeSortIterative(int arr[], int size) {int* temp = (int*)malloc(size * sizeof(int));if (temp == NULL) {printf("Memory allocation failed\n");return;}for (int width = 1; width < size; width *= 2) {for (int i = 0; i < size; i += 2 * width) {int left = i;int mid = (i + width < size) ? i + width - 1 : size - 1;int right = (i + 2 * width - 1 < size) ? i + 2 * width - 1 : size - 1;merge(arr, temp, left, mid, right);}}free(temp);
}

6、快速排序

快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分 为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。

[ 比基准值小的数] 基准值 [比基准值大的数]

接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据 进行排序时同样也会使用快速排序

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

void QuickSort(int array[], int low, int high) {int i = low; int j = high;if(i >= j) {return;}int temp = array[low];while(i != j) {while(array[j] >= temp && i < j) {j--;}while(array[i] <= temp && i < j) {i++;}if(i < j) {swap(array[i], array[j]);}}//将基准temp放于自己的位置，（第i个位置）swap(array[low], array[i]);QuickSort(array, low, i - 1);QuickSort(array, i + 1, high);
}

7、堆排序

堆排序是一种树形选择排序算法，它的基本思想是将待排序的数组构建成一个大根堆（或小根堆），然后将堆顶元素与堆底元素交换位置，再将剩余元素重新构建成堆，重复执行交换和重构堆的操作，直到整个数组有序。

堆排序是一种基于堆数据结构的排序算法，它的时间复杂度为O(nlogn)。

堆的概念
集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1（左节点） 且 Ki<=K2i+2（右节点），则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。完全二叉树（除了最后一层以外上面的节点但是非空的，最后一层节点是从左到右依次排布的）

堆的性质
1.堆中某个节点的值总是不大于或不小于其父节点的值;
2.堆总是一棵完全二叉树。

完全二叉树
完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

在这里插入图片描述

完全二叉树的第 i 层至多有 2^i - 1 个结点。
完全二叉树的第 i 层至少有 2^(i - 1) 个结点。
完全二叉树的叶子结点只出现在最底层和次底层。
完全二叉树每一层的结点个数都达到了最大值

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

（1）大顶堆

在这里插入图片描述
在这里插入图片描述

（2）小顶堆

在这里插入图片描述

//向下调整算法（要满足它下面的都满足堆，才能用）
void AdjustDown(int* a, int n, int root)
{int parent = root;int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]) child+=1;//把他移到右孩子那里if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else break;}
}堆排序
void HeapSort(int* arr, int n)
{//建大堆//从最后一个根开始，就相当于它下面的都满足堆，就可以用向下调整算法for (int i = (n-1-1)/2; i >= 0; i--)//n-1-1是因为数组的最后一个元素下标是n-1{AdjustDown(arr, n, i);}//排序for (int i = n; i > 1; i--){swap(&arr[0],&arr[i - 1]);AdjustDown(arr, i-1, 0);}
}

http://www.ppmy.cn/ops/150146.html

相关文章

【maptalks】加载SVG和GIF

【maptalks】加载SVG和GIF

加载SVG和GIF 一、加载SVG方法一&#xff1a;直接载入SVG文件&#xff0c;类似载入图片方法二&#xff1a;载入SVG路径 二、加载GIFVUEmaptalks实现GIF可拖拽点VUEmaptalks实现GIF跟随线条动画 一、加载SVG 方法一&#xff1a;直接载入SVG文件&#xff0c;类似载入图片 缺点&…
阅读更多...
深度学习-算法优化与宇宙能量梯度分布

深度学习-算法优化与宇宙能量梯度分布

在当今迅速发展的科技世界中&#xff0c;算法优化和能量分布问题已成为研究的热点&#xff0c;尤其是在人工智能、机器学习和物理科学领域。算法优化通常涉及提高计算效率和降低资源消耗&#xff0c;而宇宙能量梯度分布则涉及宇宙中能量的分布和流动方式。两者看似是完全不同的…
阅读更多...
基于金融新闻微调大语言模型，进行股票回报预测

基于金融新闻微调大语言模型，进行股票回报预测

“Fine-Tuning Large Language Models for Stock Return Prediction Using Newsflow” 论文地址&#xff1a;https://arxiv.org/pdf/2407.18103 摘要 本文研究了利用金融新闻流对大型语言模型&#xff08;LLMs&#xff09;进行微调&#xff0c;以用于预测股票回报的效果&…
阅读更多...
社群团购项目运营策略的深度剖析：融合链动2+1模式、AI智能名片与S2B2C商城小程序的综合应用

社群团购项目运营策略的深度剖析：融合链动2+1模式、AI智能名片与S2B2C商城小程序的综合应用

摘要&#xff1a;随着互联网技术的飞速发展和消费者购物习惯的不断变化&#xff0c;社群团购作为一种新兴的商业模式&#xff0c;正逐渐成为连接供应商、商家与消费者的重要桥梁。然而&#xff0c;社群团购的成功并非仅限于线上运营&#xff0c;其关键在于项目整体运营的优劣&a…
阅读更多...
小结：路由器和交换机的指令对比

小结：路由器和交换机的指令对比

路由器和交换机的指令有一定的相似性&#xff0c;但也有明显的区别。以下是两者指令的对比和主要差异&#xff1a; 相似之处 基本操作 两者都支持类似的基本管理命令&#xff0c;比如&#xff1a; 进入系统视图&#xff1a;system-view查看当前配置&#xff1a;display current…
阅读更多...
39_Lua选择结构语句

39_Lua选择结构语句

Lua语言提供了多种选择结构语句，用于根据不同的条件执行不同的代码块。在条件为true时执行指定程序代码，在条件为false时执行其他指定代码。以下是典型的流程控制流程图。 控制结构的条件表达式结果可以是任何值，Lua认为false和nil为假，true和非nil为真。要注意的是，Lua中…
阅读更多...
WINFORM - DevExpress -＞ DevExpress总结[安装、案例]

WINFORM - DevExpress -＞ DevExpress总结[安装、案例]

安装devexpress软件 路径尽量不换&#xff0c;后面破解不容易出问题 vs工具箱添加控件例如: ①使用控制台进入DevExpress安装目录: cd C:\Program Files (x86)\DevExpress 20.1\Components\Tools ②添加DevExpress控件&#xff1a; ToolboxCreator.exe/ini:toolboxcreator…
阅读更多...
Hadoop3.x 万字解析，从入门到剖析源码

Hadoop3.x 万字解析，从入门到剖析源码

&#x1f496; 欢迎来到我的博客&#xff01; 非常高兴能在这里与您相遇。在这里&#xff0c;您不仅能获得有趣的技术分享&#xff0c;还能感受到轻松愉快的氛围。无论您是编程新手&#xff0c;还是资深开发者&#xff0c;都能在这里找到属于您的知识宝藏&#xff0c;学习和成长…
阅读更多...
最新文章

Copyright @ 2022~2023