您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

算法之常见排序算法-冒泡排序、归并排序、快速排序

时间:2019-10-22 10:07:17  来源:  作者:

冒泡排序时间之所以效率低,就是因为将所有数都一视同仁不做区分挨个比较,这是最普通的做事方法,所以效率也是最普通的,时间复杂度为N的平方;而归并排序效率高,则是采用了分治的思想,将一个整体分成多个小份,每个小份排好序之后再互相比较,这样就比冒泡快了不少,时间复杂度为NlogN;快速排序的平均时间复杂度也是NlogN,但是实际的耗费时间会比归并排序快两三倍(当然快排在最坏的情况下时间复杂度还是N的平方,比归并排序大),它的平均执行时间能比归并更快一些是因为它每次分组时不是随机分组而是相对有序的分组,即先从数组中随机取一个数作为基数,然后将数据移动,使得基数一边的数都比它小,另一边的数都比它大,再在两边各取一个基数进行相同的移动、分组操作,递归下去,这样每个细分的小组都在整体的大数组中有个位置,合并时直接按从小到大将各个分组合并起来即可,所以一般情况下会比归并快一些。

了解了思想之后,再用代码实现相对就会容易很多。此处就再借用一个直观一点的例子来说明归并与快排二者的区别。假设有1000个学生,想对他们的成绩进行排序。方法1借用归并排序的思想,具体这样做:将这1000个人分成10组,将每组的100人进行排序,排完之后再在各组之间从小到大依次进行比较,最后得到整个的成绩排名。方法2借用快速排序的思想,具体需这样做:将1000个人也是分成10组,但是是按分数段分,0-10分的放在一组,10-20分的放在一组,20-30分的放在一组,依次类推,分完组之后再在各个小组中进行排序,而当你合并各个小组时,只需将其按从小到大的顺序直接合并就行,无需跟方法1一样将各小组中的数据取出来跟其他小组中的数据挨个比较。看到这里,想必各位道友对快排比归并排序还要快一些的原因就有了解了。

算法可以理解成做事的技巧或者说套路,我们对其的理解可以不止于编程,完全可以推广出去。比如归并的分治法,将一个大事情拆解成多个小事件,解决起来就会方便很多。闲话扯了一大堆,下面就将我自己写的排序给大家贴出来,附带上注释讲解,如果有之前不了解的道友,相信看完之后便会念头通透,原地飞升 >_< 。 正文 [erji]归并排序[/erji]

// 归并排序
 public static void mergeSort (int[] arr) {
 // 建一个临时数据来存放数据
 int[] temp = new int[arr.length];
 mergeSort(arr, 0, arr.length - 1, temp);
 }
 private static void mergeSort(int[] arr, int left, int right, int[] temp) {
 if (left < right) { // 如果起始下标跟结束下标差值小于1,则不进行操作
 int mid = (left + right) / 2;
 mergeSort(arr, left, mid, temp); // 分组,将左边分为一组,递归调用进行排序
 mergeSort(arr, mid+1, right, temp); // 将右边分为一组
 merge(arr, left, mid, right, temp); //将左右分组合并
 }
 }
 private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
 int i = left; // 定义左指针
 int j = mid + 1; // 定义右指针
 int t = 0; // 给temp临时数组用的指针
 while (i <= mid && j <= right) { // 设置左右指针的移动边界
 if (arr[i] <= arr[j]) { // 此处是升序,故谁小谁先赋给临时数组
 temp[t++] = arr[i++];
 } else {
 temp[t++] = arr[j++];
 }
 }
 while (i <= mid) { // 如果左边有剩余,则放在temp中
 temp[t++] = arr[i++];
 }
 while (j <= right) { // 如果右边有剩余,依次放入temp中
 temp[t++] = arr[j++];
 }
 t = 0;
 // 此时temp中已经是arr数组中下标从left到right之间排好序的数据了,因为temp每次都是从0开始赋值,所以需将排好序的数放回arr的对应位置
 while (left <= right) {
 // 将left到right之间排好序的数据放回arr中,此时left到right之间的数就是最终排好序的数
 arr[left++] = temp[t++];
 }
 }

快速排序

// 快速排序
 public static void quickSort (int[] arr, int left, int right) {
 // 先将异常情况处理掉
 if (arr == null || arr.length < 2) {
 return;
 }
 if (right <= left) {
 return;
 }
 if (right - left == 1 && arr[left] <= arr[right]) {
 return;
 }
 // 取第一个数为基准数(基数取哪个都行,此处是为了方便)
 int index = arr[left];
 int i = left + 1; // 左指针
 int j = right; // 右指针
 while (i < j && i < right && j > left) { // 设置指针的移动边界
 while (arr[j] > index && j > left) {j--;} // 找到从右边数第一个比index小的数
 while (arr[i] < index && i < right) {i++;} // 找到从左边数第一个比index大的数
 if (i < j) { // 交换这两个数 如果i == j,说明二者定位到了同一个位置,则不用交换;如果i > j,说明二者已经相遇然后背向而行了,也不交换
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 }
 // 执行完上面循环后,arr已经是左边比index小,右边比index大的数组了,只是基准数仍在基准位置left处,需放到它应该在的位置
 if (j != left && arr[j] != arr[left]) {
 // j最后停留位置的数,肯定是一个小于等于index的值,所以如果不是同一个位置的话,直接将二者调换一下位置即可
 int temp = arr[j];
 arr[j] = arr[left];
 arr[left] = temp;
 }
 quickSort(arr, left, j-1); // 将基准数左边排序
 quickSort(arr, j+1, right); // 将基准数右边排序
 }


Tags:排序算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 排序算法  点击:(16)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 排序算法  点击:(40)  评论:(0)  加入收藏
1. 插入排序步骤:1.从第一个元素开始,该元素可以认为已经被排序2.取下一个元素tem,从已排序的元素序列从后往前扫描3.如果该元素大于tem,则将该元素移到下一位4.重复步骤3,直到找...【详细内容】
2021-08-19  Tags: 排序算法  点击:(100)  评论:(0)  加入收藏
人生有涯,学海无涯今天跟大家分享一个常用的排序算法&mdash;&mdash;快速排序。我想大家在日常的工作或者面试的时候肯定经常会遇到很多排序算法,而且快速排序算法往往是这里面...【详细内容】
2021-03-04  Tags: 排序算法  点击:(182)  评论:(0)  加入收藏
1. 冒泡排序算法实现(javascript)//冒泡排序算法(javascript)//author:Hengda//arr数组//mode false 升序 ture 降序function bubbleSort( arr, mode ){ var i, j, temp, l...【详细内容】
2021-02-07  Tags: 排序算法  点击:(220)  评论:(0)  加入收藏
用希尔排序法对一组数据由小到大进行排序,数据分别为 69、56、12、136、3、55、46、 99、88、25。例子:(1)自定义函数 shsort(),实现希尔排序。(2) main() 函数作为程序的入口...【详细内容】
2021-01-25  Tags: 排序算法  点击:(216)  评论:(0)  加入收藏
选择排序 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续...【详细内容】
2020-11-19  Tags: 排序算法  点击:(173)  评论:(0)  加入收藏
今天我们就来讨论面试官最喜欢问到的排序算法吧,从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手,彻底搞清实现原理,保证面试道路一路畅通。0...【详细内容】
2020-07-26  Tags: 排序算法  点击:(97)  评论:(0)  加入收藏
今天我们就来讨论面试官最喜欢问到的排序算法吧,从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手,彻底搞清实现原理,保证面试道路一路畅通。01...【详细内容】
2020-07-25  Tags: 排序算法  点击:(62)  评论:(0)  加入收藏
1 插入排序算法定义插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好...【详细内容】
2020-06-30  Tags: 排序算法  点击:(55)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条