排序算法 - Githubissues

基础的排序算法

冒泡排序（BubbleSort）

冒泡排序是比较经典的算法之一，也是排序最慢的算法之一。冒泡排序的基本思路如下（升序排序）：

比较相邻的元素，如果第一个比第二个大，就交换它们两个位置；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样最终最大数被交换到最后的位置；
除了最后一个元素以外，针对所有的元素重复以上的步骤；

重复步骤1~3，直到排序完成。

// 冒泡排序
function bubbleSort ( data ) {
var temp = 0;
for ( var i = data.length ; i > 0 ; i -- ){
    for( var j = 0 ; j < i - 1 ; j++){
       if( data[j] > data[j + 1] ){
           temp = data[j];
           data[j] = data [j+1];
           data[j+1] = temp;
       }
    }
}
return data;
}
// 运行结果如下：
> var arr = [99,77,87,100, 6, 38, 69, 32, 2, 6, 9, 55, 69];
> bubbleSort(arr);
> [2, 6, 6, 9, 32, 38, 55, 69, 69, 77, 87, 99, 100]

选择排序（SelctionSort)

选择排序是一种比较简单直观的排序算法。它的算法思想是，从数组的开头开始遍历，将第一个元素和其他元素分别进行比较，记录最小的元素，等循环结束之后，将最小的元素放到数组的第一个位置上，然后从数组的第二个位置开始继续执行上述步骤。当进行到数组倒数第二个位置的时候，所有的数据就完成了排序。

选择排序同样会用到嵌套循环，外循环从数组第一个位置移到倒数第二个位置；内循环从第二个位置移动到数组最后一个位置，查找比当前外循环所指向的元素还要小的元素，每次内循环结束后，都会将最小的值放到合适的位置上。

//选择排序
function selectionSort( data ) {
    for( var i = 0; i< data.length ; i++){
        var min = data[i];
        var temp;
        var index = i;
        for( var j = i + 1; j< data.length; j++){
            if( data[j] < min ){
                min = data[j];
                index = j;
            }
        }

        temp = data[i];
        data[i] = min;
        data[index]= temp;
    }
    return data;
}

// 运行结果如下：
> var arr = [99,77,87,100, 6, 38, 69, 32, 2, 6, 9, 55, 69];
> selectionSort(arr)
> [2, 6, 6, 9, 32, 38, 55, 69, 69, 77, 87, 99, 100]

插入排序（insertionSort）

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序的实现过程：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到下一位置中
重复步骤2~5

//插入排序

function insertionSort( data ) {
    var len = data.length;
    for (var i = 1; i < len; i++) {
        var key = data[i];
        var j = i - 1;
        while ( j >= 0 && data[j] > key) {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = key;
    }
    return data;
}

在运算速度上，冒泡排序是最慢的，插入排序是最快的，我们可以在运行的过程中通过 console.time('sortName') 和 console.timeEnd('sortName') 来看他们的效率如何

mamba-1024 / myblog

排序算法 #12

基础的排序算法

冒泡排序（BubbleSort）

选择排序（SelctionSort)

插入排序（insertionSort）