/* 手撕排序 + 算法总结 */
//比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
//非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

// 1.冒泡排序
//时间复杂度O(n^2) 最好情况O(n)，空间O(1) 稳定
//它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
//走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
var num = [1,2,4,3,5,6,8,7,9]
var bubbleSort = function(num){
    var temp=0;
    var i=num.length;
    while(i--){
        for(let j=0;j<i-1;j++){
            if(num[j]>num[j+1]){
                temp = num[j+1];
                num[j+1]=num[j];
                num[j]=temp;
            }
        }
    }
    return num;
}
var a=bubbleSort(num);
console.log(a);

// 2.选择排序
//时间复杂度O(n^2) 最好情况O(n^2)，空间O(1) 不稳定
//首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
//然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
var selectionSort = function(num){
    for(let i=0;i<num.length;i++){
        let temp=0;
        for(let j=i+1;j<num.length;j++){
            if(num[i]>num[j]){
                temp=num[j];
                num[j]=num[i];
                num[i]=temp;
            }
        }
    }
    return num;
}
var b=selectionSort(num);
console.log(b);

// 3.插入排序
//时间复杂度O(n^2) 最好情况O(n)，空间O(1) 稳定
//通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
var insertionSort = function(num){
    var temp=0;
    for(let i=0;i<num.length;i++){
        for(let j=i;j>0;j--){
            temp = num[j];
            if(num[j]<num[j-1]) num[j] = num[j-1];
            else{
                num[j]=temp;
                break;
            }
        }   
    }
    return num;
}
var c=insertionSort(num);
console.log(c)

// 4.归并排序
//该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
//将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
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>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}
var d=mergeSort(num);
console.log(d);

// 5.快速排序
//通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，
//则可分别对这两部分记录继续进行排序，以达到整个序列有序。
//steps
//从数列中挑出一个元素，称为 “基准”（pivot）；
//重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
//递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
var quickSort = function(nums){
    var len = nums.length;
    if(len<2) return nums;
    var pivot = nums[Math.floor(len/2)];
    var left = 0,right = nums.length-1;
    var temp = 0;
    while(left!=right){
        if(nums[left]<pivot) left++;
        if(nums[right]>pivot) right--;
        temp = nums[right];
        nums[right] = nums[left];
        nums[left] = temp;
    }
    quickSort(nums.slice(0,left));
    quickSort(nums.slice(right,len));
    return nums;
}

var e=quickSort(num);
console.log(e);