1、冒泡排序
\1. 冒泡排序
原理：从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素
function bubbleSort(arr) {
if (Array.isArray(arr)) {
for (var i = arr.length - 1; i > 0; i--) {
for (var j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1r[j]];
}
}
}
return arr;
}
}
2、选择排序
原理：遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。
function selectSort(arr) {
if (Array.isArray(arr)) {
for (var i = 0; i < arr.length - 1; i++) {
var minIdex = i;
for (var j = i + 1; j < arr.length; j++) {
minIdex = arr[j] < arr[minIdex] ? j : minIdex;
}
[arr[i], arr[minIdex]] = [arr[minIdex], arr[i]];
}
return arr;
}
}3、插入排序
2.插入排序
原理：第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。
function insertSort(arr) {
if (Array.isArray(arr)) {
for (var i = 1; i < arr.length; i++) {
var preIndex = i - 1;
var current = arr[i]
while (preIndex >= 0 && arr[preIndex] > c) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
}4、希尔排序
原理：
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
// 动态定义间隔序列，也可以手动定义，如 gap = 5；
while (gap < len / 5) {
gap = gap * 5 + 1;
}
for (gap; gap > 0; gap = Math.floor(gap / 5)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
return arr;
}5、归并排序
原理：
（1） 把长度为n的输入序列分成两个长度为n/2的子序列；
（2）对这两个子序列分别采用归并排序；
（3） 将两个排序好的子序列合并成一个最终的排序序列。
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(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) {
// 不断比较left和right数组的第一项，小的取出存入res
left[0] < right[0] ? result.push(left.shift()) : result.push(right.shift());
}
return result.concat(left, right);
}6、快速排序
原理：在数据集之中，找一个基准点，建立两个数组，分别存储左边和右边的数组，利用递归进行下次比较。
function quickSort(arr) {
if (!Array.isArray(arr)) return;
if (arr.length <= 1) return arr;
var left = [], right = [];
var num = Math.floor(arr.length / 2);
var numValue = arr.splice(num, 1)[0];
for (var i = 0; i < arr.length; i++) {
if (arr[i] > numValue) {
right.push(arr[i]);
} else {
left.push(arr[i]);
}
}
return [...quickSort(left), numValue, ...quickSort(right)]
}7、堆排序
一、简介
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
-
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
-
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
-
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
二、js代码
var len;
function buildMaxHeap(arr) { //建堆
len = arr.length;
// [n/2-1]表示的是最后一个有子节点 (本来是n/2（堆从1数起），但是这里arr索引是从0开始，所以-1)
for (var i = Math.floor(len/2)-1; i>=0; i--) {
maxHeapify(arr, i);
}
//对每一个节点（非叶节点），做堆调整
}
function maxHeapify(arr, i) { //堆调整
var left = 2*i+1,
right = 2*i+2,
largest = i; //i为该子树的根节点
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) { //即上面的if中有一个生效了
swap(arr, i, largest); //交换最大的为父节点
maxHeapify(arr, largest); //交换后，原值arr[i]（往下降了）（索引保存为largest），
//作为根时，子节点可能比它大，因此要继续调整
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
maxHeapify(arr, 0);
}
return arr;
}
