javascript sort

[violet0sea]

合并排序采取分而治之的策略，将数组递归划分为两个子数组，直到数组无法划分为止，此时，再由细化的数组逐级向上合并，依次比较两个数组里面较小的数，然后取出来放入新的数组，最终组合各个层级的数组，从而完成排序

function merge(left, right) {
    let result = [];
    while(left.length > 0 && right.length > 0) {
        if(left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return result.concat(left,right);
}

function mergeSort(array) {
    if(array.length === 1) {
        return array;
    }
    var middle = Math.floor(array.length / 2);
    var left = array.slice(0, middle);
    var right = array.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

集完美优雅于一身的排序

[violet0sea]

侏儒排序，选取数组中的第二个元素为侏儒标志位，通过不断比较和替换侏儒达到排序的目的

// var count = 0;
function gnome(array) {
    var len = array.length, i = 1;
    while(i < len) {
        if(array[i-1] <= array[i]) { // 恰巧两个数按照大小关系排好
            i++;
        } else { // 需要交换位置，并且侏儒的标志位需要变更
            swap(array, i, i - 1);
            if(i > 1) {
                i--;
            }   
        }
              // count++;
    }
}
function swap(array, a, b) {
    const temp = array[a];
    array[a] = array[b];
    array[b] = temp; 
}
var arr = [1,5,2,3,0];
gnome(arr); // [0, 1, 2, 3, 5]

对于需要交换位置的元素，如果遇到较小的值在后面，需要将和之前已经排序好的值依次比较找到正确的位置，然后i还需要依次恢复到交换之前的位置，可以优化吧，记录上次已经比较的位置，减少排序次数

//可以设置一个变量count,未优化前count = 15

//优化后 count = 11；

var count = 0;
var lastPos = 1;
function gnome(array) {
    var len = array.length, i = 1;
    while(i < len) {
        if(array[i-1] <= array[i]) {
            i++;
            lastPos = i; // 无需排序 每次更新记录位置
        } else {
            swap(array, i, i - 1);
            if(i > 1) {
                i--;
            } else {
                            i = lastPos + 1; // 将需要排序的值依次向前比较，整个过程完成后恢复到上次之后的位置
                        }   
        }
count++
    }
}
function swap(array, a, b) {
    const temp = array[a];
    array[a] = array[b];
    array[b] = temp; 
}
var arr = [1,5,2,3,0];
gnome(arr); // [0, 1, 2, 3, 5]

[violet0sea]

插入排序: 默认第一个已经排好，拿元素找位置，如果元素小于已经排好的列表，则将被比较位置的元素后移一位，直到找到正确的位置才插入该元素

function insertionSort(array) {
    for(let i = 1; i < array.length; i++) {
        const temp = array[i];
        let j = i; // 用于记录比较标记位
        while(j>0&&(temp < array[j - 1])) {
            array[j] = array[j - 1]; // 右移一位
            j--; // 比较标记位置左移
        }
        array[j] = temp; // 找到合适的位置后插入
    }
}

[violet0sea]

创建一个最大堆

首先将需要排序的数组转换为一个最大堆，依据最大堆的特性，父节点永远大于子节点，由最后一个非叶节点依次递归实现最大堆的构建，将堆的根元素与堆的最后一个元素交换，并将堆的大小减1，则最大值位于当前数组的最后一位，由于交换会引起最大堆性质的改变，所以每次交换需要重新建立最大堆

function maxHeap(arr, i, len) {
    const temp = arr[i];
    let child, j;

    for(j = i; (j * 2 + 1) < len;) {
        child = j * 2 + 1; // 左侧子节点
        if(child < len - 1 && arr[child] < arr[child + 1]) { // 边界处理 单一子节点的不考虑
            child++; // 从左右节点中选取较大的那个
        }

        if(arr[child] > temp) {
            arr[j] = arr[child]; // 父节点位置存储较大的值
        } else {
            break;
        }

        j = child; // 向下检查子节点
    }

    arr[j] = temp; 
}

function sort(arr) {
    let length = arr.length;
    const len = arr.length >> 1 ;
    for(let i = len; i >=0; i--) {
        maxHeap(arr, i, length)
    }

    while(length--) {
        const temp = arr[length];
        arr[length] = arr[0];
        arr[0] = temp;
        maxHeap(arr, 0, length);
    }

}

[violet0sea]

function shellSort(arr) {
    let len = arr.length;
    for(let step = len >> 1; step > 0; step = step >> 1) {
        for(let i = step; i < len; i++) {
            let temp = arr[i];
            let j;
            for(j = i; j >= step; j -= step) {
                if(temp < arr[j - step]) {
                    arr[j] = arr[j - step];
                } else {
                    break;
                }
            }
            arr[j] = temp;
        }
    }
}

[violet0sea]

快速排序

采用分治策略： 1.如果数组长度 <= 1，直接返回 2.找到一个基准值（pivot)，这里取数组的最后一个 3.比较数组中0-len-1个与pivot的大小，将小元素放到left数组，大元素放到right数组 4.拼接left，pivot，right数组，递归求解left，right数组。

function quickSort(arr) {
    let len = arr.length;
    if(len <= 1) {
        return arr;
    }

    const pivot = arr[len - 1];
    let i = 0;
    let left = [];
    let right = []

    for(; i < len - 1; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return [].concat(quickSort(left), pivot, quickSort(right));

}

上面的方法需要额外创建数组存储

function partion(arr, left, right) {
    const pivot = arr[right];
    let i = left;
    let j = right;

    while(i < j) {

        while(i < j && arr[i] < pivot) {
            i++;
        }

        if(i < j) {
            arr[j] = arr[i];
            j--;
        }

        while( i < j && arr[j] > pivot) {
            j--;
        }

        if(i < j) {
            arr[i] = arr[j];
            i++;
        }
    }

    arr[j] = pivot;
    return j;
}

function quickSort(arr, left, right) {
    if(left >= right) {
        return;
    }

    let j = partion(arr, left, right);
    quickSort(arr, left, j - 1);
    quickSort(arr, j + 1, right);
}

var arr = [3,5,4,31,23,1,0]
quickSort(arr, 0, 6)