鹿形鱼dè小窝 - 算法
type: channel
link: https://blog.xingyu.lu/tag/%E7%AE%97%E6%B3%95/
items: 数据结构之排序总结

数据结构之排序总结
type: item
date: 2022-12-08T15:29:00+00:00
description: 冒泡排序以升序为例，有 N 个数需要排序，从第一个数开始，遍历所有数，将其与它下一个数比较，如果比它下一个数大则交换位置，这样最大的数就跑到最后了。重复这个操作至多 n - 1 次，最后这 N 个数就被排好了。动画演示示例代码最好时间复杂度为O(n^2)的算法#include <iostream> using namespace std; int main() { const int maxN = 10; // 待排序的数组 int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33}; // 冒泡算法 for (int i = 0; i < maxN - 1; i++) { // 每次遍历 for (int j = 1; j < maxN - i; j++) { // 从第一个开始比较，当前面一个大于后面一个时交换位置 if (a[j - 1] > a[j]) { int temp = a[j - 1]; a[j - 1] = a[j]; a[j] = temp; } } } // 打印 for (int i = 0; i < maxN; i++) { cout << a[i] << ' '; } }最好时间复杂度为O(n)的改进算法看书和老师PPT上说冒泡算法最好复杂度为O(n)，可是按照上面的代码无论是刚开始就是升序还是任意情况，粗略的来说进行了两次循环，最好复杂度依旧是O(n^2)，后面网上搜索才有答案：冒泡排序最佳情况的时间复杂度，为什么是O(n) - melon.h - 博客园 (cnblogs.com)。当没有排好序时，每次遍历一定会交换位置，故当没有交换位置的时候表明已经排好了，可以挑出来不需要再进行排序了，改进后的代码：#include <iostream> using namespace std; int main() { const int maxN = 10; // 待排序的数组 int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33}; // 冒泡算法 bool isSwap; for (int i = 0; i < maxN - 1; i++) { // 是否交换位置 isSwap = false; // 每次遍历 for (int j = 1; j < maxN - i; j++) { // 从第一个开始比较，当前面一个大于后面一个时交换位置 if (a[j - 1] > a[j]) { int temp = a[j - 1]; a[j - 1] = a[j]; a[j] = temp; isSwap = true; } } // 当遍历到没有交换位置时，表明已经排序好了 if(!isSwap){ break; } } // 打印 for (int i = 0; i < maxN; i++) { cout << a[i] << ' '; } }输出：2 6 10 16 19 24 33 34 37 40复杂度及稳定性因为冒泡排序用了两层循环，嵌套遍历了两次，所以平均时间复杂度为O(n ^2)；当一个序列刚好是升序无需排序时，则只进行一次循环，故最好时间复杂度为O(n)；当一个序列是降序排序时，则只需要的是嵌套循环并且每次需要交换，故最坏时间复杂度为O(n ^2)；在排序过程中无需其他空间存放数据，故空间复杂度为O(1)；在排序时当两数相等时，不进行交换，故此排序算法稳定。排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(n)O(1)稳定直接选择排序以升序为例，有 N 个数需要排序，从第一个数开始，遍历所有数，查找未排序区域的最小值以及其下表，将这个最小数与当前这个数交换位置，以此类推到最后即可得到排序好的序列。动画演示示例代码#include <iostream> using namespace std; int main() { const int maxN = 10; // 待排序的数组 int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33}; // 直接选择排序 for (int i = 0; i < maxN - 1; i++) { // 每次遍历记录最小值 int minIndex = i; for (int j = i + 1; j < maxN ; j++) { // 从第 i + 1 个开始比较，当出现小的值时记录最小值下表的值更新 if (a[minIndex] > a[j]) { minIndex = j; } } // 更新位置 int temp = a[i]; a[i] = a[mi…