热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Datastructure(七大排序算法)

我们日常生活中,很多地方都需要使用排序方法,比如你逛淘宝,天猫👇👇👇👇&#

    我们日常生活中,很多地方都需要使用排序方法,比如你逛淘宝,天猫👇👇👇👇👇👇

    你想要买一些便宜的或者贵的,或者性价比比较高的,都可以按照你的需求给你排列出来,这么多种物品, 总有一款是适合你的~~~这里就使用到了排序算法👇 👇👇👇👇👇👇👇👇👇👇👇👇👇👇。介绍数据结构中几种比较常用的排序方法~~~

目录

1.插入排序

    Notice:

🎄希尔排序

✨introduce:

   ✨ Analyze:

🎋插排希尔性能对比

🎄堆排序

 🎋堆排性能对比

🎄冒泡排序

  🎋冒泡性能对比度

🎄选择排序

🎋选择排序性能对比

🎄快速排序

 🎋快排递归版本

🎋挖坑法

🎋双指针法

 🎋 快排非递归版本

🎋快排性能对比

🎄归并排序

⭐ 算法思想:

 ✨性能对比




csdn主页



1.插入排序

    插入排序思想比较简单,在我个人看来插入排序和冒泡排序有一点相似,但是他们说这两个排序思想根本不是一回事~~~~插入排序的思想和日常生活中大家玩的扑克牌的思想就很相似,你揭的第一张牌默认为有序,再来的扑克你分一下是比第一张牌大or小你就放在一个合适的位置~~~~~~

我们通过动图来了解插入排序的思想👇👇👇👇👇

通过上面这样子,乱序数组就会被安排在有序的位置里了~~~~再来看一下代码实现👇 👇👇👇👇👇

void Insert(int* arr, int n)
{//总体需要拍的数据,我们假设是最坏的情况,里面的每一个//数据都是需要被调整的~int i = 0;for (i = 0; i = 0){//开始判断排序if (x }

 

 这样依次递归下去


    Notice:

    我们会注意到无论哪种算法,它们排序的天花板就是0(n),因为基本条件就是需要把整个数组遍历一下,上面的插入排序我们可以发现,它的最佳情况就是o(n),最糟糕的情况是o(n^2)的了,假设数组降序排为升序~~~~~~~


🎄希尔排序


✨introduce:

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:


  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

    希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。我们来看一下动图吧👇

👇👇👇👇👇👇👇

   希尔排序是根据插入排序进行优化的,我们前面已将提到,如果插入排序情况比较好的情况下,就是有的数字不需要处理,那么复杂度可能会降到o(n),那么希尔的思想就是,我可不可先将它大致整理一下再进行排序呢?

 我们先将这几个数组,每隔3个取一个数据将他们进行预排序~~那么它们使用插入排序的方式排完之后就是这个样子👇👇👇👇👇👇👇👇

可以看出它比第一次有序了,最小的和最大的分别都到了相应的位置~~~~~再次进行预排序~~~

那么这次的预排序我们就不在使用已经排好的数据了👇 👇 👇 👇 👇 👇 👇 

这次我们选择了相比第一次后一个位置数字进行预排序,那么这几个数字排完是这个样子👇👇👇👇👇👇👇👇

又比之前好了一些,我们再来一次👇 👇👇👇👇👇👇

这次排完已经很接近有序了,但是还是在需要进行依次插排,数据才会被排序好~~再进行一次插排的话加上我们之前的三次预排序我们一共处理了四次,好像原来越接近普通插入排序了~~~~~~我们来看一下代码实现👇 👇 👇 👇 👇 👇 👇 👇 👇 

int gap=3;
for (i = 0; i = 0){if (x

 这是第一次预排序,后面两次预排序我们emit..........

整体代码实现👇👇👇👇👇👇👇👇👇👇👇👇👇👇

void Shellsort(int* arr, int n)
{int gap = n;int end = 0;int i = 0;while (gap > 1){gap /= 3;for (i = 0; i = 0){if (x

 我们第一次使gap=gap/2=5,其实即是将数字两两分开进行预排👇👇👇👇👇👇👇👇👇

👇

     排完之后是这个样子~~这次是整体变化比较大。我们再使gap=gap/4=2;就可以得到更接近插入排序的~~这个希尔排序大致思想就是这样,比较不容易理解~~


   ✨ Analyze:

    时间复杂度最坏情况下还是o(n^2);😅,最好情况下则为o(n)。技术牛们说希尔排序平均下来复杂度在o(n^1.3)不知道从哪里的得到的结论~~


🎋插排希尔性能对比

    我们创建一组数据进行插入和希尔的性能比较👇👇👇👇👇👇👇


void test()
{srand(time(0));const int N = 100000;int* a1 = new int[N];int* a2 = new int[N];int* a3 = new int[N];int* a4 = new int[N];int* a5 = new int[N];int* a6 = new int[N];//int* a7 = new int[N];for (int i = 0; i }

我们得到的结果是我们排列100000个数据插排耗费3.67s。而希尔排序只耗费0.015s.我们只是得到了结论,希尔排序是一种比较稳定的排序方法,而且希尔这人也是真的厉害。这都能想到~~


🎄堆排序

    堆排序是指利用堆积树,这种数据结构所设计的一种排序算法,属于选择排序的一种。它是通过堆来进行数据选择,需要注意的是排升序需要建大堆,排降序需要建小堆~~👇👇👇👇👇👇👇👇👇我们演示一个排序升序的堆排~~~

void Heapsort(int* a, int n)
{for (int i = (n-2)/2; i >= 0; i--){AdjustDown(a, n, i);}for (int i = 0; i

因为我们需要建一个大堆,之前的插入已经不行了,比如这样的👇👇👇👇

 所以我们就需要从下往上面调~~这样就可以把它搞成一个大堆~~大堆建立完之后,就开始我们的堆排👇👇👇👇

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child }
void Heapsort(int* a, int n)
{这里需要从下向上把堆建成大根堆for (int i = (n-2)/2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){//与堆顶元素进行互换~~Swap(&a[0], &a[end]);//然后将堆顶的元素往下调,注意这里调不到原来的位置,相当于删除~~AdjustDown(a, end, 0);//依次向上遍历~·end--;}
}

 🎋堆排性能对比

 可以看出堆排和希尔排序还是在一个级别的~


  • 堆排时间复杂度为o(N*logN),建堆时间复杂度为o(n);
  • 空间复杂度为o(1);
  • 堆排稳定性不好i~~

🎄冒泡排序

    冒泡排序是非常稳定的排序方式,而且比较容易理解👇👇👇👇👇👇

void Bubblesort(int* a, int n)
{int i = 0;for (i = 0; i }

  🎋冒泡性能对比度


  •  冒泡排序很容易理解,也很稳定,属实有些慢了基本上都是o(N^2);
  • 最坏情况为o(N^2),最好的为o(N)~~~

🎄选择排序

    选择排序思想较为简单,就是打擂台的方法,选出最大或者最小的数字,然后排列称为升序或者降序只不过这次的选择排序,一次选出了最大数和最小数,相当于是量变~~👇👇👇👇👇👇👇、

    标记起始位置和最后的位置,让最大的和end交换,最小的和begin交换。这里面的一个小bug是如果最大值在第一位,那么最大值就会先被换走。就是上面这种情况,那么我们就需要稍微做一下处理~~~~👇👇👇👇👇

int begin = 0, end = n-1;while(begin a[maxi]){maxi = i;}if (a[i]

🎋选择排序性能对比

 论效率来说还是堆排和希尔是比较快的~~


🎄快速排序


       快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止~~快速排序有一些比较难以理解~我们观察一下👇👇👇👇👇👇👇

查看源图像

 🎋快排递归版本

我们先演示一趟单趟的~~👇👇👇👇👇👇👇

✨Noitice :如果keyi给的是左边的值,就需要先从右边开始查找~~~~

                      如果keyi给的是右边的值,就需要从左边的值开始进行查找~

                       这里还需要注意一些小bug,就是越界的情况~~~~

int Partion(int* a, int left, int right)
{int keyi = left;while (left = a[keyi]){right--;}//从左边开始,找比keyi大的数,while (left}

     完成这个快速排序是需要我们对它进行分区间的,也就是分治问题, 将它分为以keyi隔开的区间,逐个进行排序,这里就使用到了递归来进行~~👇👇👇👇👇👇👇👇👇👇

 我们来看一下代码实现~~其实也还好👇👇👇👇👇👇

int Partion(int* a, int left, int right)
{int keyi = left;while (left = a[keyi]){right--;}//从左边开始,找比keyi大的数,while (left}void Quicksort(int* a, int left, int right)
{//左边==右边就说明递归完了,就返回~~if (left >= right){return;}int keyi = Partion(a, left, right);Quicksort(a, left, keyi - 1);Quicksort(a, keyi + 1, right);
}

 Summary:递归版本省事比较简单,但是有时候递归太多就容易栈溢出,


🎋挖坑法

      挖坑法就是在原来的基础上进行了改进~先设置一个坑位,先让右边的走,找到小的就停止,然后把值给到坑位。让right变成新的坑位,再让左边走,和右边类似,注意最后跳出循环,需要让最后的坑位等于key值然后返回坑位~

int Partionpit(int* a, int left, int right)
{int key = a[left];//设置的坑位int pit = left;while (left = key){right--;}a[pit] = a[right];pit = right;while (left }

🎋双指针法

    

int Partoinpointer(int* a, int left, int right)
{ //两个指针int key = left;int slow = left, fast = left +1;while (fast }void Quicksort(int* a, int left, int right)
{if (left >= right){return;}int keyi = Partoinpointer(a, left, right);Quicksort(a, left, keyi - 1);Quicksort(a, keyi + 1, right);
}

 

选key的两种情况~~ 


 🎋 快排非递归版本

    快排的递归版本我们可以想到, 但是递归的缺点就是递归的太深,容易栈溢出,如果是一组比较有序的数组,递归版本就会进行的很深~~快排非递归版本是使用到栈的思想来进行👇👇👇👇👇

void QuickSortNonR(int* a, int left, int right)
{stack st;st.push(left);st.push(right);while (!st.empty()){//开始取栈内元素int end = st.top();st.pop();int begin = st.top();st.pop();int keyi = Partionpit(a, begin, end);//处理过之后区间被分为[begin,key-1],keyi,[keyi+1,end];//被分为两个区间的选择先入右边,这样就会先处理左边~//判断是区间是否还有,有的话就继续入,或者相等就入了~~if (keyi + 1 }

 


🎋快排性能对比

    

 在相对效率都较高的情况,快排还是非常稳定的~~


🎄归并排序

    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:


  • 自上而下的递归(所有递归的方法都可以用迭代重写);

⭐ 算法思想:


  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

  4. 重复步骤 3 直到某一指针达到序列尾;

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

动图演示:

     

     归并排序就是将区间细分,分治来达成目的~~

👇👇👇👇👇👇👇👇👇👇

    

void _Mergesort(int*a,int left,int right,int*tmp)
{//递归到最后一个子区间就返回&#xff0c;在返回过程中完成归并~~if (left >&#61; right){return;}int mid &#61; (left &#43; right) / 2;_Mergesort(a, left, mid, tmp);_Mergesort(a, mid &#43; 1, right, tmp);int begin1 &#61; left, end1 &#61; mid, begin2 &#61; mid &#43; 1, end2 &#61; right;int i &#61; left;while (begin1 <&#61; end1 && begin2 <&#61; end2){if (a[begin1] }void Mergesort(int *a,int n)
{int* tmp &#61; new int[n];_Mergesort(a, 0, n - 1, tmp);delete[]tmp;tmp &#61; nullptr;
}

 ✨性能对比

    

 

     最稳定的还是希尔和归并~~·

&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;


推荐阅读
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文详细解析了Python中的os和sys模块,介绍了它们的功能、常用方法及其在实际编程中的应用。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 深入解析JVM垃圾收集器
    本文基于《深入理解Java虚拟机:JVM高级特性与最佳实践》第二版,详细探讨了JVM中不同类型的垃圾收集器及其工作原理。通过介绍各种垃圾收集器的特性和应用场景,帮助读者更好地理解和优化JVM内存管理。 ... [详细]
  • Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]
  • 本文探讨了Hive中内部表和外部表的区别及其在HDFS上的路径映射,详细解释了两者的创建、加载及删除操作,并提供了查看表详细信息的方法。通过对比这两种表类型,帮助读者理解如何更好地管理和保护数据。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • ImmutableX Poised to Pioneer Web3 Gaming Revolution
    ImmutableX is set to spearhead the evolution of Web3 gaming, with its innovative technologies and strategic partnerships driving significant advancements in the industry. ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 掌握远程执行Linux脚本和命令的技巧
    本文将详细介绍如何利用Python的Paramiko库实现远程执行Linux脚本和命令,帮助读者快速掌握这一实用技能。通过具体的示例和详尽的解释,让初学者也能轻松上手。 ... [详细]
author-avatar
mobiledu2502874455
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有