开篇
共总结了冒泡，选择，插入，归并，快速，希尔，堆七种排序方式，而V8引擎sort的排序：数组长度小于等于 10的用插入排序，其它的用快速排序。
不稳定算法：快 希 选 堆
以下是算法可能涉及到的公共函数：
//排除非数组
function checkArray(array) {
if (!array instanceof Array)return;
}
//交换两个元素
function swap(array, left, right) {
let rightValue = array[right]
array[right] = array[left]
array[left] = rightValue
}
一.冒泡 时间复杂度是 O(n * n)
function bubble(array) {//冒泡算法
checkArray(array);
for (let i = array.length - 1; i > 0; i--) {
// 从 0 到 `length - 1` 遍历
for (let j = 0; j < i; j++) {
if (array[j] > array[j + 1]) swap(array, j, j + 1)
}
}
return array;
}
function checkArray(array) {
if (!array) return
}
function swap(array, left, right) {
let rightValue = array[right]
array[right] = array[left]
array[left] = rightValue
}
变种：求数组中最小 的K个数字
function GetLeastNumbers_Solution(input, k)
{
let arr=[];
// write code here
for(let i = 0; i < k;i++){
for(let j=0;j<input.length-i-1;j++){
if(input[j]<input[j+1]){//将小的数冒泡到最后
let tmp=input[j];
input[j]=input[j+1];
input[j+1]=tmp;
}
}
arr.push(input[input.length - i - 1]);//拿input最后值加入
}
return arr;
}
二.选择排序 时间复杂度是 O(n * n)
//遍历数组，定义一个等于当前索引的最小值索引。取出当前的值去与其他元素比较，得到最小值索引，把最小值索引代表的元素赋值给当前值。
function choise(arr){
for(let i=0;i<arr.length;i++){
let min=i;
for(let j=i+1;j<arr.length;i++){
min=arr[min]>arr[j]?j:min;
}
swap(arr,min,i);
}
}
三.插入排序 时间复杂度是 O(n * n)
//默认前面是已经排好序的，遍历数组，取出当前值与前面排好的序列进行比较。
//如果当前值比前一个数小，就与其交换位置。
//重复以上步骤
function insert(arr){
for(let i=1;i<arr.length;i++){//默认第一个排好序
for(let j=i;j>=0;j--){
if(arr[j]<arr[j-1])swap(arr,j,j-1);//如果前一个数比后一个数字大
}
}
return arr;
}
四.归并排序 时间复杂度为 O(N * logN)
/*
假如有数组[1,4,3,6,8,7,5],利用中间索引3，拆分得到[1,4,3,6]和[8,7,5],继续拆分得到[1,4]和[3,6]
对[1,4]和[3,6]各自排序后，再对[1,4,3,6]排序，右边也是如此，最后合并
先递归的分解数列，再合并数列
*/
/*
合并两个有序数列
如何将将二个有序数列合并。这个非常简单，
只要从比较二个数列的第一个数，谁小就先取谁，
取了后就在对应数列中删除这个数。然后再进行比较，
如果有数列为空，那直接将另一个数列的数据依次取出即可。
*/
function mergeArray(left,mid,right,array){
let help = [];
let i = 0;
let p1 = left;
let p2 = mid + 1;
//合并 ：将两个序列a[first-middle],a[middle+1-end]合并
while (p1 <= mid && p2 <= right) {
help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
while (p1 <= mid) {
help[i++] = array[p1++];
}
while (p2 <= right) {
help[i++] = array[p2++];
}
for (let i = 0; i < help.length; i++) {
array[left + i] = help[i];
}
return array;
}
//递归分解
function mergeSort(array, left, right) {
// 左右索引相同说明已经只有一个数
if (left === right) return;
let mid = parseInt(left + ((right - left) >> 1));
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
//合并
mergeArray(left,mid,right,array);
}
/*
mergeSort(array, left, right)
mergeSort(data, 0, 6) // mid = 3
mergeSort(data, 0, 3) // mid = 1
mergeSort(data, 0, 1) // mid = 0
mergeSort(data, 0, 0) // 遇到终止，回退到上一步
mergeSort(data, 1, 1) // 遇到终止，回退到上一步
// 排序 p1 = 0, p2 = mid + 1 = 1, mergeArray(left0,mid0,right1,array) [8,3]变成[3,8]
// 回退到 `mergeSort(data, 0, 3)` 执行下一个递归
mergeSort(2, 3) // mid = 2
mergeSort(3, 3) // 遇到终止，回退到上一步
// 排序 p1 = 2, p2 = mid + 1 = 3, [2，1]变[1,2]
// 回退到 `mergeSort(data, 0, 3)` 执行合并逻辑//mid=1
// 排序 p1 = 0, p2 = mid + 1 = 2
// 执行完毕回退
// 左边数组排序完毕，右边也是如上轨迹
*/
五.快速排序 平均时间复杂度：O(N*logN)
function quickSort(array, left, right) {
if (left < right) {
// 用中间值作为基准值或者随机
let mid=(left+right)>>1;
console.log(mid);
swap(array,left,mid);
let i=left,j=right,x=array[left];//x为基准值
while(i<j){
while(i<j&&array[j]>=x)//因为是找比x小的，从右向左比较，array[j]大的时候，j--
j--;
if(i<j){
array[i++]=array[j];
}
while(i<j&&array[i]<x){//从左向右比较，i向前
i++;
}
if(i<j){
array[j--]=array[i];
}
}
array[i]=x;//array[i]的左边是小于它的数，右边是大于的
quickSort(array,left,i-1);
quickSort(array,i+1,right);
}
return array;
}
console.log(quickSort(arr,0,arr.length-1))
六.希尔排序 希尔排序的时间复杂度和增量序列是相关的
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔算法步骤：选择一个增量，一般是初始增量gap=length/2，对利用gap分好的组进行插入排序，缩小增量继续以gap = gap/2的方式，重复以上步骤。当gap=1时，数组已经基本有序，而插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
//希尔排序
/**
* @msg:希尔排序
* @param {Array}arr 数组
* @return: {Array} 新数组
*/
console.log(shellSort([2,5,66,1,3,4]))
function shellSort(arr){
//增量gap初始为数组长度的一半，逐渐缩小，以gap/2的方式
for(let gap=parseInt(arr.length/2);gap>0;gap=parseInt(gap/2)){
//从第gap个元素开始，对用gap分好的组进行插入排序
for(let i=gap;i<arr.length;i++){
let j=i;
//插入排序
while(j-gap>=0&&arr[j]<arr[j-gap]){
swap(arr,j,j-gap);
j-=gap;//跳出循环
}
}
}
return arr;
}
七.堆排序(HeapSort) 平均时间复杂度：O(NlogN)
堆排序是利用堆这种数据结构而设计的一种排序算法
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
堆排序思路：
1.先构造大顶堆
2.将堆顶元素放入末尾
3.再重新调整结构使其满足大顶堆
4.重复2，3步骤
/**
* @msg: 堆排序
* @param {Array} arr 数组
* @return: {Array} 新数组
*/
heapSort([4,6,8,5,9]);
function heapSort(arr) {
// 1.构造大顶堆
for (let i = parseInt(arr.length/2)-1; i >= 0; i--) {
console.log(i);
//i从第一个非叶子节点开始
//数组[4,6,8,5,9]变成[ 9, 6, 8, 5, 4 ]
adjustHeap(arr, i, arr.length);
console.log(arr);
}
//2.将堆顶元素与末尾元素进行交换，再进行调整
for(let j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
}
console.log(arr);
}
/**
* @msg: 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
* @param arr
* @param i
* @param length *
* @return: {array} 新数组
*/
function adjustHeap(arr,i,length){
//先取出当前元素
let temp=arr[i];
//从i节点的左子节点开始
for(let k=i*2+1;k<length;k=k*2+1){
if(k+1<length&&arr[k]<arr[k+1]){//如果k++左子节点小于右子节点
//k指向右子节点
k++;
}
if(arr[k]>temp){//如果子节点大于父节点
//将子节点赋予父节点
arr[i]=arr[k];
i=k
}else{
break;
}
}
arr[i]=temp;//temp会根据情况赋值给对应的节点，i可能变化
}