【算法】经典的八大排序算法

点击链接 可视化排序 动态演示各个排序算法来加深理解,大致如下

一,冒泡排序(Bubble Sort)

原理

  • 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过多次比较和交换相邻元素的方式,将最大(或最小)的元素逐步冒泡到数组的一端。每一轮冒泡将会将未排序部分中最大(或最小)的元素“浮”到正确的位置。

算法步骤

  1. 从数组的第一个元素开始,依次比较相邻的两个元素。
  2. 如果前一个元素比后一个元素大(或小,取决于排序顺序),则交换这两个元素。
  3. 继续向后遍历,对每一对相邻元素重复步骤 2。
  4. 重复步骤 1 到 3,直到没有元素需要交换,整个数组就是有序的。

算法实现

#include <iostream>
#include <vector>// 冒泡排序
void bubbleSort(std::vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {// 在每一轮中,比较相邻元素并交换for (int j = 0; j < n - i - 1; ++j) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);}}}
}

性能分析

  • 时间复杂度:
    • 冒泡排序的时间复杂度在最坏和平均情况下都为 O(n^2),其中 n 是待排序元素的数量。每次遍历需要进行 n-1 次比较,而需要执行 n-1 次遍历。
    • 最好情况下,如果列表本身已经有序,冒泡排序仍然需要进行 n-1 次遍历,但由于没有发生交换,每次遍历只需要进行 n-1、n-2、...、2、1 次比较,时间复杂度为 O(n)。
  • 空间复杂度:
    • 冒泡排序的空间复杂度为 O(1),只需要常数级别的额外空间。
  • 稳定性:
    • 冒泡排序是稳定的排序算法,因为它在相邻元素比较时仅在必要时才进行交换。

二,选择排序(Selection Sort)

原理

  • 选择排序(Selection Sort)是一种简单的排序算法,它将待排序数组分为已排序和未排序两部分,然后从未排序部分选择最小(或最大)的元素,与已排序部分的最后一个元素交换位置。每次交换都会将一个元素归位,直到整个数组有序。

算法步骤

  1. 初始时,将整个序列分为已排序和未排序两部分,已排序为空,未排序包含所有元素。
  2. 在未排序部分中,找到最小(或最大)的元素。
  3. 将找到的最小元素与未排序部分的第一个元素交换位置,将其放到已排序部分的末尾。
  4. 重复执行步骤 2 和 3,直到未排序部分为空,整个序列变得有序。

算法实现

#include <iostream>
#include <vector>// 选择排序
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]);}
}

性能分析

  • 时间复杂度:
    • 选择排序的时间复杂度在最好、最坏和平均情况下都是 O(n^2),其中 n 是待排序元素的数量。
  • 空间复杂度:
    • 选择排序的空间复杂度为 O(1),只需要常数级别的额外空间。
  • 稳定性:
    • 选择排序是不稳定的排序算法,因为在选择最小(或最大)元素的过程中,相同值的元素可能会交换位置。

三,插入排序(Insertion Sort)

原理

  • 插入排序(Insertion Sort)是一种简单的排序算法,它将待排序数组分为已排序和未排序两部分,然后逐个将未排序部分的元素插入到已排序部分的正确位置,使得已排序部分始终保持有序。

算法步骤

  1. 初始时,将第一个元素视为已排序部分,其余元素视为未排序部分。
  2. 从未排序部分中取出一个元素,将其插入到已排序部分的适当位置,使得插入后的已排序部分仍然保持有序。
  3. 重复步骤 2,直到未排序部分为空,整个序列变得有序。

算法实现

#include <iostream>
#include <vector>// 插入排序
void insertionSort(std::vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int current = arr[i]; // 当前要插入的元素int j = i - 1; // 已排序部分的末尾索引// 将元素插入到正确位置while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j];j--;}arr[j + 1] = current;}
}

性能分析

  • 时间复杂度:
    • 插入排序的时间复杂度在最好情况下是 O(n),最坏和平均情况下是 O(n^2),其中 n 是待排序元素的数量。
  • 空间复杂度:
    • 插入排序的空间复杂度为 O(1),只需要常数级别的额外空间。
  • 稳定性:
    • 插入排序是稳定的排序算法,因为它在插入元素时相同值的元素不会改变相对顺序。

四,希尔排序(Shell Sort)

原理

  • 希尔排序(Shell Sort)是一种改进的插入排序算法,它通过将数组分成多个子序列来排序,然后逐步缩小子序列的间隔,最终将整个数组排序。希尔排序的核心思想是使数组中任意间隔 h 的元素都是有序的,当 h 逐步减小到 1 时,整个数组变为有序。

算法步骤

  1. 选择一个增量序列(通常为递减的整数序列),例如 [n/2, n/4, n/8, ...],其中 n 是数组的长度。
  2. 对每个增量进行迭代,将数组分成多个子数组,每个子数组中的元素间隔为增量。
  3. 对每个子数组进行插入排序,将子数组中的元素插入到已排序部分的适当位置。
  4. 重复步骤 2 和 3,不断减小增量,直到增量为 1,此时整个数组被视为一个子数组,进行最后一次插入排序。

算法实现

#include <iostream>void shellSort(int arr[], int n) {for (int gap = n / 2; gap > 0; gap /= 2) {// 使用插入排序对子数组进行排序for (int i = gap; i < n; ++i) {int temp = arr[i];int j = i;// 移动元素,寻找插入位置while (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap];j -= gap;}arr[j] = temp; // 将元素插入到合适的位置}}
}

性能分析

  • 时间复杂度:
    • 希尔排序的时间复杂度依赖于所选的增量序列。最好的已知增量序列的时间复杂度是 O(n^1.3),平均情况下的时间复杂度较难分析,但它通常优于 O(n^2) (介于 O(n log n) 和 O(n^2) 之间)的插入排序。具体取决于增量序列的选择。
  • 空间复杂度:
    • 希尔排序的空间复杂度为 O(1),只需要常数级别的额外空间。
  • 稳定性:
    • 希尔排序不是稳定的排序算法,因为在交换元素的过程中可能会改变相同值元素的相对顺序。

五,归并排序(Merge Sort)

原理

  • 归并排序(Merge Sort)是一种分治策略的排序算法,它将待排序数组不断划分为两个子数组,然后将这些子数组逐步合并成一个有序数组。归并排序的核心思想是将两个有序的子数组合并成一个有序的数组,这样逐步合并,最终得到整个数组有序。

算法步骤

  1. 分割:将待排序数组递归地分割成较小的子数组,直到每个子数组只包含一个元素。
  2. 合并:将两个有序的子数组合并成一个有序数组。合并过程中,分别从两个子数组中取出较小的元素,放入结果数组中。

算法实现

#include <iostream>
#include <vector>// 合并两个有序子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {int leftCount = mid - left + 1;    // 左边子数组大小int rightCount = right - mid;      // 右边子数组大小// 创建临时数组存放两个子数组的元素std::vector<int> leftArr(leftCount), rightArr(rightCount);for (int i = 0; i < leftCount; ++i)leftArr[i] = arr[left + i];for (int i = 0; i < rightCount; ++i)rightArr[i] = arr[mid + 1 + i];// 合并两个子数组int i = 0, j = 0, k = left;while (i < leftCount && j < rightCount) {if (leftArr[i] <= rightArr[j]) {arr[k++] = leftArr[i++];} else {arr[k++] = rightArr[j++];}}// 将剩余的元素拷贝到结果数组中while (i < leftCount) {arr[k++] = leftArr[i++];}while (j < rightCount) {arr[k++] = rightArr[j++];}
}// 归并排序
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);}
}

性能分析

  • 时间复杂度:
    • 归并排序的时间复杂度是稳定的,无论数据的分布如何,都是 O(n log n),其中 n 是待排序元素的数量。
  • 空间复杂度:
    • 归并排序需要额外的空间来存储临时数组,因此其空间复杂度是 O(n)。
  • 稳定性:
    • 归并排序是稳定的排序算法,因为在合并两个子数组时,相同值的元素不会改变相对顺序。

六,快速排序(Quick Sort)

原理

  • 快速排序(Quick Sort)是一种基于分治思想的排序算法,它通过选择一个基准元素,将数组划分为小于基准和大于基准的两部分,然后递归地对这两部分进行排序。在每一次划分后,基准元素会被放置在最终的正确位置上。

算法步骤

  1. 选择基准元素:从数组中选择一个基准元素,通常选择第一个或最后一个元素。
  2. 分区:将数组划分为小于基准和大于基准的两部分,使得基准元素位于正确的位置上。
  3. 递归排序:对小于基准和大于基准的两部分分别递归地应用快速排序算法。
  4. 合并:不需要合并步骤,因为在分区过程中已经将数组划分为有序的部分。

算法实现

#include <iostream>
#include <vector>// 分区函数,返回基准元素的正确位置
int partition(std::vector<int>& arr, int low, int high) {int pivot = arr[low]; // 选择第一个元素作为基准while (low < high){while (low<high && arr[high]>=pivot)--high;arr[low] = arr[high];   // 将小于基准的元素移到左边while (low<high && arr[low]<=pivot)++low;arr[high] = arr[low];   // 将大于基准的元素移到右边}// 将基准元素放到正确的位置上arr[low] = pivot;return low; // 返回存放基准的最终位置
}// 快速排序
void quickSort(std::vector<int>& arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high); // 基准元素的正确位置// 对基准左边和右边的部分分别递归进行排序quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}
}

性能分析

  • 时间复杂度:
    • 平均情况下,快速排序的时间复杂度是 O(n log n),其中 n 是待排序元素的数量。
    • 在最坏情况下(数组已经有序或接近有序),快速排序的时间复杂度可能退化到 O(n^2)。
  • 空间复杂度:
    • 快速排序的空间复杂度主要取决于递归调用的栈空间,通常为 O(log n)。
    • 在最坏情况下,递归栈的深度可能达到 n,空间复杂度为 O(n)。
  • 稳定性:
    • 快速排序是不稳定的排序算法,因为在分区过程中可能改变相同元素的相对顺序。

七,堆排序(Heap Sort)

原理

  • 堆排序(Heap Sort)是一种基于二叉堆的排序算法。它将待排序数组构建成一个二叉堆,然后不断从堆顶取出最大(或最小)元素,将其放置到已排序部分的末尾,直到整个数组有序。

算法步骤

  1. 构建最大堆:将待排序数组看作完全二叉树,从最后一个非叶子节点开始,逐步向上调整,使得每个节点都大于其子节点。
  2. 不断从堆顶取出最大元素:每次将堆顶元素与堆末尾元素交换,然后将堆的大小减一,再进行堆化操作,将最大元素移至正确位置。
  3. 重复步骤 2,直到堆中只剩一个元素,此时整个数组有序。

算法实现

#include <iostream>
#include <vector>// 交换元素
void swap(int& a, int& b) {a = a + b;b = a - b;a = a - b;
}// 对以 root 为根的子树进行堆化
void heapify(std::vector<int>& arr, int n, int root) {int largest = root; // 初始化最大元素为根节点while (largest < n) {int left = 2 * root + 1; // 左子节点索引int right = 2 * root + 2; // 右子节点索引// 找到左右子节点中较大的元素索引if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大元素不是根节点,则交换元素if (largest != root) {swap(arr[root], arr[largest]);root = largest; // 继续向下调整} else {break; // 堆结构已经满足,退出循环}}
}// 堆排序
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) {swap(arr[0], arr[i]); // 将堆顶元素移至已排序部分的末尾heapify(arr, i, 0); // 对剩余的部分进行堆化}
}

性能分析

  • 时间复杂度:
    • 堆排序的时间复杂度在最好、最坏和平均情况下都是 O(n log n),其中 n 是待排序元素的数量。
  • 空间复杂度:
    • 堆排序的空间复杂度为 O(1),只需要常数级别的额外空间。
  • 稳定性:
    • 堆排序通常是不稳定的,因为堆化操作可能改变相同元素的相对顺序。然而,通过一些额外的操作可以实现稳定性。

八,基数排序(Counting Sort)

原理

  • 基数排序(Radix Sort)是一种非比较的整数排序算法,它根据数字的每个位上的值来对元素进行排序。基数排序可以看作是桶排序的扩展,它先按照最低位进行排序,然后逐步移到更高位,直到所有位都考虑完毕。

算法步骤

  1. 找到最大数的位数:首先,找到待排序数组中最大数的位数,这将决定排序的轮数。
  2. 按位排序:从低位到高位,依次对每一位进行计数排序(或桶排序),将元素分配到不同的桶中。
  3. 合并桶:将每一轮排序后的桶中的元素按顺序合并成一个新的数组。
  4. 重复步骤 2 和 3,直到所有位都考虑完毕,得到有序数组。

算法实现

#include <iostream>
#include <vector>
#include <queue>// 找到数组中的最大数
int findMax(std::vector<int>& arr) {int max = arr[0];for (int num : arr) {if (num > max) {max = num;}}return max;
}// 基数排序
void radixSort(std::vector<int>& arr) {int n = arr.size();int max = findMax(arr);int exp = 1; // 用于获取每个位数的值while (max / exp > 0) {// 创建桶队列,每个桶用于存放某个位数上的元素std::vector<std::queue<int>> buckets(10);   // 使用10个桶,每个桶代表一个数字(0到9)// 将元素分配到桶中for (int i = 0; i < n; ++i) {int bucketIndex = (arr[i] / exp) % 10; // 计算当前位数的值,作为桶的索引buckets[bucketIndex].push(arr[i]); // 将元素放入对应的桶中}// 从桶中取回元素到原数组int index = 0;for (int i = 0; i < 10; ++i) {while (!buckets[i].empty()) {arr[index++] = buckets[i].front(); // 取出队列头部元素,放入原数组buckets[i].pop(); // 弹出队列头部元素}}exp *= 10; // 移到下一个位数}
}

性能分析

  • 时间复杂度:
    • 基数排序的时间复杂度取决于位数和基数的大小。对于位数为 k,基数为 r 的情况,时间复杂度为 O(k * (n + r))。
  • 空间复杂度:
    • 基数排序的空间复杂度为 O(n + r),其中 n 是待排序元素的数量,r 是基数的大小。
  • 稳定性:
    • 基数排序是稳定的排序算法,因为在同一位数上的排序时,相同值元素的相对顺序不会改变。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于神经网络的3D地质模型

地球科学家需要对地质环境进行最佳估计才能进行模拟或评估。 除了地质背景之外&#xff0c;建立地质模型还需要一整套数学方法&#xff0c;如贝叶斯网络、协同克里金法、支持向量机、神经网络、随机模型&#xff0c;以在钻井日志或地球物理信息确实稀缺或不确定时定义哪些可能是…

视频汇聚/视频监控管理平台EasyCVR接入海康SDK协议后无法播放该如何解决?

开源EasyDarwin视频监控/安防监控/视频汇聚EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;在视频监控播放上&#xff0c;视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多路视频流&#…

[Linux]命令行参数和进程优先级

[Linux]命令行参数和进程优先级 文章目录 [Linux]命令行参数和进程优先级命令行参数命令行参数的概念命令函参数的接收编写代码验证 进程优先级进程优先级的概念PRI and NI使用top指令修改nice值 命令行参数 命令行参数的概念 命令行参数是指用于运行程序时在命令行输入的参数…

Python之动态规划

序言 最近在学习python语言&#xff0c;语言有通用性&#xff0c;此文记录复习动态规划并练习python语言。 动态规划&#xff08;Dynamic Programming&#xff09; 动态规划是运筹学的一个分支&#xff0c;是求解决策过程最优化的过程。20世纪50年代初&#xff0c;美国数学家…

ospf不规则区域划分和数据库表

华子目录 ospf不规则区域1.远离骨干的非骨干区域2.不连续骨干 不规则区域解决方案1.tunnel-点到点GRE2.ospf虚链路3.多进程双向重发布&#xff08;推荐&#xff09; ospf的数据库表 ospf不规则区域 1.远离骨干的非骨干区域 图示 2.不连续骨干 图示 不规则区域解决方案 …

成都瀚网科技有限公司:抖店精选联盟企业是什么?

我很高兴为您提供有关如何加入抖店特色联盟企业以及加入的好处的信息。在这篇文章中&#xff0c;我将为大家详细介绍如何申请加入抖店精选的关联公司&#xff0c;并讲解加入的好处。希望能够帮助您更好地了解和使用抖店精选联盟企业平台。 1、如何加入抖店精选联盟企业&#xf…

Docker基础入门:容器数据卷与Dockerfile构建镜像(发布)

Docker基础入门&#xff1a;容器数据卷与Dockerfile构建镜像&#xff08;发布&#xff09; 一、docker容器数据卷1.1、使用docker容器数据卷1.2、具名挂载、匿名挂载1.3、如何确定是具名挂载还是匿名挂载 二、使用dockerfile2.1 初识Dockerfile2.2 Dockerfile构建过程2.3 Docke…

Ansible学习笔记2

Ansible是Python开发的自动化运维工具&#xff0c;集合了众多运维工具&#xff08;Puppet、cfengine、chef、func、fabric&#xff09;的优点&#xff0c;实现了批量系统配置&#xff0c;批量程序部署、批量运行命令等功能。 特点&#xff1a; 1&#xff09;部署简单&#xff…

Kafka3.0.0版本——Leader故障处理细节原理

目录 一、服务器信息二、服务器基本信息及相关概念2.1、服务器基本信息2.2、LEO的概念2.3、HW的概念 三、Leader故障处理细节 一、服务器信息 三台服务器 原始服务器名称原始服务器ip节点centos7虚拟机1192.168.136.27broker0centos7虚拟机2192.168.136.28broker1centos7虚拟机…

Spring——Spring Boot基础

文章目录 第一个helloword项目新建 Spring Boot 项目Spring Boot 项目结构分析SpringBootApplication 注解分析新建一个 Controller大功告成,运行项目 简而言之&#xff0c;从本质上来说&#xff0c;Spring Boot 就是 Spring&#xff0c;它做了那些没有它你自己也会去做的 Spri…

【Unity】终极移动指南-注解【理解移动到抓钩,再到贪吃蛇的实现】

文章目录 【Unity】终极移动指南-注解&#xff08;从移动、抓钩到贪吃蛇&#xff09;观前提醒链接地址&#xff1a; 内容一、 transform移动操作【1】transform.position变换位置【2】transform.Translate平移【3】transform.position 类似平移的操作【4】定向矢量【5】停在指定…

IP 地址追踪工具

IP 地址跟踪工具是一种网络实用程序&#xff0c;允许您扫描、跟踪和获取详细信息&#xff0c;例如 IP 地址的 MAC 和接口 ID。IP 跟踪解决方案通过使用不同的网络扫描协议来检查网络地址空间来收集这些详细信息。一些高级 IP 地址跟踪器软件&#xff08;如 OpUtils&#xff09;…

RT-Thread 时钟管理

时钟节拍 任何操作系统都需要提供一个时钟节拍&#xff0c;以供系统处理所有和时间有关的事件&#xff0c;如线程的延时、时间片的轮转调度以及定时器超时等。 RTT中&#xff0c;时钟节拍的长度可以根据RT_TICK_PER_SECOND的定义来调整。rtconfig.h配置文件中定义&#xff1a…

自然语言处理(一):词嵌入

词嵌入 词嵌入&#xff08;Word Embedding&#xff09;是自然语言处理&#xff08;NLP&#xff09;中的一种技术&#xff0c;用于将文本中的单词映射到一个低维向量空间中。它是将文本中的单词表示为实数值向量的一种方式。 在传统的文本处理中&#xff0c;通常使用独热编码&…

Python Opencv实践 - Canny边缘检测

import cv2 as cv import numpy as np import matplotlib.pyplot as pltimg cv.imread("../SampleImages/pomeranian.png", cv.IMREAD_GRAYSCALE) print(img.shape)#图像Canny边缘检测 #cv.Canny(image, threshold1, threshold2[, edges[, apertureSize[, L2gradien…

GitHub 标星 15w,如何用 Python 实现所有算法?

学会了 Python 基础知识&#xff0c;想进阶一下&#xff0c;那就来点算法吧&#xff01;毕竟编程语言只是工具&#xff0c;结构算法才是灵魂。 新手如何入门 Python 算法&#xff1f; 几位印度小哥在 GitHub 上建了一个各种 Python 算法的新手入门大全。从原理到代码&#xf…

助力网络管理的利器:企业办公网络中的VLAN划分策略

企业办公网络的性能和安全性对员工的高效工作和信息安全具有重要意义。在实现这一目标时&#xff0c;VLAN&#xff08;Virtual Local Area Network&#xff09;划分在网络设计中发挥着至关重要的作用。通过将办公网络划分为多个虚拟局域网&#xff0c;VLAN划分可以实现网络资源…

Web服务器-Tomcat详细原理与实现

Tomcat 安装与使用 &#xff1a;MAC 安装配置使用Tomcat - 掘金 安装后本计算机就相当于一台服务器了&#xff01;&#xff01;&#xff01; 方式一&#xff1a;使用本地安装的Tomcat 1、将项目文件移动到Tomcat的webapps目录下。 2、启动Tomcat 3、在浏览器输入想要加载的…

ELK日志分析系统概述及部署

ELK 平台是一套完整的日志集中处理解决方案&#xff0c;将 ElasticSearch、Logstash 和 Kibana 三个开源工具配合使用&#xff0c;完成更强大的用户对日志的查询、排序、统计需求。 一、ELK概述 1、组件说明 ①ElasticSearch ElasticSearch是基于Lucene&#xff08;一个全文…

2023年中,量子计算产业现状——

2023年上半年&#xff0c;量子计算&#xff08;QC&#xff09;领域取得了一系列重要进展和突破&#xff0c;显示出量子计算技术的快速发展和商业应用的不断拓展。在iCV TAnk近期发表的一篇报告中&#xff0c;团队从制度进步、产业生态、投融资形势、总结与展望四个方面对量子计…