JavaScript 之排序算法学习

整理一下几种基础的排序算法：

冒泡排序
选择排序
插入排序
快速排序
归并排序
堆排序

冒泡排序

【原理】

依次比较相邻的两个数，如果前者比后者大，则交换顺序。
由于每次循环后，当前最大数已确定，所以下次只需对最大数之前位置的数进行循环冒泡。

【代码】

function bubbleSort(arr){
    var len = arr.length;
    for(var i = 0; i< len-1; i++){ // 外层循环 n-1 次
        for(var j = 0 ; j< len-1-i; j++){ // 内存循环，比较最大数之前的序列
            if(arr[j] > arr[j+1]){ // 满足条件就进行交换
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

【图示】

冒泡排序

选择排序

【原理】

每次循环找出当前序列中的最大值，并与最后位置的值交换（或者找出最小值，与最前位置交换）
每次循环后，能找出本次循环中最大的数排在后面。所以需要循环n - 1次（外层循环）。（最小值同理）
由于每次循环后，当前最大数已确定，所以下次只需对最大数之前位置的数进行循环冒泡。（最小值同理）

【代码】

//选择最大值进行排序
function selectionSort(arr){
    var len = arr.length;
    for(var i = 0; i < len-1; i++){ // 外层循环 n-1 次
        var maxIndex = 0;
        var max = arr[0];  //每次循环最值的初始值都为第一个元素的值
        for(var j = 0; j< len-i; j++){ // 每次对len-i个元素进行最大值选取
            if(arr[j] > max){ // 满足条件就更新最大值，并记录位置
                max = arr[j];
                maxIndex = j;
            }
        }
        // 交换最大值
        var temp = arr[len-1-i];
        arr[len-1-i] = max;
        arr[maxIndex] = temp;
    }
    return arr;
}
//选择最小值进行排序
function selectionSort2(arr){
    var len = arr.length;
    for(var i = 0;i < len-1;i++){ // 外层循环 n-1 次
        var min = arr[i];
        var minIndex = i;  //每次循环最小值的初始值都为开始元素的值
        for(var j = i; j<len;j++){  // 每次从第i个元素开始后的元素进行最小值选取
            if(min > arr[j]){ // 满足条件就更新最小值，并记录位置
                min = arr[j];
                minIndex = j;
            }
        }
        // 交换最小值
        var temp = arr[i];
        arr[i] = min;
        arr[minIndex] = temp;
        console.log(arr);
    }
    return arr;
}

【图示】

选择最小值排序

选择排序

插入排序

【原理】

把数组分为[已排序]和[未排序]两部分，初始状态第一个数为[已排序]，其余为[未排序]
每次循环从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置

【代码】

function insertSort(arr){
    var len = arr.length;
    for(var i = 1; i < len; i++){ // 从第1个元素开始，而非从第0个开始，共循环 n-1 次
        var preIndex = i - 1;  //设置当前位置的前一个位置
        var current = arr[i]; //记录当前位置的值，即[未排序]部分的第一个数
        while(preIndex >= 0 && arr[preIndex] > current){ // 如果[未排序]部分的值比当前值大，就依次向后挪一位
            arr[preIndex+1] =  arr[preIndex];
            preIndex--;  
        }
        arr[preIndex+1] = current; // 进行赋值
    }
    return arr;
}

【图示】

插入排序

快速排序

【原理】

以一个数为基准(中间的数或第一个数)，比基准小的放到左边，比基准大的放到右边
再按此方法对这两部分数据分别进行快速排序（递归进行）
不能再分后退出递归，并重新将数组合并

【代码】

function quickSort(arr){
    var len = arr.length;
    if(len <= 1){ //终止递归的条件
        return arr; 
    }
    var pivot = arr.splice(0,1)[0]; //以第一个数为基准
    
    //var pivotIndex = Math.floor(arr.length / 2);  
    //var pivot = arr.splice(pivotIndex, 1)[0]; 以中间数为基准
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) { // arr已经改变，不能直接用len
        if(arr[i] > pivot){
            right.push(arr[i]);
        }else{
            left.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot],quickSort(right)); //合并数组
}

【图示】

以中间数为基准排序

快速排序

归并排序

【原理】

不断将数组对半分，直到每个数组只有一个
将分出来的部分重新合并
合并的时候按顺序排列

【代码】

function mergeSort(arr){
    var len = arr.length;
    if(len <= 1){ //终止递归的条件
        return arr;    
    }
    var midIndex = Math.floor(len/2);  //计算长度中间值
    var left = arr.slice(0,midIndex);  //对半分割数组
    var right = arr.slice(midIndex);
    return merge(mergeSort(left),mergeSort(right)); //将对半分的数组进行重新排序
}
function merge(left,right){
    var leftLen = left.length;
    var rightLen = right.length;
    var leftIndex = 0;
    var rightIndex = 0;
    var result = [];
    while(leftIndex < leftLen && rightIndex < rightLen){
        if(left[leftIndex] < right[rightIndex]){
            result.push(left[leftIndex++]);
        }else{
            result.push(right[rightIndex++]);
        }
    }
    // 将可能剩余的添加到result中
    return result.concat(left.slice(leftIndex),right.slice(rightIndex));
}

【图示】

归并排序

堆排序

堆，包括二叉堆，二项式堆，斐波纳契堆等。这里的堆排序就是指二叉堆的排序，一般将二叉堆就简称为堆。

二叉堆是完全二叉树或者近似完全二叉树。

二叉堆满足两个特性：

父节点的值总是大于（或小于）其（左、右）子节点的值。
每个节点的左子树和右子树都是一个二叉堆（最大堆或最小堆）。

【关系】

堆的存储

结论：节点i的左子节点索引为 2 * i + 1，右子节点索引为 2 * i + 2，父节点索引为 Math.floor((i - 1) /2)。

证明：

假设节点i在堆的第m层（m>=0）的第k个位置（k>=1），则

i = 2^0 + 2^1 + ...+ 2^(m-1) + k - 1

（i是索引，从0开始，所以要减1），所以节点i的左子节点位置 = 这m层节点总数 + （k-1）*2 + 1 - 1，（前 k-1 个节点每个有两个子节点，索引同样要减1），则

left = 2^0 + 2^1 + ...+ 2^(m-1) + 2^ m + (k-1) *2 = 2*i + 1，
right = left + 1 = 2*i + 2。

现在根据子节点反推父节点：

已知 left = 2*i + 1 ，则 i_1 = (left - 1) / 2；
已知 right = 2*i + 2 ，则 i_2 = (right - 2) / 2；

那么以哪个为准呢？

很明显，i_1 > i_2，而且 right为偶数，所以 Math.floor(i_1) = i_2。
这样无论子节点是奇数还是偶数，都可以用Math.floor(i_1)求出。

证毕。

【原理】

假设一个m层的堆（m从0开始取值），遍历有子节点的节点i，从而建立最大堆（最小堆）。
最后一个节点索引为 len-1，那么它的父节点索引为 Math.floor((len - 1) /2)。
所以 0 <= i <= Math.floor((len - 1) /2)
建立最大堆的过程中，对堆进行调整，找出最大值，放在父节点。
最大堆建立完成后，每次循环取值根节点的值与末尾节点交换（此时跟节点是当前最大值），堆节点数目减1，重新调整最大堆，直至只剩最后一个元素。需要循环 len - 1次。

【代码】

var len;
function headSort(arr){    
    len = arr.length;
    //建立最大堆
    for(var i = Math.floor((len-1)/2); i >= 0; i--){
        heapify(arr,i);    //调整堆
    }
    //每次循环取值最大值放在末尾
    for (var j = arr.length-1; j > 0; j--) {
        swap(arr,0,j);
        len--;
        heapify(arr,0); //调整堆
    }
    return arr;
}
function heapify(arr,i){
    //当前节点索引为 i，节点i的左子节点的索引为 2i+1，节点i的右子节点的索引为 2i+2，
    //设当前节点索引为最大值节点索引（即当前节点为最大值节点）
    var largest = i;
    var left = 2*i + 1;
    var right = 2*i + 2;
    if(left < len && arr[left] > arr[largest]){ //比较左节点，满足条件则更改最大值节点索引
        largest = left;
    }
    if(right < len && arr[right] > arr[largest]){
    //比较右节点，满足条件则更改最大值节点索引
        largest = right;
    }
    if(largest != i){ 
        swap(arr,i,largest); //交换值
        heapify(arr,largest); //调整堆
    }
}
function swap(arr,i,j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

【图示】

堆排序

算法的复杂度

算法复杂度分为时间复杂度和空间复杂度。

时间复杂度：度量算法执行的时间长短。

空间复杂度：算法在计算机内执行时所需存储空间的度量。

排序算法的复杂度

n: 数据规模
k: “桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
稳定性：排序后2个相等键值的顺序和排序之前它们的顺序相同

参考文章：

注：文章中的排序示意图来自于网络，如侵删。

冒泡排序
选择排序
插入排序
快速排序
归并排序
堆排序
算法的复杂度

冒泡排序

选择排序

插入排序

快速排序

归并排序

堆排序

算法的复杂度

FRIENDS