# 排序

非常晦涩难懂，但是为啥还是要啃呢，可能是因为对智商比较有好处，类似老头、老太太去打麻将，殊途同归。

冒泡排序 bubbleSort
插入排序 insertSort
折半插入排序 binaryInsertionSort
希尔排序 shellSort

# 冒泡排序 bubbleSort

/**
 * 冒泡排序
 * 入门级排序
 *
 * 2018年09月16日23:14:17
 */

let a = [123, 3, 3, 0, 31, 23, -12, 898, -2, 4, 5, 1, 2];
console.log('origin data is, ', a);
let l = a.length;
// 第一层控制循环次数
for (let i = 0; i < l-1; i++) {
    // 从0开始冒泡，将大的数冒出去，所以也是正序
    for(let k=0; k<l-i; k++ ){
        let temp;
        if(a[k]>a[k+1]){
            temp = a[k];
            a[k] = a[k+1];
            a[k+1] = temp;
        }
    }
}

console.log('bubbleSort result is, ',a)

# 插入排序 insertSort

let aa = [123,233,3,3,1,2,3,4,78,0];
console.log(aa)
let temp,j;
for(let i=1;i<aa.length;i++){
    temp = aa[i];
    j = i-1;
    while(j>=0 && temp<aa[j]){
        aa[j+1] = aa[j];
        --j;
    }
    aa[j+1] = temp;
}

console.log(aa)


// 我理解的插入，
let a = [123,233,3,3,1,2,3,4,78,0];
let b = [a[0]]
console.log(a)
for(let i=1;i<a.length-1;i++){
    b.push(a[i])
    for(let k = 0;k<b.length-1;k ++){
        let temp;
        if(b[k]>b[k+1]){
            temp = b[k];
            b[k] = b[k+1];
            b[k+1] = temp;
        }
    }
}

console.log(b)

# 折半插入排序 binaryInsertionSort


let a = [123, 3, 3, 0, 31, 23, -12, 898, -2, 4, 5, 1, 2];
console.log('origin a= ',a)

let temp,low,high,m;
for(let i=1; i<a.length;i++ ){
    temp  = a[i];
    low = 0;
    high = i-1;
    while(low <= high){
        m = Number.parseInt((high+low)/2);
        if (temp > a[m]){
            low = m+1
        } else {
            high = m-1;
        }
    }
    
    for(let j = i-1; j>=high+1; j--){
        a[j+1] = a[j];
    }
    a[high+1] = temp;
}

console.log('sorted = ', a)

# 希尔排序 shellSort

let a = [123, 3, 0, 31, 23, -12, 898, -2, 4, 5, 1];

/**
 * 
 * shell sort
 * 希尔排序是不稳定排序
 * 
 * 123, 3, 0, 31, 23, -12, 898, -2, 4, 5, 1
 * 0,   1, 2, 3,  4,    5,  6,   7, 8, 9, 10
 * 
 * 以5为增量
 * 123                -12                 1
 *     3,                  898                
 *       0,                    -2
 *         31                    4
 *           23                   5
 * 快速排序
 * -12,              1                    123
 *    3                898
 *     -2                 0
 *       4                  31
 *        5                   23
 * 第一次shell排序结果
 * -12,  3,  -2,  4, 5,  1,  898,  0,  31,  23,  123
 * 0     1    2   3  4   5    6    7    8    9   10
 * 
 * 以3为增量
 * -12,        4          898        23
 *     3        5            0         10
 *      -2       1            31
 * 快速排序
 * -12,      4,          23,        898
 *    0        3           5           10
 *     -2       1           31
 * 
 * 第二次shell排序结果
 * -12,  0,  -2,  4,  3,  1,  23,  5,  31,  898,  10
 * 0     1    2   3   4   5    6   7    8   9     10
 * 
 * 以1为增量
 * 快速排序
 * -12,-2,0,1,3,4,5,10,23,31,898
 * 完成
 * 
 */

← css 开篇 →