排序算法（冒泡排序、选择排序、计数排序、快速排序、插入排序、归并排序）
二分查找法
翻转二叉树
若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的
将最大数置底
function swap(myArray, p1, p2){
var temp = myArray[p1];
myArray[p1] = myArray[p2];
myArray[p2] = temp;
}
function bubbleSort(myArray){
var len = myArray.length;
var i;
var j;
var stop;
for (i = 0; i < len - 1; i++){
for (j = 0, stop = len - 1 - i; j < stop; j++){
if (myArray[j] > myArray[j + 1]){
swap(myArray, j, j + 1);
}
}
}
return myArray;
}
bubbleSort([1,3,4,2,5,6])将第一个元素和其他元素进行比较，检查完所有元素后,最小的元素会被放到数组的第一个位置
function selectionSort(arr) {
let min
let temp
let length = arr.length
// 因为到倒数第二个的时候，全部数组就已经排好序了
for(let i = 0; i < length - 2; i++) {
min = arr[i]
for(let j = i + 1; j < length - 1; j++) {
if(arr[j] < min) {
min = arr[j]
swap(arr, j, i)
}
}
}
return arr
}
selectionSort([1,3,4,2,5,6])插入未排序数到已排序的结果数组
相比于冒泡排序，如果数组已经有序，则时间复杂度为O(n)
function insertionSort(arr) {
let sortedArrIndex
let tempValue
let length = arr.length
for(let i = 1; i < length - 1; i++) {
sortedArrIndex = i
tempValue = arr[i]
while(sortedArrIndex > 0 && (arr[sortedArrIndex - 1] > tempValue)) {
// 插入
arr[sortedArrIndex] = arr[sortedArrIndex - 1]
sortedArrIndex--
}
arr[sortedArrIndex] = tempValue
}
return arr
}
console.log(insertionSort([1,3,4,2,5,6]))把一系列排好序的子序列，合并成一个大的完整有序序列
但是需要较大的空间存储数据,数据较大时容易溢出,是一个自底向上的过程
function merge(left, right) {
let temp = []
while(left.length && right.length) {
if(left[0] > right[0]) {
temp.push(right.shift())
} else {
temp.push(left.shift())
}
}
return temp.concat(left, right)
}
function mergeSort(arr) {
let length = arr.length
if(length < 2) {
return arr
}
let mid = Math.floor(length / 2)
let left = arr.slice(0, mid)
let right = arr.slice(mid)
return merge(mergeSort(left), mergeSort(right))
}
console.log(mergeSort([1,3,4,2,5,6]))是插入排序的升级，分组插入排序。 插入排序间隔为gap的元素，逐渐减少gap至1
function shellSort(arr) {
if (!arr) {
return
}
let len = arr.length
let gap = 1
while (gap < len / 3) {
gap = 3 * gap + 1; //设置间隔
}
while (gap >= 1) {
for (var i = gap; i < len; i++) {
for (j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
swap(arr, j, j - gap);
}
}
gap = (gap - 1) / 3;
}
return arr
}选择基准元素，将大于和小于基准元素的元素分别放到不同的数组，重复知道数组中只有一个元素
function quickSort(arr) {
// 为空返回
if(!arr) {
return
}
// 长度小于等于1代表已完成排序
if(arr.length <= 1) {
return arr
}
// 选取中间元素,划分数组
const mid = Math.floor(arr.length / 2)
const midItem = arr.splice(mid, 1)[0]
let left = []
let right = []
arr.forEach(item => {
if(item < midItem) {
left.push(item)
} else {
right.push(item)
}
})
// 递归调用
let _left = quickSort(left)
let _right = quickSort(right)
return _left.concat(midItem, _right)
}
// 一行代码实现
function quickSort(a) {
return a.length <= 1 ? a : quickSort(a.slice(1).filter(item => item <= a[0])).concat(a[0], quickSort(a.slice(1).filter(item => item > a[0])));
}
console.log(quickSort([1,2,4,10,2,9,4,1]))堆排序是选择排序的升级版
其优点在于当求M个数中的前n个最大数，和最小数的时候性能极好。所以当从海量数据中要找出前m个最大值或最小值，而对其他值没有要求时，使用堆排序法效果很好
var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) { // 建立大顶堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { // 堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, 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--;
heapify(arr, 0);
}
return arr;
}
console.log(heapSort([1, 10, 9, 8, 1, 3, 4]))