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

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

 2.非递归写法(类比层序遍历用队列实现,这里用栈)

学习原因:递归的本质是不断开辟空间,当递归层数过多时可能会出现栈溢出的问题。因而引入非递归写法


实现原理:递归写法本质上是向下不断开辟空间,当达到终止条件时返回并归还空间。不采用递归的写法,即可以在原数组上直接对下标进行划分


1.入尾标,入头标


2.标记begin,end后,进行头删,并算出keyi


3.此时,原数组被分割成【begin,keyi-1】keyi【keyi+1,end】。


分别对存在的区间进行同样的操作(压栈,出栈)即可。


图示:

image.png

PS:数字表示,可视作递归的层数。而实际上没有递归。 

void quicksortnonr(int*a,int left,int right)
{
  ST st;
  StackInit(&st);
  StackPush(&st, right);//表示end的先入栈
  StackPush(&st, left);
  while (!StackEmpty(&st))
  {
    int begin = StackTop(&st);
    StackPop(&st);
    int end = StackTop(&st);
    StackPop(&st);
        //得出keyi
    int keyi = Partsort3(a, begin, end);//三数取中
    //【begin,keyi-1】keyi【keyi+1,end】
    if (keyi + 1 < end)
    {
      StackPush(&st, end);//表示end的先入栈
      StackPush(&st, keyi+1);
    }
    if (keyi -1 >begin)
    {
      StackPush(&st, keyi - 1);//表示end的先入栈
      StackPush(&st, begin);
    }
  }
  StackDestroy(&st);
}

8.归并排序(递归和非递归写法)

1.递归写法

归并原理:两个有序数组进行比较,并尾插到新空间。


PS:结合递归后,即可细分到只剩两个数归并形成有序数组,两两合成新的有序序列,并拷贝到一块新空间(避免覆盖原数组),新空间的位置关系要与原数组对应


形象图示:

image.png

注意点:为提升效率,采用取中间数进行划分

图示:

image.png

void MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
    return;
  int mid = (begin + end) / 2;
  MergeSort(a,begin,mid,tmp);
  MergeSort(a,mid+1,end,tmp);
  //拷贝回与原数组a相对应的位置
  memcpy(a + begin,tmp + begin,sizeof(int) * (end - begin + 1));
}

递归实现的逻辑:后序遍历

PS:后序遍历相关可查看博主相关博客

3.png

 2.非递归写法(注意越界情况的分类讨论)

分析:与快排的非递归算法同理。当递归次数过多时,有可能会导致栈溢出。不妨在原数组的基础上,直接对下标对应区间范围内的数组进行归并,并拷贝回原数组。

形象图示:

image.png

注意点:有时候gap的选取会越界!


分析:本质上是不断选取【begin1,end1】【begin2,end2】


注意点:以下分析是在归并进行前,对下标对应空间进行讨论!


1.当begin1和end2和并后形成新begin1,end1时,若end1临界(begin2越界)/end1越界,则停止归并


2.当end1越界时,则对end1进行修正


形象图示:  

image.png

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail\n");
    return;
  }
  int gap = 1;
  while (gap < n)
  {
    for (int i = 0; i < n; i += 2 * gap)
    {
      // [begin1,end1][begin2, end2]
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;//((i+gap)+(gap-1))
      //printf("[%d,%d][%d,%d] ", begin1, end1,begin2,end2);
            //分类讨论情况
      if (end1 >= n || begin2 >= n)
      {
        break;
      }
      if (end2 >= n)
      {
        end2 = n - 1;//修正end2区间
      }
      printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
      int j = i;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
      // 归并一部门拷贝一部分
      memcpy(a+i, tmp+i, sizeof(int) *(end2-i+1));
    }
    printf("\n");
    gap *= 2;
  }
  free(tmp);
}

三.8种排序方式复杂度/稳定性分析

    1.稳定性的概念

假定再待排序的记录序列中,存在多个具有相同关键字的记录,若经过排序,这些记录的相对次序保持不变,则称这种算法是稳定的。

    2.分析

image.png

  *计数排序较为特别,时间复杂度O(n)/O(range),空间复杂度为O(n)

 1.简单选择排序不稳定的原因

特例:替换的数在两相同数同一边时

image.png

 2.复杂度分析综述

1.希尔排序是直接插入排序基础上加了预处理。较为复杂,暂记结论。

image.png

2.直接插入排序,是取每一个数和前面所有数进行比对。无论如何都要先取,所以最好情况即有序情况即是n,最坏情况相当于一个数组的遍历,n^2。


3.快速排序当keyi每次都能取中间值时,接近二叉树,nlogn。keyi每次都取最左/右值时,即相当于一个数组的遍历,n^2。


4.归并排序,接近二叉树,nlogn。由于需要tmp新空间容纳归并后的新空间,空间复杂度为n


5.堆排序,分为堆调整(向上向下)和用删除思想堆排序两部分,根据数学计算知道后者复杂度为nlogn,即堆排整体为nlogn。

————————————————

版权声明:本文为CSDN博主「你的小笔记本YY」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/YYDsis/article/details/130110495

相关文章
|
1月前
|
搜索推荐 UED Python
实现一个带有昼夜背景切换的动态时钟:从代码到功能解析
本文介绍了一个使用Python和Tkinter库实现的动态时钟程序,具有昼夜背景切换、指针颜色随机变化及整点和半点报时功能。通过设置不同的背景颜色和随机变换指针颜色,增强视觉吸引力;利用多线程技术确保音频播放不影响主程序运行。该程序结合了Tkinter、Pygame、Pytz等库,提供了一个美观且实用的时间显示工具。欢迎点赞、关注、转发、收藏!
134 94
|
12天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
65 29
|
12天前
|
存储 机器学习/深度学习 人工智能
C 408—《数据结构》易错考点200题(含解析)
408考研——《数据结构》精选易错考点200题(含解析)。
84 27
|
1月前
|
SQL Java 数据库连接
如何在 Java 代码中使用 JSqlParser 解析复杂的 SQL 语句?
大家好,我是 V 哥。JSqlParser 是一个用于解析 SQL 语句的 Java 库,可将 SQL 解析为 Java 对象树,支持多种 SQL 类型(如 `SELECT`、`INSERT` 等)。它适用于 SQL 分析、修改、生成和验证等场景。通过 Maven 或 Gradle 安装后,可以方便地在 Java 代码中使用。
229 11
|
2月前
|
自然语言处理 搜索推荐 数据安全/隐私保护
鸿蒙登录页面好看的样式设计-HarmonyOS应用开发实战与ArkTS代码解析【HarmonyOS 5.0(Next)】
鸿蒙登录页面设计展示了 HarmonyOS 5.0(Next)的未来美学理念,结合科技与艺术,为用户带来视觉盛宴。该页面使用 ArkTS 开发,支持个性化定制和无缝智能设备连接。代码解析涵盖了声明式 UI、状态管理、事件处理及路由导航等关键概念,帮助开发者快速上手 HarmonyOS 应用开发。通过这段代码,开发者可以了解如何构建交互式界面并实现跨设备协同工作,推动智能生态的发展。
193 10
鸿蒙登录页面好看的样式设计-HarmonyOS应用开发实战与ArkTS代码解析【HarmonyOS 5.0(Next)】
|
2月前
|
PHP 开发者 容器
PHP命名空间深度解析:避免命名冲突与提升代码组织####
本文深入探讨了PHP中命名空间的概念、用途及最佳实践,揭示其在解决全局命名冲突、提高代码可维护性方面的重要性。通过生动实例和详尽分析,本文将帮助开发者有效利用命名空间来优化大型项目结构,确保代码的清晰与高效。 ####
72 20
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
96 1
|
3月前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
130 2
|
2月前
|
设计模式 存储 安全
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
创建型模式的主要关注点是“怎样创建对象?”,它的主要特点是"将对象的创建与使用分离”。这样可以降低系统的耦合度,使用者不需要关注对象的创建细节。创建型模式分为5种:单例模式、工厂方法模式抽象工厂式、原型模式、建造者模式。
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
|
2月前
|
存储 设计模式 算法
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
行为型模式用于描述程序在运行时复杂的流程控制,即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务,它涉及算法与对象间职责的分配。行为型模式分为类行为模式和对象行为模式,前者采用继承机制来在类间分派行为,后者采用组合或聚合在对象间分配行为。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象行为模式比类行为模式具有更大的灵活性。 行为型模式分为: • 模板方法模式 • 策略模式 • 命令模式 • 职责链模式 • 状态模式 • 观察者模式 • 中介者模式 • 迭代器模式 • 访问者模式 • 备忘录模式 • 解释器模式
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析

热门文章

最新文章

推荐镜像

更多