排序问题

一、插入排序

遍历数组的元素，nums[i]如果比nums[i-1]小，就说明需要将其插入到nums[0]....nums[i-1]的序列中。

var sortArray = function(nums) {
    var lookout = nums[0];  //监视哨，提供nums[i]的缓存单元
    for(var i=1;i<=nums.length;i++){
        if(nums[i] < nums[i-1]){
            lookout = nums[i];  // 将nums[i]保存到监视哨中
            // 逐级后移
            for(var j=i-1;j>=0 && nums[j]>lookout;j--){ 
                nums[j+1] = nums[j];
            }
            // 插入nums[i]
            nums[j+1] = lookout;
        }
    }
    return nums;
};

算法复杂度：O(n^2)

二、希尔排序

将待排序数组根据一定的增量分组，每一组都进行插入排序，再减少增量，每组元素变多，当增量减至1时，整个文件恰被分成一组，对该组排序进行微调，算法便终止。

var sortArray = function(nums) {
        var len = nums.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = nums[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && nums[preIndex] > temp) {
                    nums[preIndex + gap] = nums[preIndex];
                    preIndex -= gap;
                }
                nums[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return nums;
}

算法复杂度：O(nlogn)

三、冒泡排序

在一趟比较中，比较相邻两个元素nums[j]和nums[j+1]的大小，如果nums[j]>nums[j+1]，两元素交换，这样最大的元素冒泡到数组的最右边。重复上述步骤，直到不存在需要交换的元素，结束循环。

var sortArray = function(nums) {
    var tmp;
    if(nums.length == 0) return [];
    for(var i=0;i<nums.length;i++){
        for(var j=0;j<nums.length-i;j++){
            if(nums[j] > nums[j+1]){
                tmp = nums[j+1];
                nums[j+1] = nums[j];
                nums[j] = tmp;
            }
            // console.log(nums)
        }
    }
    return nums;
};

复杂度O(n^2)

四、快速排序

以序列中第一个元素作为基准，在比较分区的过程中，如果比这个数小的就放在左边，比这个数大的放在右边，返回这个基准数在序列中的位置；在这一趟比较中，比基准数小的数就全部在其左边，大的数全部在其右边。对左右区间分别重复上述步骤，直到区间中只有一个元素(low=high=0)。

var sortArray = function(nums) {
    // 快速排序
    quickSort(nums,0,nums.length-1);
    return nums;
};

var getPivot = function(nums,low,high){
    var pivot;
    while(low<high){
        while(low<high && nums[high] >= nums[low]){
            // 向前寻找比基准数小的元素
            high--;
        }
        if(nums[high] < nums[low]){
            // 较小的元素交换到基准数左边
            pivot = nums[low]; 
            nums[low] = nums[high];
            nums[high] = pivot;
        }
        while(low<high && nums[low]<=nums[high]){
            // 向后寻找比基准数大的元素
            low++;
        }
        if(nums[low]>nums[high]){
            // 较大的元素交换到基准数右边
            pivot = nums[low]; 
            nums[low] = nums[high];
            nums[high] = pivot;
        }
    }
    return low;
}

var quickSort = function(nums,low,high){
    if(low<high){
        var i = getPivot(nums,low,high); // 返回基准数位置
        quickSort(nums,low,i-1); // 对左右区间分别重复操作
        quickSort(nums,i+1,high);
}

复杂度O(nlogn)

五、选择排序

将序列分为排序序列和未排序序列，初始状态下排序序列只有一个元素，即原序列的第一个元素。选择未排序序列中最小的元素，将它交换到排序序列的最后一位。重复上述操作。

var sortArray = function(nums) {
    // 选择排序
    var sortedNums = nums[0],
        index,
        mintmp,minindex,
        temp;
    for(var i=0;i<nums.length;i++){
        minindex = i;
        mintmp = nums[minindex];
        for(var j=i+1;j<nums.length;j++){
            if(nums[j]<mintmp){
                mintmp = nums[j];
                minindex = j;
            }
        }
        temp = nums[i];
        nums[i] = nums[minindex];
        nums[minindex] = temp;
    }
    return nums;
};

复杂度O(n^2)

六、归并排序

将待排序列多次二分成小序列，直到每个小序列只有一个元素为止。然后将小序列归并成排好序的较大序列，直到归并成最大的序列。
图分析如下：（来源于https://blog.csdn.net/wojiuguowei/article/details/84321833）

归并排序图解

var sortArray = function(nums) {
    // 归并排序
    if(nums.length == 1){
        return nums;
    }
    // 拆分子列
    var mid = parseInt(nums.length/2),
        left = nums.slice(0,mid),
        right = nums.slice(mid,nums.length),
        sortedNums = new Array();
    // 子列不可再分（只有一个元素）后开始归并
    sortedNums = merge(sortArray(left),sortArray(right));
    return sortedNums;
};

var merge = function(left,right){
    var len_l = left.length, // 序列剩余元素的个数
        len_r = right.length,
        i = 0,
        j = 0,
        result = [];
    // 左右两列开始归并，由于两列都是有序的，只需要比较开始的元素大小后指针后移即可
    while(i<left.length && j<right.length){
        // if(left[i] == undefined) left[i] = Infinity;
        // if(right[i] == undefined) right[i] = Infinity;
        if(left[i]<right[j]){
            result.push(left[i]);
            i++;
            len_l--;
        }else{
            result.push(right[j]);
            j++;
            len_r--;
        }
    }
    // 考虑到两序列的长度不一样，将剩下的序列直接放入result尾部
    while(len_l>0){
        result.push(left[i]);
        i++;
        len_l--;
    }
    while(len_r>0){
        result.push(right[j]);
        j++;
        len_r--;
    }
    return result;
}

复杂度O(nlogn)