冒泡排序算是排序算法里面的一种较为简单的算法,也是我接触的第一种排序算法,有升序与降序之分,如果面试的时候面试官问道这个题目,一定要问清楚是升序还是降序,这样会给你加分。 下面,我以升序来讲一下它的运作。   1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 3、针对所有的元...

插入排序原理很简单,讲一组数据分成两组,我分别将其称为有序组与待插入组。每次从待插入组中取出一个元素,与有序组的元素进行比较,并找到合适的位置,将该元素插到有序组当中。就这样,每次插入一个元素,有序组增加,待插入组减少。直到待插入组元素个数为0。当然,插入过程中涉及到了元素的移动。   为了排序方便,我们一般将数据第一个元素视为有序组,其他均为待插入组。   下面以升序为例进行...

选择类排序算法 1、选择排序算法 思想:首先找到数组中最小的那个元素,其次将它和数组中的第一个元素交换(如果第一个元素是最小的,那么和它自己进行交换)。再次,再剩下的元素中找到最小的元素,将它与数组中的第二个元素进行位置交换。如此往复,直到整个数组排序。这就叫选择排序。 时间复杂度 o(n*n) 模板: 测试结果 2、堆排序算法   堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择...

基础算法:希尔排序

算法  排序  希尔排序

  

2019-06-07 16:20:06

希尔排序,也称递减增量排序算法,1959年Shell发明。是插入排序的一种高速而稳定的改进版本。 希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。 1、基本思想 (1)设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子...

排序算法:堆排序

排序算法  堆排序

  

2019-06-12 10:17:09

在介绍堆排序之前,首先需要说明一下,堆是个什么玩意儿。 堆是一棵顺序存储的完全二叉树。 其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆。 其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆。 举例来说,对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时,称之为堆: (1) Ri <= R2i+1 且 Ri <=...

快速排序是一种交换排序。 快速排序由C. A. R. Hoare在1962年提出。 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分:分割点左边都是比它小的数,右边都是比它大的数。 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 详细的图解往往比大堆的文字更有说明力,所以直接上图: 上图中,演示了快速排序的处理过程: 初始状态为一...

简介 我们通常所说的排序算法往往指的是内部排序算法,即数据记录在内存中进行排序。 排序算法大体可分为两种: 比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。 非比较排序,时间复杂度可以达到O(n),主要有:计数排序,基数排序,桶排序等。 如下图   有一点我们很容易忽略的是排序算法的稳定性(腾讯校招2016笔试题曾考过)。...

经典排序算法总结与实现 经典排序算法在面试中占有很大的比重,也是基础,为了未雨绸缪,在寒假里整理并用Python实现了七大经典排序算法,包括冒泡排序,插入排序,选择排序,希尔排序,归并排序,快速排序,堆排序。希望能帮助到有需要的同学。之所以用Python实现,主要是因为它更接近伪代码,能用更少的代码实现算法,更利于理解。 本篇博客所有排序实现均默认从小到大。 一、冒泡排序BubbleSort 介绍...

快速排序: 是对起泡排序的一种改进。 基本思想: 通过一次排序将序列分割成两个部分,一部分都比关键字大,一部分都比关键字小,进而继续对这两个子序列进行相同的操作。(通过递归) 具体做法:每次可以将第一个元素设置为“分割元素temp”,附设两个指针,分别指向序列的头low和尾high。首先从high所指的位置向前查找第一个小于temp的元素与low所指的元素进行交换,然后从l...

快速排序

快速排序

  

2019-06-07 10:10:07

转自:http://developer.51cto.com/art/201403/430986.htm 高快省的排序算法 有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。 假设我们现在对“6  1  2 7  9  3  4  5 10  8...

前言 博主今天跟大家聊一聊睡眠排序,皮一下很开心! 没听过睡眠排序?不要觉得丢脸,我也是刚知道的! 说起排序,大家肯定只知道快排,冒泡排序等!然而今天看到一种睡眠排序,简直是颠覆三观,毁天灭地,确实是达到排序的目的了!而且思路清奇,着实可以拿出来分享分享! 睡眠排序 假设,入参是一个乱序的数组! 那如何进行排序输出呢?步骤如下: step1 循环数组 step2 取出整数20,将整数传入线程,ne...

归并排序和希尔排序

排序算法

  

2019-06-11 23:22:42

1  归并排序 归并排序是一种分治算法,把大的问题分成一个个小部分去处理,最终解决大问题。  假设有两个数组A,B,每个数组都是从小到大排好序的,如果要将这两个数组合并成一个数组,并且从小到大排好序 那么只需要从头比较,依次将A,B中较小的值放入新的数组。 对于一个无序的数组,也可以通过这种方法排序,将数组从中间分成2部分,但是大概率是两个无序数组,然后接着对 分开的...