AI 助理
备案控制台
开发者社区 人工智能 文章 正文

【数据结构】—从冒泡排序丝滑过度快速排序（含C语言实现）

2023-09-25 275
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】—从冒泡排序丝滑过度快速排序（含C语言实现）

♉️一、前置知识—什么是交换排序

       交换排序的基本思想是通过比较相邻元素的大小关系，如果两个相邻元素的大小关系不满足排序要求，就交换它们的位置，以达到排序的目的。交换排序分为两种，即冒泡排序和快速排序。

♊️二、冒泡排序

       冒泡排序的思想

       冒泡排序是一种基本的排序算法，它的思想是将待排序的元素依次比较相邻的两个元素，根据比较结果交换它们的位置，从而使较大(或较小)的元素逐渐往后移动，最终实现整个序列的排序。

具体的实现过程如下：


       1. 从序列的第一个元素开始，依次比较相邻的两个元素的大小。


       2. 如果前一个元素比后一个元素大（或小），则交换它们的位置。


       3. 继续比较序列中下一个相邻的元素，直至最后一个元素。


       4. 重复以上操作，每一轮比较都将序列中最大（或最小）的元素排到了序列的末尾。


       5. 经过多轮比较后，序列中的元素就按照从小到大（或从大到小）的顺序排好了。

  一图理解~

        冒泡排序的实现

      太简单了，就不多解释了，看代码即可

void BubbleSort(int* a, int n)
{
  for (int j = 0; j < n; ++j)
  {
    bool exchange = false;
    for (int i = 1; i < n-j; i++)
    {
      if (a[i - 1] > a[i])
      {
        int tmp = a[i];
        a[i] = a[i - 1];
        a[i - 1] = tmp;
        exchange = true;
      }
    }
    if (exchange == false)
    {
      break;
    }
  }
}

♋️三、快速排序 （排序算法中的重点，肥肠重要！！！）

      快速排序的思想

       快速排序的基本思想是选定一个轴值，将待排序序列划分为两部分，一部分是小于轴值的元素，一部分是大于轴值的元素。然后对于这两部分分别递归地进行快速排序，直到排序完成。具体实现时，可以选择待排序序列的第一个元素作为轴值（通常需要进行比较选出，后面会详讲），也可以随机选择一个元素作为轴值，然后将序列中的元素与轴值进行比较，小于轴值的元素放在轴值的左边，大于轴值的元素放在轴值的右边，相等的元素可以放在任 一 一边，最后将左右两部分序列递归地进行快速排序即可。快速排序一般有三种实现方法：hoare法、挖坑法、前后指针法。

一图先有个大概的了解~

       以下的内容是循序渐进的，建议大家一步一步往下看！

       快速排序的三种版本实现

       1、hoare版本（基础版本）

       上来请先看一张图~

具体实现步骤如下：

  1. 选择一个基准元素 key，通常可以选择第一个或者最后一个元素作为基准元素（这里的key值选第一个）。
  1. 定义两个指针 left和 right 分别指向数组的开头和结尾。
  2. 从右向左扫描数组，如果当前元素大于或等于基准元素，则指针 right 向左移动一位。
  3. 从左向右扫描数组，如果当前元素小于或等于基准元素，则指针 left 向右移动一位。
  1. 如果 left < right，则交换指针所指向的元素。
  2. 当 left >= right 时，说明当前分区操作已经完成，交换基准元素和 left 指针指向的元素，并返回 left 的值。
  3. 对基准元素左侧的子数组和右侧的子数组分别递归执行上述步骤，直到数组长度为 1 或 0，此时数组就已经排好序了。

一些注意事项：

  1. Hoare 版本的快速排序可以避免对基准元素相同的元素的不必要交换操作，因此比 Lomuto 版本效率更高。
  2. 在实：现时需要注意边界条件的处理，尤其是数组下标越界问题。
  3. 在这里大家可能会有一个疑惑，两个指针i,j相遇的位置的值，如何保证要比key的值小呢？

               答案：右边的值先走就能做到！！！

       当右侧的值先走时，如果它遇到了一个比基准元素小的值，那么它就会停下来，等待左侧的值去找到一个比基准元素大的值。接着左侧的值找到了一个比基准元素大的值后，交换左右值的位置，此时右侧的值就会从原来的位置继续走下去。由于左侧的值都比基准元素小，所以右侧的值再次遇到比基准元素小的值时，仍然会停下来等待左侧的值交换位置。这样，右侧的值先走就可以保证最后相遇的位置的值一定比基准元素的值小。


  在这里大家可能会有一个疑惑了，那我们能左边先走吗？

               当然可以，同样的道理，只需要key值在右边就行了！

        代码实现：

       详见代码内注释

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
int Partsort(int* a, int left, int right)
{
  int key = left;
  while (left < right)
  {
    //找小，注意这里是右向左靠，在最后会的一步将是靠向左边
    while (left < right && a[right] >= a[key])
    {
      --right;
    }
    //找大
    while (left < right && a[left] <= a[key])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);//交换大于key和小于key位置的值
  }
  Swap(&a[key], &a[left]);//此时left==right，交换key和left的值
  return left;//用于递归下一步的key的左半边以及右半边
}
void Quicksort(int* a, int begin, int end)
{
  if (begin >= end)//当下标越界时，直接退出
    return;
  int key = Partsort(a, begin, end);
  // [begin, key-1] key [key+1, end] 大致形状
  Quicksort(a, begin, key - 1);//对左key半边进行排序
  Quicksort(a, key + 1, end);//对右半边进行排序
}
      ♒️快排的优化

       先看个例子：（当我们的快排是排升序，然而我们要排的数据确是一个降序时）

        对此，快速排序有相应的优化：采用“三点取中法”，即：在待排序序列中随机选取三个元素，取中间值作为key值。这样做是为了避免选取到最大或最小值作为 key值，从而导致快排算法性能下降的问题。

       代码实现：

       详见代码内注释

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
int Getmid(int* a, int left, int right)//三点取中值
{
  int mid = (left + right) / 2;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])
    {
      return right;
    }
    else
    {
      return left;
    }
  }
  else
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[right] > a[left])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
int Partsort(int* a, int left, int right)
{
  int mid = Getmid(a, left, right);//三点取中值，优化
  Swap(&a[left], &a[mid]);//将中值放到最左边
  int key = left;
  while (left < right)
  {
    //找小，注意这里是右向左靠，在最后会的一步将是靠向左边
    while (left < right && a[right] >= a[key])
    {
      --right;
    }
    //找大
    while (left < right && a[left] <= a[key])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);//交换大于key和小于key位置的值
  }
  Swap(&a[key], &a[left]);//此时left==right，交换key和left的值
  return left;//用于递归下一步的key的左半边以及右半边
}
void Quicksort(int* a, int begin, int end)
{
  if (begin >= end)//当下标越界时，直接退出
    return;
  int key = Partsort(a, begin, end);
  // [begin, key-1] key [key+1, end] 大致形状
  Quicksort(a, begin, key - 1);//对左key半边进行排序
  Quicksort(a, key + 1, end);//对右半边进行排序
}
   2、 挖坑法

       上来请先看一张图~

挖坑法的实现步骤如下：

  1. 设置左指针left和右指针right，以及基准元素key。
  1. 从右指针开始，向左遍历数组，直到找到第一个小于准元素key的元素，将其填入左指针所在位置的坑中，并将右指针指向左边一位。
  2. 从左指针开始，向右遍历数组，直到找到第一个大于准元素key的元素，将其填入右指针所在位置的坑中，并将左指针指向右边一位。
  3. 重复执行步骤2和步骤3，直到左指针等于右指针。
  4. 将基准元素填入最后的坑中。
  5. 对基准元素左边的子数组和右边的子数组，分别递归执行以上步骤，直到完成排序

一些注意事项：

  • 坑位可以是基准元素的位置，也可以是左指针或右指针的位置。
  • 在填坑的过程中，需要先将当前指针指向的元素保存起来，然后将其填入对应的坑中。
  • 在左指针等于右指针时，需要将基准元素填入最后的坑中。

代码实现：

       详见代码内注释

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
int Getmid(int* a, int left, int right)//三点取中值
{
  int mid = (left + right) / 2;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])
    {
      return right;
    }
    else
    {
      return left;
    }
  }
  else
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[right] > a[left])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
int Partsort2(int* a, int left, int right)
{
  int midi = Getmid(a, left, right);
  Swap(&a[left], &a[midi]);
  int key = a[left];
  // 保存key值以后，左边形成第一个坑
  int hole = left;
  while (left < right)
  {
    // 右边先走，找小，填到左边的坑，右边形成新的坑位
    while (left < right && a[right] >= key)
    {
      --right;
    }
    a[hole] = a[right];
    hole = right;
    // 左边再走，找大，填到右边的坑，左边形成新的坑位
    while (left < right && a[left] <= key)
    {
      ++left;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = key;
  return hole;
}
void Quicksort(int* a, int begin, int end)
{
  if (begin >= end)//当下标越界时，直接退出
    return;
  int key = Partsort2(a, begin, end);
  // [begin, key-1] key [key+1, end] 大致形状
  Quicksort(a, begin, key - 1);//对左key半边进行排序
  Quicksort(a, key + 1, end);//对右半边进行排序
}
3、前后指针法

       上来请先看一张图~

前后指针法的实现步骤如下：

  1. 选取基准数。可以选择数组的第一个元素、最后一个元素、中间元素等。
  2. 设置两个指针，一个指向数组的第一个位置，另一个指向数组的最后一个位置。
  3. 从后往前遍历，找到第一个比基准数小的数，停止遍历。
  4. 从前往后遍历，找到第一个比基准数大的数，停止遍历。
  5. 交换两个数的位置。
  6. 重复步骤3到步骤5，直到前后指针相遇。
  7. 将基准数放到前后指针相遇的位置。
  8. 对基准数左右两边的子序列分别进行快排序。
  9. 重复以上步骤，直到数组被完全排序。

一些注意事项：

        在交换两个数的位置时，如果前后指针指向的数相同，那么就不能进行交换操作，因为这样会导致两个数的值发生变化。同时，在递归的过程中，需要对子序列进行边界检查，避免出现数组越界的情况。

代码实现：

       详见代码内注释

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
int Getmid(int* a, int left, int right)//三点取中值
{
  int mid = (left + right) / 2;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])
    {
      return right;
    }
    else
    {
      return left;
    }
  }
  else
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[right] > a[left])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
// 前后指针
int Partsort3(int* a, int left, int right)
{
  int midi = Getmid(a, left, right);
  Swap(&a[left], &a[midi]);
  int prev = left;//前指针，从最左边开始
  int cur = prev + 1;//后指针
  int keyi = left;
  while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)//当后指针cur找到比key小的值时，先让前指针++prev让prev到交换位置（因为原来比cur小1个位置）再判断前指针是否更cur相等，如果相等了就没有必要再交换了
    {
      Swap(&a[prev], &a[cur]);
    }
    ++cur;//继续遍历找比key值小的值
  }
  Swap(&a[prev], &a[keyi]);//最后交换prev与key的值
  return prev;//此时prev在key最终位置，后续用于递归
}
void Quicksort(int* a, int begin, int end)
{
  if (begin >= end)//当下标越界时，直接退出
    return;
  int key = Partsort3(a, begin, end);
  // [begin, key-1] key [key+1, end] 大致形状
  Quicksort(a, begin, key - 1);//对左key半边进行排序
  Quicksort(a, key + 1, end);//对右半边进行排序
}



   感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！ 

文章标签：
C语言
搜索推荐
算法
关键词：
快速排序C语言
数据结构c语言
C语言数据结构
C语言冒泡排序
数据结构快速排序
慕斯(˘▽˘)っ
目录
相关文章
ephemerals__
|
27天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
123 9
ephemerals__
|
21天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现（c语言）
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低，而三路快排通过将数组分为三部分（小于、等于、大于基准值）来优化这一问题。文章详细讲解了三路快排的实现步骤，并提供了完整的代码示例。
ephemerals__
47 4
ephemerals__
|
26天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
63 16
ephemerals__
|
26天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
87 8
ephemerals__
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
55 4
ephemerals__
|
1月前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
61 3
ephemerals__
|
29天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
42 0
那年春天
|
18天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
23 1
龙大吉
|
6天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
28 5
德国都芳最好
|
21天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
72 21