关于排序那些事

前言

---

春招要来了，大三的我目标找到一家实习公司，趁着这段空闲时间，来温习温习数据结构与算法吧。来看排序篇吧。

排序知识点回顾

冒泡排序

时间复杂度为O(n)=n²
排序算法中最简单的即冒泡排序。但运行时间也最长。
冒泡排序的基本思想是，比较任何两个相邻项，若后者比前者小，将会交换这两项。进而每次确定一个最大值。像气泡一样升到表面，因此得名。

function bubbleSort(array){
    var max = array.length
    var flag = true;
    for(var i=0;i<max;i++){
        for(var j=0;j<max-i-1;j++){
            if(array[j]>array[j+1]){
                flag = false;
                [array[j],array[j+1]]=[array[j+1],array[j]];
            }
        }
        if(flag){
            break;
        }
    }
    return array;
}

选择排序

时间复杂度为O(n)=n²
选择排序的大致思路是找到数据结构中最小值，并将其放到第一位。而后找到第二小的值，将其放在第二位。

function easyChooseSort(array){
    if(array.length<=1){
        return array;
    }
    for(var i=0;i<array.length-1;i++){
        var minIndex = i;
        for(var j=i+1;j<array.length;j++){
            if(array[minIndex]>array[j]){
                minIndex = j;
            }
        }
        if(minIndex !=i){
            [array[i],array[minIndex]]=[array[minIndex],array[i]];
        }
    }
    return array;
}

插入排序

时间复杂度：O(n)=n²
当比较小型数组时，该排序比冒泡排序和选择排序效果更好。
插入排序的思想类似于扑克牌，假定第一项已排序完成，接着和第二项比较，排序前两项后和第三项比较。

function insertSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    for(var i=1;i<arr.length;i++){
        var key = arr[i];
        var j = i;
        while(j>0 && key < arr[j-1]){
                arr[j] = arr[j-1];
                j--;
        }
           arr[j] = key;
    }
    return arr;
}

Shell排序

时间复杂度O(n)=nlogn
Shell排序是插入排序的高效版，可以设定间隔，进行插入排序。

function shellSort(arr,length){
    if(gap <= 1){
        return arr;
    }
    var gap = Math.floor(length/2);
    for(gap;gap>=1;gap=gap/2){
        for(var i=gap; i<arr.length; i++){
            if(arr[i] < arr[i-gap]){
                var temp = arr[i];
                var k = i-gap;
                while(k>=0 && arr[k]>temp){
                    arr[k+gap] = arr[k];
                    k = k-gap;
                }
               arr[k+gap] = temp;
            }
        }
    }
    return arr;
}

归并排序

时间复杂度O(n)=nlogn
归并排序效果较好，其基本思想是分而治之，向归并（分）成各个小元素，而后排序（治）成有序数组。
Js中的Array类定义一个sort()函数（Array.prototype.sort),各大浏览器实现算法不一，Firefox浏览器使用归并排序，Chrome浏览器使用快速排序。

function merge(arr){
    if(arr.length<=1){
        return arr;
    }
    var mid = Math.floor(arr.length/2);
    var left = arr.slice(0,mid);
    var right = arr.slice(mid);
    return mergeSort(merge(left),merge(right));
}
function mergeSort(leftNode,rightNode){
    var resultArray = [];
    while(leftNode.length>0 && rightNode.length>0){
        if(leftNode[0] < rightNode[0]){
            resultArray.push(leftNode.shift());
        }else{
            resultArray.push(rightNode.shift());
        }
    }
    return resultArray.concat(leftNode).concat(rightNode);
}

快速排序

时间复杂度O(n)=nlogn
快速排序的基本思想也是分而治之，但并不分成归并排序的小粒度，而是选取基准元素，遍历数组，将每个元素与基准元素进行比较，放入左侧或右侧，递归调用整个过程。

function quickSort(array){
    if(array.length<=1){
        return array;
    }
    var left = [];  
    var right = [];
    var pivotIndex = Math.floor(array.length/2);
    var pivot = array.splice(pivotIndex,1);
    for(var i=0;i<array.length;i++){
        if(array[i]<pivot){
            left.push(array[i]);
        }else{
            right.push(array[i]);
        }
    }
    return quickSort(left).concat([pivot],quickSort(right));
}

计数排序

时间复杂度O(n)=n
计数排序的基本思想为采用HashMap的思想，牺牲空间换取时间。使用额外数组的索引来记录待排序数组的值，并记录数目，完成后将额外数组进行转化。

function countingSort(arr, maxValue) {
    var resultArray = [];
    var index = 0;
    var buckArray = new Array(maxValue + 1);
    for (var i = 0; i < arr.length; i++) {
        if (!buckArray[arr[i]]) {
            buckArray[arr[i]] = 0;
        }
        buckArray[arr[i]]++;
    }
    for(var j=0;j<buckArray.length;j++){
        while(buckArray[j]>0){
            resultArray[index++] = j;
            buckArray[j]--;
        }
    }
    return resultArray;
};

颜色分类_中等

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。
示例: 输入:[2,0,2,1,1,0] 输出: [0,0,1,1,2,2]

这里使用计数排序，直接求解。

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    var tempArray = [0,0,0];
    var index=0;
    for(var i of nums){
        tempArray[i]++;
    };
    for(var i in tempArray){
        while(tempArray[i]>0){
            nums[index++] = i; 
            tempArray[i]--;
        }   
    }
};

排序链表_中等

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1: 输入: 4->2->1->3 输出:1->2->3->4
示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5

题中有提示时间复杂度为O(n)=nlogn，由此我们可以采取归并排序分而治之的思想，采用链表快慢指针的方式拆分链表，进而对链表排序。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
var sortList = function(head) {
    if(head==null || head.next==null){ 
        return head; 
    };
    let [slow,fast,mid] = [head,head.next,null];
    while(fast && fast.next){
        [slow,fast] = [slow.next,fast.next.next]
    };
    [slow.next,mid] = [null,slow.next];
    let[left,right] = [sortList(head),sortList(mid)];
    let curr = res = new ListNode(null);
    while(left && right){
        if(left.val <= right.val){
            [curr.next,left] = [left,left.next]
        }else{
            [curr.next,right]=[right,right.next]
        }
        curr = curr.next;
    }
    curr.next = left ? left : right;
    return res.next;
};