> 文档中心 > 冒泡排序、插入排序、选择排序

冒泡排序、插入排序、选择排序


冒泡排序、插入排序、选择排序

推荐知乎博客:排序算法之选择排序
十大经典排序算法(动图演示)

冒泡排序

JavaScript代码实现、Python代码实现、Go代码实现、Java代码实现、PHP代码实现、C语言代码实现、C++语言实现、C#语言实现、Ruby语言实现、Swift语言实现

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  • 算法步骤

比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

  • 什么时候最快

当输入的数据已经是正序时

  • 什么时候最慢

当输入的数据是反序时

  • JavaScript代码实现
function bubbleSort(arr) {    var len = arr.length;    for (var i = 0; i < len - 1; i++) { for (var j = 0; j < len - 1 - i; j++) {     if (arr[j] > arr[j+1]) { // 相邻元素两两对比  var temp = arr[j+1]; // 元素交换  arr[j+1] = arr[j];  arr[j] = temp;     } }    }    return arr;}

插入排序

https://www.runoob.com/w3cnote/insertion-sort.html

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

  • 算法步骤

将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

function insertionSort(arr) {    var len = arr.length;    var preIndex, current;    for (v ar i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while(preIndex >= 0 && arr[preIndex] > current) {     arr[preIndex+1] = arr[preIndex];     preIndex--; }

选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

  • 算法步骤

① 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值,若小于第一个数,则交换
② 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值,若小于第二个数,则交换
③ 依次类推下去……

function selectionSort(arr) {    var len = arr.length;    var minIndex, temp;    for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) {     if (arr[j] < arr[minIndex]) {     // 寻找最小的数  minIndex = j;   // 将最小数的索引保存     } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;    }    return arr;}