数据结构——排序（交换排序）

目录

一、交换排序的总体概念

二、冒泡排序

三、快速排序

1.挖坑法

2.左右指针

3.前后指针

一、交换排序的总体概念

交换排序是一类排序算法，它的核心思想是通过交换元素的位置来达到排序的目的。在排序过程中，比较数组中的元素对，如果它们的顺序不符合排序要求，就交换它们的位置。在这里主要讲冒泡排序和快速排序。

二、冒泡排序

  • 基本概念：

    • 冒泡排序是一种简单的交换排序算法。它的基本思想是通过反复比较相邻的元素，根据排序要求（升序或降序）交换它们的位置，使得每一轮比较后，最大（或最小）的元素像气泡一样 “浮” 到数组的一端。

  • 工作原理：

    • 对于一个包含 n 个元素的数组，进行 n - 1 轮比较。在每一轮比较中，从数组的第一个元素开始，依次比较相邻的两个元素。如果它们的顺序不符合排序要求（例如在升序排序中，前面的元素大于后面的元素），则交换这两个元素的位置。这样，在每一轮比较结束后，未排序部分的最大元素就会被交换到该轮比较范围的末尾。
    • 随着比较轮数的增加，每一轮需要比较的元素数量逐渐减少。例如，第一轮需要比较 n - 1 对相邻元素，第二轮需要比较 n - 2 对相邻元素，以此类推，最后一轮只需要比较 1 对相邻元素。

  • 特点：

    • 时间复杂度：
      • 最坏情况和平均情况的时间复杂度都是O(n*n)。当数组是逆序（对于升序排序要求）时，每一轮比较都需要进行最多的交换操作，总共需要进行 n - 1 轮比较，所以时间复杂度为O(n*n)。
      • 最好情况时间复杂度为O(n)，当数组已经有序时，只需要进行一轮比较，且不进行任何交换操作，就可以确定数组已经有序。
    • 空间复杂度：空间复杂度为O(1)，因为它只需要一个临时变量来辅助交换相邻元素，属于原地排序算法。
    • 稳定性：冒泡排序是一种稳定的排序算法。在比较相邻元素时，如果两个元素相等，不进行交换，所以相同元素的相对顺序不会改变。

  • 主要步骤

  • 外层循环控制遍历趟数：
    • for (int j = 0; j < n; ++j)外层循环控制整个排序过程的趟数。每一趟都会将当前未确定位置的最大元素移动到正确的位置上。随着趟数的增加，已确定位置的元素越来越多，未确定位置的元素越来越少。
  • 内层循环进行相邻元素比较和交换：
    • int exchange = 0;在内层循环开始前，初始化一个标志变量exchange为 0，表示在当前这一趟中还没有进行过交换。
    • for (int i = 1; i < n - j; ++i)内层循环从数组的第二个元素开始，依次比较相邻的两个元素。如果前一个元素大于后一个元素，就进行交换。
    • if (a[i - 1] > a[i])如果a[i - 1]大于a[i]，则执行交换操作Swap(&a[i - 1], &a[i])，并将exchange设置为 1，表示在这一趟中有过交换。
  • 提前结束排序的条件：
    • if (exchange == 0)在每一趟遍历结束后，检查exchange的值。如果exchange为 0，说明在这一趟中没有进行过交换，即数组已经有序，此时可以提前结束排序。
  • //冒泡排序
void BubbleSort(int* a, int n)
{//控制躺数for (int j = 0; j < n; ++j){int exchange = 0;//控制交换次数for (int i = 1; i < n - j; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0){break;}}
}

三、快速排序

  • 基本概念：

    • 快速排序是一种高效的交换排序算法，它基于分治策略。其基本思想是选择一个基准元素（pivot），将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素，然后对这两部分分别进行快速排序，直到整个数组有序。

  • 工作原理：

    • 首先选择一个基准元素，通常可以选择数组的第一个元素、最后一个元素或中间元素等。以选择第一个元素为基准为例。
    • 设置两个指针，一个从数组的第二个元素开始（左指针），一个从数组的最后一个元素开始（右指针）。左指针向右移动，寻找大于基准元素的元素；右指针向左移动，寻找小于基准元素的元素。当左指针找到大于基准元素的元素，右指针找到小于基准元素的元素时，交换这两个元素的位置。
    • 不断重复上述步骤，直到左指针和右指针相遇。此时，将基准元素与相遇位置的元素交换，这样就将数组分为了两部分，左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。
    • 然后对这两部分子数组分别递归地应用快速排序算法，直到子数组的长度为 1 或 0，此时数组已经有序

  • 特点：

    • 时间复杂度：
      • 平均时间复杂度为O(n*logn)。在每次划分操作中，如果能够将数组比较均匀地分为两部分，那么总共需要进行次划分操作，每次划分操作需要遍历数组中的大部分元素，时间复杂度约为O(n)，所以平均时间复杂度为O(n*logn)。
      • 最坏情况时间复杂度为O(n*n)，当数组已经有序或者逆序（对于选择第一个元素作为基准的情况）时，每次划分得到的两部分子数组长度相差很大，例如一个子数组长度为 n - 1，另一个子数组长度为 0，这样就会导致划分次数达到 n - 1 次，时间复杂度变为O(n*n)。
    • 空间复杂度：
      • 最好情况空间复杂度为O(logn)，这是因为在快速排序的递归过程中，需要使用栈来保存每次划分的子数组信息，在平均情况下，递归深度为logn，所以空间复杂度为O(logn)。
      • 最坏情况空间复杂度为O(n)，当递归深度达到 n 时，例如数组已经有序的情况，需要占用较多的栈空间。
    • 稳定性：快速排序是一种不稳定的排序算法。因为在划分过程中，交换元素的操作可能会改变相同元素的相对顺序。

  • 主要步骤

  • /快速排序
// 三数取中
//GetMidIndex三数取中  校招一般不写
// 防止快速排序遇见有序情况是时间复杂度和直接插入的数量级一样
int GetMidIndex(int* a, int left, int right)
{int mid = (left + right) >> 1;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}

    GetMidIndex函数实现了 “三数取中” 策略，目的是为了在快速排序算法中选择一个较合理的基准值（pivot），以避免在特殊情况下（如数组已基本有序）快速排序算法的性能退化到与直接插入排序相近的时间复杂度。

  • 1.挖坑法

  • // 挖坑法  只写了一趟，若需完整算法，应在QuickSort调用或进行递归
int PartSort1(int* a, int left, int right)
{int index = GetMidIndex(a, left, right);Swap(&a[left], &a[index]);int begin = left, end = right;int pivot = begin;int key = a[begin];// O（N）while (begin < end){// 右边找小，放到左边while (begin < end && a[end] >= key)--end;// 小的放到左边的坑里，自己形成新的坑位a[pivot] = a[end];pivot = end;// 左边找大while (begin < end && a[begin] <= key)++begin;// 大的放到右边的坑里，自己形成新的坑位a[pivot] = a[begin];pivot = begin;}pivot = begin;a[pivot] = key;return pivot;
}

  • 选择基准值并进行交换：

    • int index = GetMidIndex(a, left, right);调用 “三数取中” 函数GetMidIndex选择一个相对中间的元素索引。
    • Swap(&a[left], &a[index]);将这个中间元素与数组最左端的元素交换，使得后续操作可以以a[left]作为基准值进行划分。

  • 初始化变量：

    • int begin = left, end = right;分别定义了两个指针begin和end，分别指向数组的左端和右端。
    • int pivot = begin;定义了一个变量pivot，表示当前的 “坑位” 索引，初始值为begin。
    • int key = a[begin];将基准值存储在变量key中。

  • 划分过程：

    • while (begin < end)循环用于进行划分操作，直到两个指针相遇。
    • 右边找小：
      • while (begin < end && a[end] >= key)从右往左扫描，找到第一个小于基准值的元素。
      • --end;如果找到小于基准值的元素，将指针end向左移动一位。
      • a[pivot] = a[end];将找到的小于基准值的元素放入当前的 “坑位”，同时更新 “坑位” 索引为end。
    • 左边找大：
      • while (begin < end && a[begin] <= key)从左往右扫描，找到第一个大于基准值的元素。
      • ++begin;如果找到大于基准值的元素，将指针begin向右移动一位。
      • a[pivot] = a[begin];将找到的大于基准值的元素放入当前的 “坑位”，同时更新 “坑位” 索引为begin。

  • 2.左右指针

    //左右指针：在挖坑法的基础上，begin找大，end找小
//只不过没有坑了，而是把左右指针换了
//只写了一趟，若需完整算法，应在QuickSort调用或进行递归
int PartSort2(int* a, int left, int right)
{int index = GetMidIndex(a, left, right);//三数取中Swap(&a[left], &a[index]);//永远把关键字放在最左边int begin = left, end = right;int keyi = begin;while (begin < end){// 找小while (begin < end && a[end] >= a[keyi]){--end;}// 找大while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[begin], &a[keyi]);//把之前找的关键字存在begin和end相遇的地方return begin;//返回相遇的地方
}

  • 选择基准值并进行交换：

    • int index = GetMidIndex(a, left, right);调用 “三数取中” 函数选择一个相对中间的元素索引。
    • Swap(&a[left], &a[index]);将中间元素与数组最左端的元素交换，这样后续操作可以以a[left]作为基准值进行划分。

  • 初始化变量：

    • int begin = left, end = right;定义两个指针分别指向数组的左端和右端。
    • int keyi = begin;将基准值的索引初始化为begin。

  • 划分过程：

    • while (begin < end)循环用于进行划分操作，直到两个指针相遇。
    • 找小：
      • while (begin < end && a[end] >= a[keyi])从右往左扫描，找到第一个小于基准值的元素。如果当前元素大于等于基准值，继续向左移动指针end。
      • --end;当找到小于基准值的元素时，将指针end向左移动一位。
    • 找大：
      • while (begin < end && a[begin] <= a[keyi])从左往右扫描，找到第一个大于基准值的元素。如果当前元素小于等于基准值，继续向右移动指针begin。
      • ++begin;当找到大于基准值的元素时，将指针begin向右移动一位。
    • Swap(&a[begin], &a[end]);当找到一 “小” 一 “大” 两个元素后，交换它们的位置。

  • 确定基准值的最终位置并返回：

    • Swap(&a[begin], &a[keyi]);当左右指针相遇时，将基准值与相遇位置的元素交换，确定基准值的最终位置。
    • return begin;返回相遇位置的索引，即基准值在排序后的位置。

  • 3.前后指针

    //前后指针法：cur找小，每次遇到比key小的值，就停下来，++prev
//然后交换cur和prev位置的值
//核心思想就是把小的值往前移
int PartSort3(int* a, int left, int right)
{int index = GetMidIndex(a, left, right);//三数取中Swap(&a[left], &a[index]);int keyi = left;//永远把关键字放在最左边int prev = left, cur = left + 1;//形成前后指针while (cur <= right){if (a[cur] < a[keyi]&& ++prev != cur)//如果++prev和cur相等，不用换，提高效率{Swap(&a[prev], &a[cur]);}++cur;//不论是否小于，cur都要往前移，所以cur和prev也许中间隔了好几个大的数}Swap(&a[keyi], &a[prev]);//把关键字放在此时prev的位置return prev;
}

  • 选择基准值并进行交换：

    • int index = GetMidIndex(a, left, right);调用 “三数取中” 函数选取相对中间的元素索引。
    • Swap(&a[left], &a[index]);将中间元素与数组最左端的元素交换，后续以a[left]作为基准值进行划分。

  • 初始化变量：

    • int keyi = left;将基准值的索引设置为left，表示基准值在数组的最左端。
    • int prev = left, cur = left + 1;初始化前后指针，prev初始指向基准值，cur指向基准值的下一个位置。

  • 划分过程：

    • while (cur <= right)循环用于遍历数组，进行划分操作。
    • if (a[cur] < a[keyi] && ++prev!= cur)如果当前元素小于基准值，且prev自增后不等于cur，说明需要交换。交换a[prev]和a[cur]，这样就将小于基准值的元素移动到了左边。
    • ++cur;无论当前元素是否小于基准值，cur都要向前移动，继续检查下一个元素。

  • 确定基准值的最终位置并返回：

    • Swap(&a[keyi], &a[prev]);循环结束后，将基准值与prev位置的元素交换，确定基准值在排序后的位置。
    • return prev;返回基准值的最终位置索引。

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

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

相关文章

小赢卡贷公益行：乡村振兴与多元公益并进

小赢卡贷公益行：乡村振兴与多元公益并进

在金融科技的浪潮中&#xff0c;小赢卡贷不仅以其创新的金融产品和服务赢得了市场的广泛认可&#xff0c;更以其背后的公益之心&#xff0c;积极履行社会责任&#xff0c;传递着温暖与希望。小赢公益基金会&#xff0c;作为小赢卡贷社会责任的延伸&#xff0c;主要聚焦于乡村振…
阅读更多...
衡石分析平台系统管理手册-智能运维之系统设置

衡石分析平台系统管理手册-智能运维之系统设置

系统设置​ HENGSHI 系统设置中展示了系统运行时的一些参数&#xff0c;包括主程序相关信息&#xff0c;Base URL、HTTP 代理、图表数据缓存周期、数据集缓存大小、租户引擎等相关信息。 主程序​ 系统设置中展示了主程序相关信息&#xff0c;这些信息是系统自动生成的&#…
阅读更多...
springboot宿舍管理-计算机毕业设计源码40740

springboot宿舍管理-计算机毕业设计源码40740

摘要 宿舍管理系统作为一种利用信息技术改善学生住宿管理的工具&#xff0c;在大学宿舍管理中具有重要的实际意义。本文通过对国内外研究现状的调查和总结&#xff0c;探讨了宿舍管理系统的论文主题、研究背景、研究目的、研究意义以及主要研究内容。 首先&#xff0c;宿舍管理…
阅读更多...
心觉：购物选择困难症! 为什么你总是挑不出“最完美”的商品？

心觉：购物选择困难症! 为什么你总是挑不出“最完美”的商品？

Hi&#xff0c;我是心觉&#xff0c;与你一起玩转潜意识、脑波音乐和吸引力法则&#xff0c;轻松掌控自己的人生&#xff01; 挑战每日一省写作194/1000天 你有没有遇到过这样一种情况&#xff1a;打算买一款新的电子产品、家具或者衣服 但在网上和实体店翻来覆去&#xff0…
阅读更多...
编译链接的过程发生了什么？

编译链接的过程发生了什么？

一&#xff1a;程序的翻译环境和执行环境 在 ANSI C 的任何一种实现中&#xff0c;存在两个不同的环境。 第 1 种是翻译环境&#xff0c;在这个环境中源代码被转换为可执行的机器指令。 第 2 种是执行环境&#xff0c;它用于实际执行代码 也就是说&#xff1a;↓ 1&#xff1…
阅读更多...
ai免费写论文是原创吗？分享5款ai写作免费一键生成助手

ai免费写论文是原创吗？分享5款ai写作免费一键生成助手

在当今的学术研究和写作领域&#xff0c;AI技术的应用越来越广泛&#xff0c;尤其是在论文写作方面。许多AI写作工具声称能够一键生成高质量的论文&#xff0c;并且保证原创性。然而&#xff0c;这些工具是否真的能生成完全原创的论文&#xff0c;仍然是一个值得探讨的问题。 …
阅读更多...
【动态规划-最长递增子序列（LIS）】【hard】力扣1671. 得到山形数组的最少删除次数

【动态规划-最长递增子序列（LIS）】【hard】力扣1671. 得到山形数组的最少删除次数

我们定义 arr 是 山形数组 当且仅当它满足&#xff1a; arr.length > 3 存在某个下标 i &#xff08;从 0 开始&#xff09; 满足 0 < i < arr.length - 1 且&#xff1a; arr[0] < arr[1] < … < arr[i - 1] < arr[i] arr[i] > arr[i 1] > … &g…
阅读更多...
掌握甘特图，没有Excel也能轻松制作的技巧

掌握甘特图，没有Excel也能轻松制作的技巧

甘特图是项目管理中常用工具&#xff0c;由亨利甘特发明。不擅长Excel者可用ZohoProjects等软件创建甘特图&#xff0c;其直观展示项目时间和任务&#xff0c;支持实时协作、工时管理等功能&#xff0c;广泛应用于各领域项目管理。 一、甘特图的由来 甘特图最初是由工程师和管…
阅读更多...
tp5 fastadmin列表页图片批量压缩并下载

tp5 fastadmin列表页图片批量压缩并下载

记录&#xff1a;tp5 fastadmin对列表页选中数据的多张图片进行压缩并下载。 html代码 <a href"javascript:;" class"btn btn-info btn-apple btn-disabled disabled {:$auth->check(zhuanli/zhuanli/xiazai)?:hide}" title"批量下载专利证书…
阅读更多...
selenium-Alert类用于操作提示框/确认弹框（4）

selenium-Alert类用于操作提示框/确认弹框（4）

之前文章我们提到&#xff0c;在webdriver.WebDriver类有一个switch_to方法&#xff0c;通过switch_to.alert()可以返回Alert对象&#xff0c;而Alert对象主要用于网页中弹出的提示框/确认框/文本输入框的确认或者取消等动作。 Alert介绍 当在页面定位到提示框/确认框/文本录入…
阅读更多...
如何通过systemed实现Linux脚本在服务器的开机自启动，解决网络摄像机IPC通过 域名接入视频监控平台出现离线的问题。

如何通过systemed实现Linux脚本在服务器的开机自启动，解决网络摄像机IPC通过 域名接入视频监控平台出现离线的问题。

目录 一.问题描述和分析 二.实现脚本开机自启动的过程 2.1确认该系统是不是systemed系统 2.2创建并配置该脚本的systemd服务 2.2.1创建服务 2.2.2配置服务 2.3启动服务 三.问题解决结果 3.1查看服务状态 3.2查看摄像机在线状态 3.3查看视频是否正常 一.问题描述和分…
阅读更多...
leetcode:反转字符串中的单词III

leetcode:反转字符串中的单词III

题目链接 string reverse(string s1) {string s2;string::reverse_iterator rit s1.rbegin();while (rit ! s1.rend()){s2 *rit;rit;}return s2; } class Solution { public:string reverseWords(string s) {string s1; int i 0; int j 0; int length s.length(); for (i …
阅读更多...
C++关于树的基础知识

C++关于树的基础知识

首先区分概念 “度为m的树”指的是至少有一个结点的度是m&#xff0c;一定是非空树 “m叉树”指的是允许所有的结点都小于m&#xff0c;且可以是空树 常见考点&#xff1a; 度为m的树的第i层最多有个结点 &#xff08;对于m叉树也相同&#xff09; 第一层m的0次方 第二层m的…
阅读更多...
电池大师 2.3.9 | 专业电池管理，延长寿命优化性能

电池大师 2.3.9 | 专业电池管理，延长寿命优化性能

Battery Guru 显示电池使用情况信息&#xff0c;测量电池容量&#xff08;mAh&#xff09;&#xff0c;并通过有用技巧帮助用户改变充电习惯&#xff0c;延长电池寿命。支持显示电池健康状况&#xff0c;优化电池性能。 大小&#xff1a;9.6M 百度网盘&#xff1a;https://pan…
阅读更多...
多模态大语言模型（MLLM）-InstructBlip深度解读

多模态大语言模型（MLLM）-InstructBlip深度解读

前言 InstructBlip可以理解为Blip2的升级版&#xff0c;重点加强了图文对话的能力。 模型结构和Blip2没差别&#xff0c;主要在数据集收集、数据集配比、指令微调等方面下文章。 创新点 数据集收集&#xff1a; 将26个公开数据集转换为指令微调格式&#xff0c;并将它们归类…
阅读更多...
创建osd加入集群

创建osd加入集群

故障原因&#xff1a;ceph节点一个磁盘损坏&#xff0c;其中osd69 down了&#xff0c;需要更换磁盘并重新创建osd加入ceph集群。 信息采集&#xff1a; 更换磁盘前&#xff0c;查询osd69对应的盘符&#xff1a; 将对应的故障磁盘更换后&#xff0c;并重做raid&#xff0c;然后查…
阅读更多...
≌图概念凸显有长度不同的射线

≌图概念凸显有长度不同的射线

黄小宁 【摘要】自有射线概念后的2300年里一直无人能知有长度不同的射线、无人能知有互不≌的射线&#xff0c;从而使数学一直有几何“常识”&#xff1a;任何射线都没有长度差别。保距变换和≌图概念使人能一下子看到有长度不同的射线。 变量x所取各数也均由x代表&#xff0c…
阅读更多...
1. Keepalived概念和作用

1. Keepalived概念和作用

1.keepalived概念 (1)解决单点故障(组件免费) (2)可以实现高可用HA机制 (3)基于VRR协议(虚拟路由沉余协议) 2.keepalived双机主备原理
阅读更多...
DockerCompose 启动 open-match

DockerCompose 启动 open-match

背景介绍 open-match是Google和unity联合开源的支持实时多人匹配的框架&#xff0c;已有多家游戏厂商在生产环境使用&#xff0c;官网 https://open-match.dev/site/ 。原本我们使用的是UOS上提供的匹配能力&#xff0c;但是UOS目前不支持自建的Dedicated servers 集群&#x…
阅读更多...
ai论文写作软件哪个好？分享5款ai论文题目生成器

ai论文写作软件哪个好？分享5款ai论文题目生成器

在当前的学术研究和写作领域&#xff0c;AI论文写作软件已经成为提高效率和质量的重要工具。根据多个来源的评测和推荐&#xff0c;以下是五款值得推荐的AI论文写作软件&#xff0c;其中特别推荐千笔-AIPassPaper。 1. 千笔-AIPassPaper 千笔-AIPassPaper是一款基于深度学习和…
阅读更多...
最新文章

Copyright @ 2022~2023