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

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 【数据结构】-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

相关文章
|
17天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
43 1
|
1月前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
2月前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
32 1
|
1月前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
2月前
|
存储 算法 索引
HashMap底层数据结构及其增put删remove查get方法的代码实现原理
HashMap 是基于数组 + 链表 + 红黑树实现的高效键值对存储结构。默认初始容量为16,负载因子为0.75。当存储元素超过容量 * 负载因子时,会进行扩容。HashMap 使用哈希算法计算键的索引位置,通过链表或红黑树解决哈希冲突,确保高效存取。插入、获取和删除操作的时间复杂度接近 O(1)。
31 0
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
159 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
27 1
|
18天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
41 5
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

推荐镜像

更多