排序 全 js版（冒泡、快排、归并、选择、插入、希尔、堆）

冒泡排序（稳定 O(n^2)）

通过相邻元素之间的比较和交换，将排序码小的元素逐渐从底部移向顶部。

// 冒泡，相邻元素之间比较functionfn(arr){for(let i=0;i<arr.length-1;i++){for(let j=0;j<arr.length-1-i;j++){if(arr[j]>arr[j+1]){let temp = arr[j];
                    arr[j]= arr[j+1];
                    arr[j+1]= temp;}}}return arr;}let arr =[57,68,59,52,72,28,96,33,24,19];
    console.log(fn(arr));

快速排序（不稳定 O(nlogn)）

找基准，比基准大的放右边，比基准小的放左边。

functionfn(arr){if(arr.length<=1)return arr;let index= Math.floor(Math.random()*arr.length);let left =[];let right =[];for(let i=0;i<arr.length;i++){if(arr[i]<=arr[index]){
            left.push(arr[i]);}else{
            right.push(arr[i]);}}returnfn(left).concat(fn(right))}let  arr =[57,68,59,52,72,28,96,33,24,19];
console.log(fn(arr));

归并排序（稳定 O(nlogn)）

分治：

1. 先将数组分成一半，把左边的排序，右边的排序，之后再归并在一起。
2. 左边和右边的数组进行排序，将左边和右边的数组看作单独的一个数组，继续划分。
3. 直到每个部分只有一个元素了，不需要再排序了，直接归并就可以。
4. 归并到上一个层级之后继续归并，归并到更高的层级，直到归并完成。

//拆分functionfn(arr){if(arr.length<2)return arr;let mid =parseInt(arr.length/2);let left = arr.slice(0,mid);let right = arr.slice(mid);returnfn2(fn(left),fn(right));}// 排序+归并functionfn2(left,right){let res =[];// 比大小，拿每个数组中第一个最小的while(left.length>0&&right.length>0){if(left[0]<right[0]){
            res.push(left.shift());}else{
            res.push(right.shift());}}// 跳出循环，left或者right会有一个还有数字return res.concat(left).concat(right);}let  arr =[57,68,59,52,72,28,96,33,24,19];
console.log(fn(arr));

插入排序（稳定 O(n^2)）

移动法：
在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。（从无序的数组中取出一个数字，与有序列表中的最后一个对比，如果小于，就将有序列表中的数字向后移动，直到找到该数组的合适位置。）

functionfn(arr){if(arr.length<2)return arr;for(let i=1;i<arr.length;i++){let j = i-1;// 需要记录一下当前arr[i]的值，进入while循环时会改变当前值let item = arr[i];while(j>0&&item<arr[j]){
            arr[j+1]=arr[j];
            j--;}
        arr[j+1]= item;}return arr;}let  arr =[57,68,59,52,72,28,96,33,24,19];
console.log(fn(arr));

希尔排序（不稳定 O(nlogn)）

插入排序的一种，直接插入排序的优化：
先进行分组，再分别对每组进行直接插入排序，继续分组，继续排序，直到分组到一个元素为一组，结束

functionfn(arr){//分组let gap = Math.floor(arr.length /2);while(gap >=1){for(let i = gap; i < arr.length; i++){let j = i - gap;let item = arr[i];while(j >=0&& item < arr[j]){
                    arr[j + gap]= arr[j];
                    j = j - gap;}
                arr[j + gap]= item;}
            gap = Math.floor(gap /2);}return arr;}let arr =[57,68,59,52,72,28,96,33,24,19];
    console.log(fn(arr));

直接选择排序（不稳定 O(n^2)）

双重循环遍历数组：
每经过一轮比较，找到最小元素的下标，将其交换至首位。（每一轮排序都找出当前的最小值，把这个最小值交换至本轮首位。）

functionfn(arr){let minIndex ;//确定最小值的下标for(let i=0;i<arr.length;i++){
        minIndex = i;for(let j=i+1;j<arr.length;j++){if(arr[j]<arr[minIndex]){
                minIndex = j;}}//交换let temp = arr[i];
        arr[i]= arr[minIndex];
        arr[minIndex]= temp;}return arr;}let  arr =[57,68,59,52,72,28,96,33,24,19];
console.log(fn(arr));

堆排序 （不稳定 O(nlogn)）

思路：先进行初建堆，再进行堆排序，继续执行前面操作

1. 根据给出的序列，建立一个完全二叉树
2. 进行调整，从最后一个非叶子结点，该节点是否全大于该子节点，如果有子节点大于该节点，双方交换，一次进行到根节点，如果下边又出现了该情况，则继续进行交换。—此时初建堆完成
3. 进行堆排序：将根节点从树中去掉，把最后一个结点放到根节点，再进行初建堆的初始化步骤，循环该操作，直到所有节点从树中移除

//堆排序 functionfn(arr){// 初始化大堆顶，从第一个非叶子节点开始 // 完全二叉树中，父节点是i时，左孩子为2i+1，右孩子是2i+2let index = Math.floor(arr.length/2-1);// 先建立大根堆，向上比较的过程，进来的元素与父元素比较，大了就向上走for(let i=index;i>=0;i--){fn1(arr,i,arr.length);}// 大根堆此时已经建立好，将根节点从树中去掉，// 把最后一个结点放到根节点，再进行初建堆的初始化步骤，循环该操作，直到所有节点从树中移除// 次循环就是把跟顶元素，也就是数组中的第一个元素和最后一个元素进行交换，继续进行堆排序for(let j=arr.length-1;j>0;j--){const temp = arr[0];
            arr[0]= arr[j];
            arr[j]= temp;fn1(arr,0,j);}return arr;}//将i节点以下整理成大堆顶 functionfn1(arr,i,length){// 完全二叉树中，父节点是i时，左孩子为2i+1，右孩子是2i+2for(let j=2*i+1;j<length;j=2*j+1){const temp = arr[i];// 判断右孩子节点和左孩子节点哪一个更大，直接拿最大的节点和改父节点比较就可以if(j+1<length&& arr[j]<arr[j+1]){
                j++;}// 如果孩子中的最大节点大于根节点就进行交换，不大于的话不做处理if(temp<arr[j]){
                arr[i]=arr[j];
                arr[j]=temp;
                i=j;}elsebreak;}}let arr =[57,68,59,52,72,28,96,33,24,19];
    console.log(fn(arr));