导航
冒泡排序是一种交换排序，基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
———— 动图来自《菜鸟教程》
说明：绿色表示当前正在比较的两个相邻元素；橘黄色表示已排完序的元素，不再参与后续的比较
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 相邻两两比较，每轮过后从后往前确定一个排好序数字，所以外层for(len-1)，内层(len - i - 1)
function myBubbleSort(arr) {
for (var i = 0; i < arr.length - 1; i++) { // 趟数
for (var j = 0; j < arr.length - 1 - i; j++) { // 当前趟要比较的次数
if (arr[j] > arr[j+1]) { // 相邻元素两两比较
var temp = arr[j]; // 元素交换
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
代码与图片配合食用更加~
// 改进冒泡排序
function bubbleSort1(arr) {
let i = arr.length - 1;
while (i > 0) {
let pos = 0;
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
pos = j;
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
i = pos;
}
return arr
}
根据上述代码，我们每一轮冒泡需要的结果就是把最大的数通过冒泡放到最后，
然后缩小下一轮需要冒泡的数组的范围（未优化的方案中数组范围只缩小了一位），
但是实际上我们每一轮冒泡后可能会出现后面的几个数都有序的情况，
这个时候我们完全可以再缩小一点下一次需要冒泡的数组的范围
（不然下一轮冒泡到最后发现最大的数本来就在最后，此次冒泡就是多余的）。那怎么确定这个i值呢？
举个栗子：
[a[0],...,a[j],a[j+1],...,a[i]]
如果某一次冒泡比较中a[j]>a[j+1]
交换两值，此时a[j+1]大于a[0]到a[j]的任何值（a[0]到a[j]还是无序的）
如果再接下来的冒泡中满足a[j+1]到a[i]有序，即不做任何交换操作（a[j]和a[j+1]是最后一次交换操作）
那我们下一轮只需要对a[0]到a[j]的无序数组进行冒泡排序，j就是下一轮循环的i值
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function mySelectionSort(arr) {
// 每轮确定从前往后确定一个排好序数字，所以for循环外层(len-1)，内层不减（最后一个数字始终会比较）
for (var i = 0; i < arr.length - 1; i++) { // 第 i 轮选择
var minIndex = i; // 每轮开始假设起始元素为最小值
for (var j = i + 1; j < arr.length; j++) { // 遍历剩余未排序元素
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
var temp = arr[i]; // 交换起始元素与真正的最小值
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
配图：
插入排序的原理应该是最容易理解的，因为只要你打过扑克牌就应该能秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function insertionSortHand(cards) {
// 模拟抓牌的过程
for (let currentIdx = 1; currentIdx < cards.length; currentIdx++) {
let currentCard = cards[currentIdx]; // 当前抓到的牌
let preIdx = currentIdx - 1; // 当前牌的前一张牌
// 逐个比较手里的牌，找到合适的插入位置
while (preIdx >= 0 && cards[preIdx] > currentCard) {
// 如果手里的牌比抓到的牌大，就把这张牌向后移
cards[preIdx + 1] = cards[preIdx];
preIdx--;
}
// 抓到的牌插入到合适的位置
cards[preIdx + 1] = currentCard;
}
return cards; // 返回排好序的牌
}
console.log(insertionSortHand(arr));
假设有一个牌堆 [3, 44, 38, 5]，你想把它们排好序。
抓到 3，第一张牌，默认已经排好序了。
抓到 44，跟 3 比较，44 > 3，所以不用动，继续下一张。
抓到 38，跟 44 比较，38 < 44，所以把 44 往后挪一格，38 插到 3 后面。
结果变成 [3, 38, 44, 5]。
抓到 5，跟 44 比较，5 < 44，把 44 往后移。
跟 38 比较，5 < 38，把 38 也往后移。
跟 3 比较，5 > 3，所以 5 插到 3 后面。
结果变成 [3, 5, 38, 44]。
这样一步一步，你就把所有牌排好序了。
// 例如for循环中 i 等于 2 时，已排序完毕的元素为[3,44]，进入for循环
// 待插入元素为 arr[2]，也就是38;
// j=i-1也就是2-1等于1
// while循环比较，待插入元素38是小于arr[j]（j=1）44 的 => 条件成立
// arr[j+1]要等于arr[j] => arr[2]要等于arr[1] => arr[2]=44 => 此刻数组前三个元素：[3,44,44]
// j-- => j=1-1也就是0
// 再来一轮while比较，待插入元素38现在不小于arr[j] 也就是arr[0]的3，所以直接退出while循环
// arr[j+1]=insertItem => arr[1]=38 => 数组前三排序完毕：[3,38,44]
希尔排序也是一种插入排序，它是简单插入排序的一个改进版，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
在此我们选择增量 gap=数组长度length/2，缩小增量继续以 gap = gap/2 的方式，这种增量选择我们可以用一个序列来表示：{n/2,(n/2)/2...1}，称为增量序列。当然，希尔排序的增量序列有很多种，这里采用的是比较常用的一种作为示例：
在上面这幅图中：
初始时，有一个大小为 10 的无序序列。
在第一趟排序中，我们设 gap1 = 10 / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
注意：图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法。
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function myShellSort(arr) {
var gap = Math.floor(arr.length / 2);
while (1 <= gap) {
// 把距离为 gap 的元素编为一个组，扫描所有组
for (var i = gap; i < arr.length; i++) {
var j = 0;
var temp = arr[i];
// 对距离为 gap 的元素组进行排序
for (j = i - gap; j >= 0 && temp < arr[j]; j = j - gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
console.log(`gap = ${gap}`);
console.log(arr);
gap = Math.floor(gap / 2); // 减小增量
}
return arr;
}
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
可以看到这种结构很像一棵完全二叉树，下面的归并排序代码将会采用递归去实现（你也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
图片来自博客《图解排序算法之归并排序》
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if (len < 2) return arr;
var middle = parseInt(len / 2), // 将未排序数组拆分成两半分而治之
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length && right.length) {
// 两边的起始元素相互比较，始终将小的一方的头元素弹出，并push到准备好的容器result中
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的元素均比另一部分记录的元素小，继而再分别对这两部分记录递归的进行同样的排序操作。
首先把未排序数组的第一个（最左边）元素设置为基准，把它的位置叫做 l ：
然后依次向后查看所有元素，在查看过程中，不断的调整后面元素的位置，使得后面的元素分为两部分，一部分都小于 v ；一部分都大于 v 。
我们用 j 来不断记录这两部分的分割线位置。而 e 就是我们要判断的下一个元素，用索引 i 来表示，i 会遍历每一个元素，来看该如何调整这个元素。
在下图中，我们用 arr[l+1 ... j] 来表示小于 v 的橙色部分，用 arr[j+1 ... i-1] 来表示大于 v 的紫色部分。
接下来就要看如何来调整下一个元素 e 的位置。分情况讨论：
当 e 大于 v 时，我们直接让 e 融入大于 v 的部分，并让 i++
当 e 小于 v 时，我们让 e 和大于 v 部分的第一个元素交换位置。
把 e 融入到小于 v 的部分。此时就需要让分隔线的索引位置 j++ ，相应的，索引 i 的位置也要 i++ 以便查看下一个元素。
以这样的步骤我们就能遍历完整个数组，如下图所示
现在还差最后一个步骤，那就是把基准值 v ，与小于 v 部分的最后一个元素交换位置。此刻 v 左边都小于它，v 右边都大于它，而 j 指向的就是基准值所在的位置。这样我们就完成了分区（Partition）操作。
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function quickSort(arr) {
if (arr.length <= 1) return arr;
let leftArr = [];
let rightArr = [];
let q = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > q) {
rightArr.push(arr[i]);
} else {
leftArr.push(arr[i]);
}
}
return [].concat(quickSort(leftArr), [q], quickSort(rightArr));
}
console.log(quickSort(arr));
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function countingSort(arr) {
var len = arr.length,
Result = [],
Count = [],
min = max = arr[0];
// 查找最大最小值,并将arr数置入Count数组中,统计出现次数
for (var i = 0; i < len; i++) {
min = min <= arr[i] ? min : arr[i];
max = max >= arr[i] ? max : arr[i];
Count[arr[i]] = Count[arr[i]] ? Count[arr[i]] + 1 : 1;
}
// 从最小值->最大值,将计数逐项相加
for (var j = min; j < max; j++) {
Count[j + 1] = (Count[j + 1] || 0) + (Count[j] || 0);
}
// Count中,下标为arr数值,数据为arr数值出现次数;反向填充数据进入Result数据
for (var k = len - 1; k >= 0; k--) {
// Result[位置] = arr数据
Result[Count[arr[k]] - 1] = arr[k];
// 减少Count数组中保存的计数
Count[arr[k]]--;
}
return Result;
}
console.log(countingSort(arr));