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

数据结构（初阶）—— 排序算法（下）（1）

2022-11-24 101
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构（初阶）—— 排序算法（下）（1）

一、冒泡排序

       基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

1.动图演示

2.代码实现 

// 冒泡排序
void Swap(int* px, int* py)
{
  int tmp = *px;
  *px = *py;
  *py = tmp;
}
void BubbleSort(int* a, int n)
{
  int end = n;
  while (end > 0)
  {
    int exchange = 0;
    for (int j = 0; j < end - 1; j++)
    {
      if (a[j] > a[j + 1])
      {
        exchange = 1;
        Swap(&a[j], &a[j + 1]);
      }
    }
    --end;
    if (exchange == 0)
    {
      break;
    }
  }
  /*for (int i = 0; i < n - 1; i++)
  {
    for (int j = 0; j < n - i - 1; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
      }
    }
  }*/
}

二、快速排序

       快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

基本思想如下：

1ecd1b2606ed46e9956a89f231c9802c.png

1. 递归实现

1.Hoare版本（含动图演示）

动图演示

image.gif

代码实现 

int Partion1(int* a,int left,int right)
{
  int keyi = left;
  while (left < right)
  {
    //右边先走，找小
    while (a[right] > a[keyi])
    {
      --right;
    }
    //左边再走，找大
    while (a[left] < a[keyi])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  return left;
}

上述代码存在两大缺陷:

场景1：

如果是一个有序的数组（升序），每个数都比第一个数大，小黄就没人管了，撒开腿就一直跑；

1ecd1b2606ed46e9956a89f231c9802c.png

场景2：

如果这个数组元素都相同，小黄先跑，发现跑不动；（死循环）

image.png

针对刚才的代码很明显在这两种场景下一定会出问题；

如何解决：

1.确保 右边找小 或 左边找大 的时候，判断它（小黄或小白）的下标有没有越界；

2.要考虑元素相等的情况；

int Partion1(int* a,int left,int right)
{
  int keyi = left;
  while (left < right)
  {
    //右边先走，找小
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
    //左边再走，找大
    while (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  return left;
}

 单趟排序完成之后，比key大的数都放在右边，比key小的数都放在左边，只要以key为基准值，它的左子区间再有序，右子区间再有序，那么整体就有序了；这种问题和二叉树很类似；第一趟排序找了一个key，分成了左右区间，只要为左右区间各找一个key，不断的去划分，那么久把整个数组排序完成了；

int Partion1(int* a,int left,int right)
{
  int keyi = left;
  while (left < right)
  {
    //右边先走，找小
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
    //左边再走，找大
    while (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  return left;
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
    int keyi = Partion1(a, left, right);/*hoare版本*/
        //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);//左子区间
    QuickSort(a, keyi + 1, right);//右子区间
  }
}

如何定位基准值（key）：

       先看下面的图例，发现快排在针对无序的数组进行排序时，它的效率是很快的，但是在有序或接近有序的情况下，就会变得很糟糕；这里最关键的就是key的选择问题； 也就是如何针对快排对于数组有序情况下选key的问题；

1ecd1b2606ed46e9956a89f231c9802c.png

为了解决选key的问题，可以采用三数取中法；

三数取中法：最左边的数、中间数、最右边的数；

1ecd1b2606ed46e9956a89f231c9802c.png

对这三个数进行比较，选出一个中间值(既不是最大也不是最小)，作为key； 那么针对于有序的情况，就会瞬间变得很好，直接将数据二分；

快排完整动图

image.gif

代码实现  

/*hoare版本*/
//快排（递归）
//三数取中
int GetMidIndex(int* a, int left, int right)
{
  //int mid = (left + right) / 2;
  int mid = left + ((right - left) >> 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;
    }
  }
}
int Partion1(int* a,int left,int right)
{
  //三数取中
  int mini = GetMidIndex(a, left, right);
  Swap(&a[mini], &a[left]);
  int keyi = left;
  while (left < right)
  {
    //右边先走，找小
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
    //左边再走，找大
    while (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  return left;
}
//O(N*logN)
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
  //小区间优化，当分割到小区间时，不在用递归思路让这段子区间有序
  //对于递归快排，减少递归次数
  if (right - left + 1 < 10)
  {
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    int keyi = Partion1(a, left, right);/*hoare版本*/
    //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
  }
}

在上面的代码中有这样一段代码：

    if (right - left + 1 < 10)
  {
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    int keyi = Partion1(a, left, right);/*hoare版本*/
    //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
  }

由于采用递归的方式进行快排，如果数据量很大，就会造成栈的溢出；为了解决这个问题，采用了一个小区间优化的方法，在不断划分区间去进行递归的时候，越往下划分区间越来越小，但是区间数量越来越多，递归次数也越来越多；我们采取当区间相差小于10（最低给10）时，直接让这些区间的数据进行直接插入排序；

1ecd1b2606ed46e9956a89f231c9802c.png

2.挖坑法 （含动图演示）

1.基本思路：

       先将第一个变量存储在临时变量key中，右边先走，去找小扔到左边的坑，自己成为新的坑；然后左边再走，去找大扔到右边的坑( pivot )，自己成为新的坑( pivot )；直到两者相遇把保存的key的值放进坑( pivot )；


image.png

2.动图演示

下图为挖坑法的单趟演示，其完整排序和上面的快排完整版类似，需要划分左右子区间； 进行递归调用

20201204182323419.gif

3.代码实现

//挖坑法
//三数取中
int GetMidIndex(int* a, int left, int right)
{
  //int mid = (left + right) / 2;
  int mid = left + ((right - left) >> 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;
    }
  }
}
int Partion2(int* a, int left, int right)
{
  //三数取中
  int mini = GetMidIndex(a, left, right);
  Swap(&a[mini], &a[left]);
  int key = a[left];
  int pivot = left;
  while (left < right)
  {
    //右边找小，扔到左边的坑
    while (left < right && a[right] >= key)
    {
      --right;
    }
    a[pivot] = a[right];
    pivot = right;//自己形成新的坑
    //左边找大，扔到右边的坑
    while (left < right && a[left] <= key)
    {
      ++left;
    }
    a[pivot] = a[left];
    pivot = left;//自己形成新的坑
  }
  a[pivot] = key;
  return pivot;
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
  //小区间优化，当分割到小区间时，不在用递归思路让这段子区间有序
  //对于递归快排，减少递归次数
  if (right - left + 1 < 10)
  {
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    //int keyi = Partion2(a, left, right);//挖坑法
    //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
  }
}

3.前后指针法 （含动图演示）

1.基本思路：

       前后指针法的基本思想其实和前面两种方法类似，cur去找小，prev去找大；也会得到key的左边是小值右边是大值；

20210505110855951.gif

2.代码实现

//前后指针法
//三数取中
int GetMidIndex(int* a, int left, int right)
{
  //int mid = (left + right) / 2;
  int mid = left + ((right - left) >> 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;
    }
  }
}
int Partion3(int* a, int left, int right)
{
  //三数取中
  int mini = GetMidIndex(a, left, right);
  Swap(&a[mini], &a[left]);
  int keyi = left;
  int prev = left;
  int cur = left +1;
  while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[cur], &a[prev]);
    }
    cur++;
  }
  Swap(&a[prev], &a[keyi]);
  return prev;
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
  //小区间优化，当分割到小区间时，不在用递归思路让这段子区间有序
  //对于递归快排，减少递归次数
  if (right - left + 1 < 10)
  {
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    int keyi = Partion3(a, left, right);//前后指针法
    //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
  }
}
文章标签：
搜索推荐
存储
关键词：
数据结构算法
数据结构排序算法
霄沫凡M
目录
相关文章
土木林森
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
49 1
java冯坚持
|
3月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
99 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
光明顶阳顶天
|
2月前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体，算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心，对于提高程序的质量和性能具有至关重要的作用
光明顶阳顶天
57 24
德国都芳最好
|
2月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化？
德国都芳最好
58 19
XIAZHI
|
2月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中，路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法（DFS）和宽度优先算法（BFS）。DFS使用栈实现，适合路径问题；BFS使用队列，保证找到最短路径。两者均能有效查找路由信息，但适用场景不同，需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果，验证了算法的有效性。
XIAZHI
112 23
XIAZHI
|
2月前
|
算法
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法，通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置，逐步优化适应度，最终找到问题的最优解。代码实现了单链表结构，用于管理蜜蜂节点，并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点，但也存在对初始化参数敏感、计算复杂度高等缺点。
XIAZHI
62 20
XIAZHI
|
2月前
|
机器学习/深度学习 算法 C++
数据结构之鲸鱼算法
鲸鱼算法（Whale Optimization Algorithm，WOA）是由伊朗研究员Seyedali Mirjalili于2016年提出的一种基于群体智能的全局优化算法，灵感源自鲸鱼捕食时的群体协作行为。该算法通过模拟鲸鱼的围捕猎物和喷出气泡网的行为，结合全局搜索和局部搜索策略，有效解决了复杂问题的优化需求。其应用广泛，涵盖函数优化、机器学习、图像处理等领域。鲸鱼算法以其简单直观的特点，成为初学者友好型的优化工具，但同时也存在参数敏感、可能陷入局部最优等问题。提供的C++代码示例展示了算法的基本实现和运行过程。
XIAZHI
58 0
java冯坚持
|
3月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十：排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法，以及常见的时间复杂度级别，并简单提及了空间复杂度。
java冯坚持
50 1
数据结构与算法学习十：排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
XIAZHI
|
2月前
|
算法 vr&ar 计算机视觉
数据结构之洪水填充算法（DFS）
洪水填充算法是一种基于深度优先搜索（DFS）的图像处理技术，主要用于区域填充和图像分割。通过递归或栈的方式探索图像中的连通区域并进行颜色替换。本文介绍了算法的基本原理、数据结构设计（如链表和栈）、核心代码实现及应用实例，展示了算法在图像编辑等领域的高效性和灵活性。同时，文中也讨论了算法的优缺点，如实现简单但可能存在堆栈溢出的风险等。
XIAZHI
59 0
龙大吉
|
3月前
|
存储 算法 Java
Set接口及其主要实现类（如HashSet、TreeSet）如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类（如HashSet、TreeSet）如何通过特定数据结构和算法确保元素唯一性，并提供了最佳实践建议，包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
龙大吉
55 4

热门文章

最新文章

  • 1
    Python编程数据结构的深入理解
  • 2
    掌握Pandas核心数据结构：Series与DataFrame的四种创建方式
  • 3
    K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
  • 4
    Python 中的数据结构与其他编程语言数据结构的区别
  • 5
    C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
  • 6
    Python 中的数据结构和算法优化策略
  • 7
    Python 中数据结构和算法的关系
  • 8
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
  • 9
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
  • 10
    Pandas数据结构：Series与DataFrame
  • 1
    【Python进阶（七）】——Series数据结构
    186
  • 2
    Redis数据结构精讲：选择与应用实战指南
    1335
  • 3
    深入浅出数据结构之布隆过滤器
    75
  • 4
    数据结构/C++：位图 & 布隆过滤器
    49
  • 5
    数据结构/C++：哈希表
    84
  • 6
    数据结构/C++：红黑树
    47
  • 7
    数据结构/C++：AVL树
    49
  • 8
    栈的基本应用
    64
  • 9
    栈与队列理解
    49
  • 10
    数据结构/C++：二叉搜索树
    54

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解
  • 相册服务中的故事生成算法介绍
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 图解算法小抄

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月