【数据结构】-8种排序解析(详细总结,简洁,含代码,例题)(一)

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 【数据结构】-8种排序解析(详细总结,简洁,含代码,例题)

一.8种排序方式总览分析(带图)

   1.按方式分类(比较排序)

image.png

*计数排序:非比较排序

二.8种排序方式详细解析

    1.计数排序

注意:计数排序适合范围集中,且范围不大的整型数组排序。不适合范围分散或者非整型的排序,如:字符串、浮点数 等


步骤:


1.找到原数组最大的值,记作range


2.设置一个计数数组,遍历一遍原数组O(n),统计每个数据出现的次数。


3.遍历一遍计数数组O(range)


计数排序分为:相对映射型和非相对映射型(相对位置)


图示意:

image.png

 2.冒泡排序

遍历有序区间的各个数,从其开始到结尾的区间内轮转交换不断缩小区间

原理:不断把大/小的数移到后面

注意点:为提高效率,当发现一次循环中没有数对交换,即可中止循环。

void BubbleSort(int*a,int n)
{
  int i = 0,j=0;
  for (j = 0; j<n; j++)
  {
    bool exchange = false;
    for (i = 0; i < n-j; i++)
    {
      if (a[i + 1] < a[i])
      {
        Swap(&a[i + 1], &a[i]);
        exchange = true;
      }
    }
        //加入判断环节,提前终止,提高效率
    if (exchange == false)
    {
      break;
    }
  }
}

    3.选择排序

遍历有序区间的各个数,找出其之后的最大/最小数并与该数之后的数进行替换。


代码的设计思路是设置left,right下标从数组两端向中间遍历,依次筛选出最大值和最小值mini,maxi,并分别与left,riight进行交换。


注意点:在交换过程中,left所处的位置可能正好被maxi标记,接下来下一步maxi与right的交换则会出错,right无法与正确的maxi交换。


解决方法:如果left和maxi重叠,交换后要修正

void SelectSort(int* a, int n)
{
  int left = 0;
  int right = n;
  while (left < right)
  {
    int mini = left, maxi = right;
    for (int i =left+1; i <= right; i++)
    {
      if (a[i] > a[maxi])
      {
        maxi = i;//移动下标
      }
      if (a[i] < a[mini])
      {
        mini = i;
      }
    }
    Swap(&a[left], &a[mini]);
    if (left == maxi)
    {
      maxi = mini;
    }
    Swap(&a[right], &a[maxi]);
    left++;
    right--;
  }
}

 4.插入排序

遍历有序区间的各个数,把其视作临时变量tmp,分别于它前面的数进行对比,

其进一步优化即为“希尔排序”

注意点:此算法中,当tmp比第一个数大/小时,end会到-1的位置。所以采用图中标记用法

image.png

//升序
void InsertSort(int* a, int n)//a 数组  n 个数
{
  int i = 0;
  for (i = 1; i < n; i++)
  {
    int end = i - 1;
    int tmp = i;
    while (end >= 0)
    {
      if (a[tmp] < a[end])
      {
        //整体后移
        a[end + 1] = a[end];
        --end;
      }
      else
      {
        break;
      }
    }
    //填空
    a[end + 1] = a[tmp];
  }
}

5.希尔排序

其可以理解为在插入排序的基础上进行预排序(分组插排)

注意点:图示辅助理解循环:

image.png

void ShellSort(int* a, int n)
{
  //gap==1 插入排序
  //gap>1预先排序
  int gap=n;
  //升序
  while(gap>1)
  { 
    gap = gap / 2;
    //gap=gap/3+1     确保gap的跳跃到最后为1,
    int i = 0;
    for (i = 0; i < n-gap; i++)
    {
      int end = i;
      int tmp = i+gap;
      while (end >= 0)
      {
        if (a[tmp] < a[end])
        {
          //整体后移
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      //填空
      a[end + gap] = a[tmp];
    }
  }
}

 6.堆排序

详情可见博主关于堆排详解:

image.png

 7.快速排序(递归和非递归写法)

任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中的所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。


注意点:当快速排序接近二分(二叉树)的递归模式时,效率最高。因此引入“三数取中”优化代码:

int GetMidNumi(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 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;
    }
  }
}

    1.三种排序方式

 1.交换法


  1.左边做key,右边先走——保证相遇位置比key小


    ps:【右边先走找比key小的数,则其停止位置一定小于等于key】


  2.由于左右相遇的位置一定比key小,把左边与相遇位置替换


图示:

image.png


image.png

代码:

2.挖坑法

  1.先将左边第一个数据放在临时变量key中,原地形成一个坑位

 2.右边先动,找小于key的数,放到坑位中,并且原地新生成一个坑位

 3.当左右相遇时,将key填入最后一个坑位中

1.png

3.前后指针法(玩区间)


 1.左边第一个数设为key,prev(延迟指针),cur(实时指针)


 2.cur开始向右移动,找到比key小的值prev和cur同时移动


 3.找到比key大的值只移动cur——保证prev和cur中间隔着一段比key大的区间


 4.找到比key小的值时,交换prev下一个位置(比key大的区间)和cur位置的值——比key大的值翻到区间右边,把比key小的值翻到区间左边。

图示:

2.png

相关文章
|
1月前
|
搜索推荐 UED Python
实现一个带有昼夜背景切换的动态时钟:从代码到功能解析
本文介绍了一个使用Python和Tkinter库实现的动态时钟程序,具有昼夜背景切换、指针颜色随机变化及整点和半点报时功能。通过设置不同的背景颜色和随机变换指针颜色,增强视觉吸引力;利用多线程技术确保音频播放不影响主程序运行。该程序结合了Tkinter、Pygame、Pytz等库,提供了一个美观且实用的时间显示工具。欢迎点赞、关注、转发、收藏!
134 94
|
16天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
67 29
|
16天前
|
存储 机器学习/深度学习 人工智能
C 408—《数据结构》易错考点200题(含解析)
408考研——《数据结构》精选易错考点200题(含解析)。
90 27
|
1月前
|
SQL Java 数据库连接
如何在 Java 代码中使用 JSqlParser 解析复杂的 SQL 语句?
大家好,我是 V 哥。JSqlParser 是一个用于解析 SQL 语句的 Java 库,可将 SQL 解析为 Java 对象树,支持多种 SQL 类型(如 `SELECT`、`INSERT` 等)。它适用于 SQL 分析、修改、生成和验证等场景。通过 Maven 或 Gradle 安装后,可以方便地在 Java 代码中使用。
262 11
|
1月前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
36 10
|
1月前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
41 7
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
332 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
54 1
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
3天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。

热门文章

最新文章

推荐镜像

更多