js 常用排序整理

排序：
　　1. 内部排序：
　　　　(1). 交换排序：
　　　　　　1). 冒泡排序 稳定
　　　　　　　　一次比较相邻两个元素的大小，顺序错误的，将其位置互换
　　　　　　　　（从高位到低位 或者 从低位到高位）

初始版：　

          var array = [6, 5, 3, 1, 8, 7, 2, 4],
        length = array.length,
        temp = '';
        for (var i=0; i<length-1; i++) {
            for (var j=0; j<length-i-1; j++) {
                if (array[j]>array[j+1]) {
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        console.log(array)    

　改进版（定义标志变量记录每次最后一次交换的位置索引，此标志变量之后的元素都已交换完成，故再次循环的时候只进行到标记变量的位置比较即可）

var array = [6, 5, 3, 1, 8, 7, 2, 4],
    temp = '',
    i = array.length - 1;
    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (array[j] > array[j + 1]) {
                pos = j;
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        i = pos;
    }
    console.log(array)

鸡尾酒(定向冒泡排序)（从高位到低位的同时也从低位到高位）

        var array = [6,5,3,1,8,7,2,4],
        length = array.length,
        temp = '',
        left = 0,
        right = length-1;
        while (left<right) {
            for (var i=0; i<right; i++) {
                if (array[i]>array[i+1]) {
                    temp = array[i];
                    array[i] = array[i+1];
                    array[i+1] = temp;
                }
            }
            right--;
            for (var i=right; i>left; i--) {
                if (array[i]<array[i-1]) {
                    temp = array[i];
                    array[i] = array[i-1];
                    array[i-1] = temp;
                }
            }
            left++;
        }
        console.log(array)

　　　　　  2). 快速排序 不稳定
　　　　　　　　1. 取数组中间索引(pivotIndex)
　　　　　　　　2. 去数组中间位置元素(pivot = Number(array.splice(pivotIndex, 1)))
　　　　　　　　3. 新建两个空数组left, right
　　　　　　　　4. 循环跟数组中间元素比较，大的放right，小的放left
　　　　　　　　5. 递归回调: 对left,right 分别递归回调形成有序的数组后
　　　　　　　　6. 最后，将有序的left pivot right 三部分 concat 起来

var array = [6,5,3,1,8,7,2,4];
function quickSort(array) {
    if (array.length <= 1) {
        return array;
    }
    const pivotIndex = parseInt(array.length / 2);
    const pivot = Number(array.splice(pivotIndex, 1));
    const left = [];    const right = [];
    for (let 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));
};
console.log(array)            

　　　　(2). 插入排序：
　　　　　　1). 直接插入排序 稳定
　　　　　　　　1. 取无序序列的第一个最为有序序列
　　　　　　　　2. 从第二个开始抓取，从有序序列的末尾开始向前找
　　　　　　　　3. 如果 比较到的元素(有序序列中的元素)(array[j]) > 被比较的元素(要插入的元素)(key)，则 将前者向后移动一个位置(array[j+1] = array[j])
　　　　　　　　4. 如果 比较到的元素(有序序列中的元素)(array[j]) >= 被比较的元素(要插入的元素)(key)，则 将后者放置前者的下一个位置处(array[j+1] = key)

        var array = [6,5,3,1,8,7,2,4];
        for (let i = 1; i < array.length; i++) {
            let key = array[i];
            let j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
        console.log(array)

　　　　　　2). 二分法插入排序
　　　　　　　　1. 取无序序列第一个元素作为有序序列(即有序序列的起始)(有序序列：array[0]~array[i-1])
　　　　　　　　2. 取下一个元素(array[i])作为被插入元素并做记录为 key
　　　　　　　　3. 取有序序列的开始及结束位置的索引分别为 left 和 right
　　　　　　　　4. 取有序序列的中间索引为 middle= Math.floor((left+right)/2)
　　　　　　　　5. 将 middle 位置的元素 array[middle] 与 被插入元素 key 比较，
　　　　　　　　　　如果 key > array[middle]，便置 left = middle+1，
　　　　　　　　　　反之 key > array[middle] ,则置 right = middle-1，
　　　　　　　　　　直至 right < left 为止
　　　　　　　　　　(此步骤为 二分查找 原理)
　　　　　　　　6. 对从 left 到 key值元素所在位置索引 i-1 处之间的有序序列 array[left]~array[i-1] 与 key 两者之间采用 直接插入法 进行插入
　　　　　　　　7. 重复以上步骤 2~6

        var array = [6,5,3,1,8,7,2,4];
        for (let i = 1; i < array.length; i++) {
            let key = array[i], left = 0, right = i - 1;
            //console.log(i+'++'+key);
            //console.log(left+'=='+right);
            while (left <= right) {
                let middle = parseInt((left + right) / 2);
                //console.log(left+'=='+middle+'=='+right)
                if (key < array[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
                //console.log(left+'=='+right)
            }
            //console.log(array)
            for (let j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            //console.log(array)
            }
            array[left] = key;
            //console.log(array)
        }
        console.log(array)

　　　　　　3). 希尔排序 不稳定
　　　　　　　　不太理解

        var arr=[49,38,65,97,76,13,27,49,55,4],
        len=arr.length;
        for(var fraction = Math.floor(len/2);fraction>0;fraction = Math.floor(fraction/2)){
            for(var i=fraction;i<len;i++){
                for(var j=i-fraction;j>=0&&arr[j]>arr[fraction+j];j-=fraction){
                    var temp=arr[j];
                    arr[j]=arr[fraction+j];
                    arr[fraction+j]=temp;
                }
            }
        }
        console.log(arr);

　　　　(3). 选择排序：
　　　　　　1). 简单选择排序 不稳定
　　　　　　　　1. 取序列的第一个元素作为有序序列，并取该序列末尾索引位置为作参照，minIndex=0
　　　　　　　　2. 从序列的第二个元素开始与 array[minIndex] 做比较，如果小就记该元素位置索引为 minIndex,
　　　　　　　　3. 重复操作步骤2 直至再无更小元素为止，将此时的 minIndex 与有序序列的末尾元素互换
　　　　　　　　(先从未排序序列中找出最小（大）元素，将该最小元素与序列的起始位置交换，至此 最小元素即到了有序元素的起始位置，
　　　　　　　　然后 再从剩余的未排序序列中继续寻找最小（大）元素，依次与未排序序列中的起始位置互换，至此 次大的元素就依次放到了有序序列的末尾)

        var array = [6,5,3,1,8,7,2,4],
              length = array.length;
        for (let i = 0; i < length - 1; i++) {
            let minIndex = i;
            console.log(array[minIndex]);
            for (let j = i + 1; j < length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            let temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
            console.log(array);
        }
        console.log(array)

　　　　　　2). 堆排序 不稳定

　　　　(4). 归并排序： 稳定
　　　　　　1). 递归原理
　　　　　　　　1. 利用递归将数组对半开分为 left，right 两个数组，直到每个拆分完的数组中只有一个元素为止，将每个数组视为有序数组
　　　　　　　　2. 创建一个新的数组 newArray 来放排好序的元素
　　　　　　　　3. 从每个数组的第一个元素开始拿来比较，往newArray里放，小的先放，大的后放
　　　　　　　　注：步骤1 是递归进最里层，步骤3 是递归往外出，最后得到有序序列

            function mergeSort(array) {
            if (array.length < 2) {
                return array;
            }
            const middle = parseInt(array.length / 2);
            const left = array.slice(0, middle);
            const right = array.slice(middle);
            return merge(mergeSort(left), mergeSort(right));
        }
        function merge(left, right) {
            const newArray = [];
            while (left.length && right.length) {
                if (left[0] <= right[0]) {
                    newArray.push(left.shift());
                } else {
                    newArray.push(right.shift());
                }
            }
            while (left.length) {
                newArray.push(left.shift());
            }
            while (right.length) {
                newArray.push(right.shift());
            }
            return newArray;
        }

　　　　　　2). 基数排序： 稳定
　　2. 外部排序：
　　　　(1). 计数排序 稳定
　　　　(2). 桶排序 稳定

http://www.cnblogs.com/eniac12/p/5329396.html

http://www.cnblogs.com/eniac12/p/5332117.html

http://www.jianshu.com/p/96f5c19e13df