首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

【图解面试基础】三种基本排序算法

冒泡排序、选择排序和插入排序三种基本排序算法。...其原理是相通的: 将数组划分成前后两个子集:{[order-list], [unorder-list]},前面是有序集,后面是无序集 三种方法都是线性的一次从无序集中搬一个元素到有序集中,只不过搬法不同...三种排序的复杂度都是 O(n^2)。 冒泡排序 S-order <--bubble-- S-unorder 像冒泡一样,每次让最小的数冒出剩余数据集(无序)“水面”,抵达有序集。...选择排序 S-order <--selection-- S-unorder 从剩余数据集(无序)中选择最值,放到有序集中。 口诀: 数组分两块,初始前空置; 后面选极前追加,前满后空则终止。...插入排序 S-order <--insertion-- S-unorder 从剩余数据集(无序)中随意取一个值,然后通过比较“插入”(也可以理解为往前冒泡)到有序集中。

16120

–冒泡排序三种实现(Java)

冒泡排序是非常好理解的,以从小到大排序为例,每一轮排序就找出未排序序列中最大值放在最后。 设数组的长度为N: (1)比较前后相邻的二个数据,如果前面数据大于后面的数据,就将这二个数据交换。...以上就是冒泡排序基本思想,按照这个定义很快就能写出代码: /** * 冒泡排序的第一种实现, 没有任何优化 * @param a * @param n */ public static void bubbleSort1...如果是对于上面的冒泡排序算法2来说,虽然也只排序100次,但是前面的100次排序每次都要对后面的900个数据进行比较,而对于现在的排序算法3,只需要有一次比较后面的900个数据,之后就会设置尾边界,保证后面的...900个数据不再被排序。...https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/BubbleSort.java

18210
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    三种排序方式

    }; System.out.println("冒泡排序后数据为"); bubble(arr); list(arr); System.out.println();...给你一个串数字,根据冒泡排序的方法演示就是这样的 假如有这样的数字11,4,7,2,55,9。...选择排序 选择排序,就是先拿出一个数,假设是最小的数,一个一个的跟后面的数进行比较。找到最小的数,由于是在数组中操作的。...插入法排序 插入法排序,先让两个数进行排序,当第三个数进来时,只需要跟第二个数比较,当它大于最二个数是,直接插入这个数的后面。当它小于第二个数时,依次跟前两个数比较。...总的来说,后面两种方法都是根据冒泡排序方法延伸而来,主要是考虑到效率问题,后面的方法相对于冒泡来说依次少比较了很多次。

    32510

    基本排序算法

    o(n^2)级别排序算法 为什么要学习O(n^2)的排序方法?...● 基础 ● 编码简单,易于实现,是一些简单情景的首选 ● 在一些特殊情况下,简单的排序算法更有效 ● 简单的排序算法思想衍生出复杂的排序算法 ● 作为子过程,改进更复杂的排序算法 1.选择排序...Selection Sort 每次选择没有排序部分的最小值和第一位交换 def selection_sort(org_arr, length): """ 选择排序,每次选择未排序部分的最小值和未排序部分的第一位交换位置...:当找到合适的位置以后(arr[j-1] > e),可以提前终止内层循环 这使得在一个近乎有序的数组在进行插入排序的时候,效率要高的多,设置比o(logn)的算法效率还要高 当排序一个完全排序的数组时...,插入排序的算法复杂度为o(n)级别

    31420

    基本排序算法总结

    以下算法参考《算法(第四版)》 ---- 冒泡排序 最好情况(加了标记辅助的)时间复杂度O(n) 平均情况O(n*n) 最坏情况O(n*n) import java.io.BufferedReader;...,只是一个教学版本,但至少得掌握吧 插入排序 时间复杂度最好情况是O(n) 最坏和平均情况是O(n*n) import java.io.BufferedReader; import java.io.IOException...import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public...java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Random...堆排序: 下沉排序(数值大的下沉,这样就是升序,如果数值小的下沉,那么就是降序) 最好最坏平均时间复杂度都为O(nlogn),空间复杂度为O(1) 升序代码: import java.io.BufferedReader

    23710

    python基本排序算法

    以此类推,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 #!...也就是说排序以后还是这样的[1,1,1,1,1,1,1] 三、插入排序 插入排序是一种简单直观且稳定的排序算法。...如果有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序基本操作就是将一个数据插入到已经排好序的有序数据中...在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。   插入排序基本思想是:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。 #!...main__': li = [9, 0, -1, 46, -87, 7, 17, 20, 2] print(merge_sort(li)) 最近搞了一个个人公众号,会每天更新一篇原创博文,java

    38520

    ------排序----基本内容

    2.1 插入排序 2.1.1基本思想: 直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列...希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。...2.2 选择排序 2.2.1基本思想: 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。...稳定性:稳定 2.3.2 快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列...稳定性:不稳定 2.4 归并排序 基本思想: 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用

    5210

    三种python 列表排序方法

    本文将讨论的是,如何将一个字符串组成的列表,比如 'abc','cba','bac' ,按照特定的条件(比如首字母、尾字母、或者长度)灵活的排序?...目录 直接排序 由一些字符串组成的 list ,sort( )方法可以直接用来对字符串排序: a = "John Smith", "Alice Young", "John Scott Brown"...a.sort() a 'Alice Young', 'John Scott Brown', 'John Smith' 注意,这里 sort 方法是原位排序(in-place sort),也就是直接更改了原对象...按其中一部分排序 在上面的例子里,如果我想按照空格后面的姓排序,该怎么写?sort 方法有一个可选参数key,接收一个函数,这个函数将待排序的对象重新处理后,作为新的排序依据,传给 sort。...按长度排序 key 也可以定义为内置函数,比如 len a = "John Smith", "Alice Young", "John Scott Brown" a.sort(key=len) a

    82820

    排序篇】实现快速排序三种方法

    1 交换排序 基本思想:所谓交换,就是根据序列中的两个记录键位的比较结果来交换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。...1.1 冒泡排序 冒泡排序的特点就是,从前到后两两比较找到最大的数放在数组的末尾。...因为已经找到数组最大元素并放置在末尾,也就是说最大元素已经放置在最终的位置,我们接下来就是把末尾提前来来一次找到数组中次大的元素,以此类推将数组彻底排序。...: 冒泡排序是一种非常容易理解的排序 时间复杂度:O(N^2) 空间复杂度:O(1) 稳定性:稳定 1.2 快速排序 快速排序是Hoare在1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序的元素序列中的某元素作为基准...,按照该排序码将待排序序集分割成两子序列,左子序列中所有元素均小于其基准值,右子序列中的所有元素均大于基准值,然后左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

    8010

    java冒泡排序代码_Java冒泡排序

    一、冒泡排序: 利用冒泡排序对数组进行排序 二、基本概念: 依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。...四、java代码实现: package 冒泡排序; import java.util.Arrays; /** * 冒泡排序 * @author chen * */ public class BubbleSort...六、算法优化: 冒泡排序法存在的不足及改进方法: 第一,在排序过程中,执行完最后的排序后,虽然数据已全部排序完备,但程序无法判断是否完成排序,为了解决这一不足,可设置一个标志位flag,将其初始值设置为非...在新一轮排序开始时,检查此标志,若此标志为0,表示上一次没有做过交换数据,则结束排序;否则进行排序; package 冒泡排序; import java.util.Arrays; /** * 冒泡排序改进版...由于局部冒泡排序和冒泡排序的数据移动次数总是相同的,而局部冒泡排序所需关键字的比较次数常少于冒泡排序,这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进,当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销

    1.9K61

    基本排序算法(冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序

    项目地址:https://github.com/windwant/windwant-service/tree/master/algorithm 冒泡排序:两两比较,大数冒泡 升序: public static...选择排序:选择剩余元素中最小(最大)的元素放置到初始选择集合中(空) public static void SelectionSortAsc(int[] arr){ int min = 0;...:设定一个初始已排序的集合(一般选择一个元素),从剩余的集合中将各个元素以此插入到初始集合中的正确位置 public static void insertionSort(int [] array){...左边的元素值都小于anchor值,右边的值都大于anchor值,递归排序左右两侧排序 //左边元素。...值索引+1---high if (end < high) { quikeSort(arr, end + 1, high); } } 归并排序

    70620

    漫画:三种 “奇葩” 的排序算法

    在算法的世界里,有许多高效率的排序算法,比如快速排序、归并排序、桶排序......它们大大提高了程序的性能。 但是,也有一些比较奇葩的排序算法,它们既不能做到高效率,也没有很好的可读性。...下面,让我们来介绍三种“异想天开”的排序算法。 1.睡眠排序 ? ? ————— 第二天 ————— ? ? ? ?...2.猴子排序 ? ? ? 或许这样说比较抽象,让我们来演示一下: ? ? ? 3.珠排序 ? ? ? 见过算盘的人都知道,算盘上有许多圆圆的珠子被串在细杆上,就像下面这样: ?...那么,我们可不可以模拟珠子下落的原理,对一组正整数进行排序呢?答案是可以的。 我们可以用二维数组来模拟算盘,有珠子的位置设为1,没有珠子的位置设为0。

    55730

    java链表排序方法_java链表排序

    插入排序 对链表进行插入排序,是最简单的一种链表排序算法,用于插入排序是迭代的,所以每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。...每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。重复直到所有输入数据插入完为止。...对于归并排序排序在数组排序中的运用,详细请点击此处。...这里主要介绍归并排序在链表排序中的运用。...在使用归并排序算法进行链表排序时,其基本思想是将链表细分成一个个子链表,将子链表进行排序,然后再将相邻的两个有序子链表进行合并,得到更长的有序链表,最后一步步得到整个有序链表,子链表进行合并排序时需要用到合并两个有序链表算法

    98510

    Python3 基本排序算法之冒泡排序

    基本排序算法按时间复杂度分类   O(n^2)   冒泡排序   插入排序   选择排序   Q(n log n)   分而治之   快速排序   归并排序   冒泡排序   相邻的两个元素对比,大的数后推...简易版冒泡排序示例如下   def bubble(sl):   """   冒泡排序,O(n^2)   相邻的两个元素对比,大的后推,遍历整个列表一次后,将最大项以冒泡的方式排列到列表末尾   :param...  def bubble_sort(items):   """   冒泡排序, 还是将while循环换为for循环比较习惯   最好 O(n)   最坏 O(n^2)   """   items_len...True   items[j - 1], items[j] = items[j], items[j - 1]   if not has_swap:   break   return items   插入排序...def insert_sort_for(items):   """   插入排序,for循环, 中间还是使用while循环容易理解:   比插入的值 大的数挪后,直到不需要挪动为止即为插入的位置。

    31020

    快速排序Java实现_快速排序实现java

    高快省的排序算法 有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。...最终将会得到这样的序列,如下 1 2 3 4 5 6 7 8 9 10 到此,排序完全结束。...细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。 这是为什么呢?...快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。...因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想,到时候再聊。

    1.4K10

    java冒泡排序经典代码_java冒泡排序

    经典算法——冒泡排序(Bubble Sort) 一、示例代码(伸手党看这里) 1.示例一 importjava.util.Arrays;public classBubbleSort {public static...int temp; /*临时变量,交换数据时使用*/ int length =arr.length;for(int p = length-1; p > 0; p–){ /*需要进行N-1(数组长度减一)趟排序...*/ for(int i = 0; i arr[i+1]){//进行位置交换 temp =arr[i]; arr[i]= arr[i+1...在使用冒泡排序的时候有可能会遇到这样一种情况:某一趟排序从头到尾,数组中的数字都没有发生位置交换。 那么上面这种情况说明了什么呢?说明了在经过上一趟的排序后,整个数组就已经被排好序了。...这么说的话原来计划的N-1趟排序我们是不是可以不用跑满了?是的!

    76720
    领券