排序算法总结（含链表）

排序算法

1. 比较排序算法

这些排序算法基于元素之间的比较进行排序，最常见的几种有：

1.1. 冒泡排序（Bubble Sort）

  • 工作原理：相邻的元素两两比较，较大的元素冒泡到最后，重复这一过程，直到整个数组有序。
  • 时间复杂度：最优 O(n)，最差 O(n²)，平均 O(n²)。
  • 特点：简单但效率较低，适合小规模数据。

1.2. 选择排序（Selection Sort）

  • 工作原理：每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾，重复这一过程。
  • 时间复杂度：最优 O(n²)，最差 O(n²)，平均 O(n²)。
  • 特点：相比冒泡排序，减少了交换次数，但仍然效率不高。

1.3. 插入排序（Insertion Sort）

  • 工作原理：每次将一个未排序的元素插入到已排序的部分中，直到整个数组有序。
  • 时间复杂度：最优 O(n)，最差 O(n²)，平均 O(n²)。
  • 特点：在数据基本有序时表现优异，适合小规模数据。

1.4. 希尔排序（Shell Sort）

  • 工作原理：基于插入排序的改进，通过比较相隔一定间隔的元素（逐步缩小间隔）来进行多次插入排序。
  • 时间复杂度：平均 O(n log n) 到 O(n²)，最差 O(n²)。
  • 特点：改进了插入排序的效率，适合中等规模的数据。

1.5. 归并排序（Merge Sort）

  • 工作原理：采用分治法，将数组递归地分成两部分，分别排序后合并。
  • 时间复杂度：最优、最差和平均都是 O(n log n)。
  • 特点：稳定排序，适合大规模数据排序，但需要 O(n) 的额外空间。

1.6. 快速排序（Quick Sort）

  • 工作原理：选择一个基准元素，将数组分成两部分，一部分小于基准，一部分大于基准，递归地对两部分进行排序。
  • 时间复杂度：最优 O(n log n)，最差 O(n²)，平均 O(n log n)。
  • 特点：效率高，尤其在数据量大时，最常用的排序算法之一，但不稳定。

1.7. 堆排序（Heap Sort）

  • 工作原理：将数组看作完全二叉树，调整为最大（最小）堆，然后依次取出堆顶元素。
  • 时间复杂度：最优、最差和平均都是 O(n log n)。
  • 特点：不需要额外空间，适合需要较高空间效率的场景。

2. 非比较排序算法

这些排序算法并不依赖元素之间的比较来确定顺序，因此可以突破 O(n log n) 的时间复杂度。

2.1. 计数排序（Counting Sort）

  • 工作原理：适用于已知范围的整数，计算每个数出现的次数，然后按次数重构数组。
  • 时间复杂度：最优、最差和平均都是 O(n + k)，其中 k 是数值范围。
  • 特点：非常快，但受限于数据的取值范围，适合整数排序。

2.2. 基数排序（Radix Sort）

  • 工作原理：将数按位数进行排序（从低位到高位或反过来），多次排序使用稳定的排序算法（如计数排序或桶排序）。
  • 时间复杂度：最优、最差和平均都是 O(n * d)，其中 d 是数字的位数。
  • 特点：适合对整数或字符串等有多位数值的数据进行排序。

2.3. 桶排序（Bucket Sort）

  • 工作原理：将数组分成多个桶，每个桶内分别排序（通常使用插入排序或其他排序算法），然后合并。
  • 时间复杂度：最优 O(n)，最差 O(n²)，平均 O(n + k)。
  • 特点：适合数据比较均匀分布的情况，适用于浮点数排序。

3. 排序算法总结

排序算法时间复杂度（平均）时间复杂度（最优）时间复杂度（最差）空间复杂度稳定性
冒泡排序O(n²)O(n)O(n²)O(1)稳定
选择排序O(n²)O(n²)O(n²)O(1)不稳定
插入排序O(n²)O(n)O(n²)O(1)稳定
希尔排序O(n log n)O(n log² n)O(n²)O(1)不稳定
归并排序O(n log n)O(n log n)O(n log n)O(n)稳定
快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定
堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定
计数排序O(n + k)O(n + k)O(n + k)O(k)稳定
桶排序O(n + k)O(n)O(n²)O(n + k)稳定
基数排序O(n * d)O(n * d)O(n * d)O(n + k)稳定

4. 选择排序算法的依据

不同的排序算法在不同的场景下有各自的优缺点，选择时可以考虑以下因素：

  • 数据规模：数据量大时，时间复杂度低的算法（如快速排序、归并排序、堆排序）更为适合。
  • 数据特点：对于整数、小范围数据，计数排序和基数排序有很好的表现；数据接近有序时，插入排序的表现优异。
  • 稳定性需求：如果排序后需要保持相同值的元素的相对顺序，必须选择稳定的排序算法，如归并排序、插入排序等。

1. 冒泡排序（Bubble Sort）

void bubbleSort(std::vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; i++) {bool swapped = false;for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);swapped = true;}}// 如果没有交换，说明数组已排序if (!swapped) break;}
}

2. 选择排序（Selection Sort）

void selectionSort(std::vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}std::swap(arr[i], arr[minIndex]);}
}

3. 插入排序（Insertion Sort）

  • 通用
void insertionSort(std::vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// 将元素逐个比较并插入到合适位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}
  • 链表

链表中的插入排序实现步骤：

  1. 创建一个新的已排序链表。
  2. 逐个遍历原链表，将每个节点插入到新链表的正确位置。
  3. 保持新链表始终是有序的。

插入排序的时间复杂度为 O(n²)，适合小规模链表或基本有序的链表。

4. 希尔排序（Shell Sort）

void shellSort(std::vector<int>& arr) {int n = arr.size();for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}

5. 归并排序（Merge Sort）

  • 通用
void merge(std::vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;std::vector<int> L(n1), R(n2);for (int i = 0; i < n1; i++) L[i] = arr[left + i];for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}void mergeSort(std::vector<int>& arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}
  • 链表中的归并排序

链表中的归并排序实现步骤：

涉及到链表元素变动的一般都有哨兵节点；

  1. 使用快慢指针（slow 和 fast）找到链表的中间节点，将链表分成两半。
  2. 递归地对两部分进行排序。
  3. 合并两个已排序的链表。

注意：

查找中心点的while循环，得根据fast的初始值来进行设计，如果fast=head,则可以用fast→next&&fast→next→next

struct ListNode{int val;ListNode* next;ListNode(int x): val(x),next(nullptr){}
};
class Solution{public:ListNode* mergeSort(ListNode* head){if(!head || !head->next) return head;ListNode* slow = head;ListNode* fast = head->next;//找中心点while(fast&&fast->next){slow = slow->next;fast = fast->next->next;}// 分左右ListNode* mid = slow->next;//断开左右slow->next = nullptr;//递归左右，得到左右子链表ListNode* rightHead = mergeSort(mid);ListNode* leftHead = mergeSort(head);//合并两个排序的子链表return merge(leftHead,rightHead);			}private:ListNode* merge(ListNode* l,ListNode* r){ListNode dummy(0);ListNode* cur = &dummy;			while(l&&r){if(l->val<r-val){cur->next = l;l = l->next;}else{cur->next = r;r = r->next;}cur = cur->next;}cur->next = l1?l1:l2;return dummy.next;}
}

6. 快速排序（Quick Sort）

  • 通用
int partition(std::vector<int>& arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;std::swap(arr[i], arr[j]);}}std::swap(arr[i + 1], arr[high]);return i + 1;
}void quickSort(std::vector<int>& arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}
  • 链表

链表中的快速排序实现步骤：

  1. 选择一个基准元素（通常选择链表的头节点）。
  2. 将链表分为三个部分：小于基准的元素，等于基准的元素，大于基准的元素。
  3. 递归地对“小于基准”的部分和“大于基准”的部分进行排序。
  4. 最后将三部分合并。

注意：

递归的开头一定是判断，如果递归的是快慢那么一定是!head||!head→next

class Solution {
public:ListNode* quickSort(ListNode* head) {if (!head || !head->next) return head;// Partition the list into three partsListNode* pivot = head;ListNode* lessHead = new ListNode(0), *greaterHead = new ListNode(0);ListNode* less = lessHead, *greater = greaterHead, *equal = pivot;ListNode* curr = head->next;while (curr) {if (curr->val < pivot->val) {less->next = curr;less = less->next;} else if (curr->val > pivot->val) {greater->next = curr;greater = greater->next;} else {equal->next = curr;equal = equal->next;}curr = curr->next;}//断开链表less->next = nullptr;greater->next = nullptr;equal->next = nullptr;// Recursively sort the less and greater partitionsListNode* sortedLess = quickSort(lessHead->next);ListNode* sortedGreater = quickSort(greaterHead->next);// Combine all parts togetherreturn combine(sortedLess, pivot, sortedGreater);}private:ListNode* combine(ListNode* less, ListNode* pivot, ListNode* greater) {ListNode dummy(0), *tail = &dummy;if (less) {tail->next = less;//将tail排到尾巴while (tail->next) tail = tail->next;}tail->next = pivot;//将tail放到尾巴while (tail->next) tail = tail->next;tail->next = greater;return dummy.next;}
};

7. 堆排序（Heap Sort）

void heapify(std::vector<int>& arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest])largest = left;if (right < n && arr[right] > arr[largest])largest = right;if (largest != i) {std::swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(std::vector<int>& arr) {int n = arr.size();// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 依次从堆中取出元素for (int i = n - 1; i > 0; i--) {std::swap(arr[0], arr[i]);heapify(arr, i, 0);}
}

8. 计数排序（Counting Sort）

void countingSort(std::vector<int>& arr) {if (arr.empty()) return;int maxVal = *max_element(arr.begin(), arr.end());int minVal = *min_element(arr.begin(), arr.end());int range = maxVal - minVal + 1;std::vector<int> count(range, 0), output(arr.size());// 计数for (int i = 0; i < arr.size(); i++)count[arr[i] - minVal]++;// 累积计数for (int i = 1; i < count.size(); i++)count[i] += count[i - 1];// 构建输出数组for (int i = arr.size() - 1; i >= 0; i--) {output[count[arr[i] - minVal] - 1] = arr[i];count[arr[i] - minVal]--;}// 将排序后的结果复制回原数组for (int i = 0; i < arr.size(); i++)arr[i] = output[i];
}

9. 基数排序（Radix Sort）

void countingSortForRadix(std::vector<int>& arr, int exp) {int n = arr.size();std::vector<int> output(n), count(10, 0);// 计数for (int i = 0; i < n; i++)count[(arr[i] / exp) % 10]++;// 累积计数for (int i = 1; i < 10; i++)count[i] += count[i - 1];// 构建输出数组for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}// 复制回原数组for (int i = 0; i < n; i++)arr[i] = output[i];
}void radixSort(std::vector<int>& arr) {int maxVal = *max_element(arr.begin(), arr.end());// 基数排序for (int exp = 1; maxVal / exp > 0; exp *= 10)countingSortForRadix(arr, exp);
}

10. 桶排序（Bucket Sort）

void bucketSort(std::vector<float>& arr) {int n = arr.size();std::vector<std::vector<float>> buckets(n);// 将元素分配到桶for (int i = 0; i < n; i++) {int bucketIndex = n * arr[i];buckets[bucketIndex].push_back(arr[i]);}// 对每个桶内的元素进行排序for (int i = 0; i < n; i++) {std::sort(buckets[i].begin(), buckets[i].end());}// 合并所有桶中的元素int index = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < buckets[i].size(); j++) {arr[index++] = buckets[i][j];}}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1556962.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

VGG16模型实现MNIST图像分类

VGG16模型实现MNIST图像分类

MNIST图像数据集 MNIST&#xff08;Modified National Institute of Standards and Technology&#xff09;是一个经典的机器学习数据集&#xff0c;常用于训练和测试图像处理和机器学习算法&#xff0c;特别是在数字识别领域。该数据集包含了大约 7 万张手写数字图片&#xf…
阅读更多...
喜讯 | 攸信技术入选第六批专精特新“小巨人”企业

喜讯 | 攸信技术入选第六批专精特新“小巨人”企业

日前&#xff0c;根据工信部评审结果&#xff0c;厦门市工业和信息化局公示了第六批专精特新“小巨人”企业和第三批专精特新“小巨人”复核通过企业名单&#xff0c;其中&#xff0c;厦门攸信信息技术有限公司进入第六批专精特新“小巨人”企业培育。 “专精特新”企业是指具有…
阅读更多...
图像分割恢复方法

图像分割恢复方法

传统的图像分割方法主要依赖于图像的灰度值、纹理、颜色等特征&#xff0c;通过不同的算法将图像分割成多个区域。这些方法通常可以分为以下几类&#xff1a; 1.基于阈值的方法 2.基于边缘的方法 3.基于区域的方法 4.基于聚类的方法 下面详细介绍这些方法及其示例代码。 1. 基…
阅读更多...
代码随想录--栈与队列--用栈实现队列

代码随想录--栈与队列--用栈实现队列

队列是先进先出&#xff0c;栈是先进后出。 如图所示&#xff1a; 题目 使用栈实现队列的下列操作&#xff1a; push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。 示例: MyQueue qu…
阅读更多...
draw.io 设置默认字体及添加常用字体

draw.io 设置默认字体及添加常用字体

需求描述 draw.io 是一个比较好的开源免费画图软件。但是其添加容器或者文本框时默认的字体是 Helvetica&#xff0c;一般的期刊、会议论文或者学位论文要求的英文字体是 Times New Roman&#xff0c;中文字体是 宋体&#xff0c;所以一般需要在文本字体选项里的下拉列表选择 …
阅读更多...
分层解耦-05.IOCDI-DI详解

分层解耦-05.IOCDI-DI详解

一.依赖注入的注解 在我们的项目中&#xff0c;EmpService的实现类有两个&#xff0c;分别是EmpServiceA和EmpServiceB。这两个实现类都加上Service注解。我们运行程序&#xff0c;就会报错。 这是因为我们依赖注入的注解Autowired默认是按照类型来寻找bean对象的进行依赖注入…
阅读更多...
2-115 基于matlab的瞬态提取变换（TET）时频分析

2-115 基于matlab的瞬态提取变换（TET）时频分析

基于matlab的瞬态提取变换&#xff08;TET&#xff09;时频分析&#xff0c;瞬态提取变换是一种比较新的TFA方法。该方法的分辨率较高&#xff0c;能够较好地提取出故障的瞬态特征&#xff0c;用于故障诊断领域。通过对原始振动信号设置不同信噪比噪声&#xff0c;对该方法的抗…
阅读更多...
关于一个模仿qq通信程序

关于一个模仿qq通信程序

7月份的时候还在学校那个时候想要学习嵌入式Linux&#xff0c;但是还没有买开发板来玩&#xff0c;再学linux系统编程&#xff0c;网络编程&#xff0c;Linux系统的文件IO&#xff0c;于是学完之后想做一个模仿qq的通信程序于是就有了这个“ailun.exe”&#xff0c;因为暑假去打…
阅读更多...
【数据结构与算法】线性表

【数据结构与算法】线性表

文章目录 一.什么是线性表&#xff1f;二.线性表如何存储&#xff1f;三.线性表的类型 我们知道从应用中抽象出共性的逻辑结构和基本操作就是抽象数据类型&#xff0c;然后实现其存储结构和基本操作。下面我们依然按这个思路来认识线性表 一.什么是线性表&#xff1f; 定义 线性…
阅读更多...
TryHackMe 第7天 | Web Fundamentals (二)

TryHackMe 第7天 | Web Fundamentals (二)

继续介绍一些 Web hacking 相关的漏洞。 IDOR IDOR (Insecure direct object reference)&#xff0c;不安全的对象直接引用&#xff0c;这是一种访问控制漏洞。 当 Web 服务器接收到用户提供的输入来检索对象时 (包括文件、数据、文档)&#xff0c;如果对用户输入数据过于信…
阅读更多...
【springboot】使用代码生成器快速开发

【springboot】使用代码生成器快速开发

接上一项目&#xff0c;使用mybatis-plus-generator实现简易代码文件生成 在fast-demo-web模块中的pom.xml中添加mybatis-plus-generator、freemarker和Lombok依赖 <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-generator&…
阅读更多...
Python | 由高程计算坡度和坡向

Python | 由高程计算坡度和坡向

写在前面 之前参加一个比赛&#xff0c;提供了中国的高程数据&#xff0c;可以基于该数据进一步计算坡度和坡向进行相关分析。 对于坡度和坡向&#xff0c;这里分享一个找到的库&#xff0c;可以方便快捷的计算。这个库为&#xff1a;RichDEM&#xff0c;官网地址如下 https…
阅读更多...
SAP学习笔记 - 豆知识11 - 如何查询某个字段/DataElement/Domain在哪个表里使用？

SAP学习笔记 - 豆知识11 - 如何查询某个字段/DataElement/Domain在哪个表里使用？

大家知道SAP的表有10几万个&#xff08;也有说30多万个的&#xff0c;总之很多就是了&#xff09;&#xff0c;而且不断增多&#xff0c;那么当想知道一个字段在哪个表里使用的时候该怎么办呢&#xff1f; 思路就是SAP的表其实也是存在表里的&#xff1a;&#xff09;&#xf…
阅读更多...
【Git】TortoiseGitPlink提示输入密码解决方法

【Git】TortoiseGitPlink提示输入密码解决方法

问题 克隆仓库&#xff0c;TortoiseGitPlink提示输入密码 解法 1、打开TortoiseGit 下的puttygen工具 位置&#xff1a;C:\Program Files\TortoiseGit\bin\ 2、点击【Load】按钮&#xff0c;载入 C:\Users\Administrator\.ssh\ 文件夹下的id_rsa文件。 3、点击save private …
阅读更多...
qt_c++_xml存这种复杂类型

qt_c++_xml存这种复杂类型

demo&#xff0c;迅雷链接。或者我主页上传的资源 链接&#xff1a;https://pan.xunlei.com/s/VO8bIvYFfhmcrwF-7wmcPW1SA1?pwdnrp4# 复制这段内容后打开手机迅雷App&#xff0c;查看更方便 #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow>#include…
阅读更多...
请散户股民看过来，密切关注两件大事

请散户股民看过来，密切关注两件大事

明天股市要开市&#xff0c;不仅散户股民期盼节后股市大涨&#xff0c;上面也同样想在节后来上一个“开门红”。 为此&#xff0c;上面没休假&#xff0c;关起门来办了两件大事&#xff0c;这两天发布消息已提前预热了。 两件大事如下&#xff1a; 一是&#xff0c;上交所10…
阅读更多...
什么是 JavaScript 的数组空槽

什么是 JavaScript 的数组空槽

JavaScript 中的数组空槽一直是一个非常有趣且颇具争议的话题。我们可能对它的实际意义、历史以及现今的新版本中对它的处理方式有所疑问。数组空槽的存在最早可以追溯到 JavaScript 的诞生之初&#xff0c;当时的设计决定让它成为了现代 JavaScript 开发中的一种特别的现象。 …
阅读更多...
大数据新视界 --大数据大厂之数据血缘追踪与治理：确保数据可追溯性

大数据新视界 --大数据大厂之数据血缘追踪与治理：确保数据可追溯性

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…
阅读更多...
计算机毕业设计hadoop+spark天气预测 天气可视化 天气大数据 空气质量检测 空气质量分析 气象大数据 气象分析 大数据毕业设计 大数据毕设

计算机毕业设计hadoop+spark天气预测 天气可视化 天气大数据 空气质量检测 空气质量分析 气象大数据 气象分析 大数据毕业设计 大数据毕设

Hadoop天气预测系统开题报告 一、研究背景与意义 在信息化和大数据时代&#xff0c;天气数据已成为社会生活和经济发展中不可或缺的重要资源。天气预测系统作为现代气象学的重要组成部分&#xff0c;对于农业生产、交通管理、环境保护以及防灾减灾等方面都具有重要意义。然而…
阅读更多...
集智书童 | 用于时态动作检测的预测反馈 DETR !

集智书童 | 用于时态动作检测的预测反馈 DETR !

本文来源公众号“集智书童”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;用于时态动作检测的预测反馈 DETR ! 视频中的时间动作检测&#xff08;TAD&#xff09;是现实世界中的一个基本且具有挑战性的任务。得益于 Transformer …
阅读更多...
最新文章

Copyright @ 2022~2023