野生前端的数据结构练习（9）冒泡排序，选择排序，插入排序

2018-11-26 09:34:43

一.冒泡排序

bubble sort的是最基本的算法，被誉为永远会被考从来不被用的算法，基本原则是大数右移，每轮遍历后最右侧的数是最大的，所以下一轮循环时可不予考虑，时间复杂度为O（n^2）。

function bubbleSort(arr) {    let length = arr.length;    for(let i = length - 1; i > 1; i--){        for(let j = 0; j < i ;j++){            if (arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
            }
        }
    }
}function swap(arr, a, b) {    let temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

二.选择排序

selection sort的基本原则是把数放在对的位置上，外层遍历依次指向每个位置，内层遍历从剩余的元素中寻找最小值放在该位置，时间复杂度O(n^2)。

/**
 * 选择排序示例代码
 */function selectionSort(arr) {    let length = arr.length;    for(let pos = 0 ; pos < length ; pos++){        let tempMin = pos;//用于记录当前内层循环找到的最小值的下标
        for(let j = pos+1 ; j < length ;j++){            if (arr[j] < arr[tempMin]) {
                tempMin = j;
            }
        }
        swap(arr, pos, tempMin);
    }
}function swap(arr, a, b) {    let temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

三.插入排序

insertion sort的基本原则是小数左移，即每轮循环结束后，外层循环指向位置左侧的片段都是已经完成排序的，时间复杂度也为O(n^2)。

/**
 * 插入排序示例代码
 */function insertionSort(arr) {    let length = arr.length;    for(let pos = 1 ; pos < length ; pos++){        for(let j = pos ; j > 0 ; j--){            if (arr[j] < arr[j-1]) {
                swap(arr, j, j-1);
            }
        }
    }
}function swap(arr, a, b) {    let temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

四. 一些需要注意的点

1.运行时间

时间复杂度仅仅代表算法本身随计算规模的增长时其自身运算量的增长速度，是一种抽象数学符号表达，并不代表程序的运行时间，在程序中对比测试3种算法时，其运行时间可能出现较大差异，这并不影响其在算法分析层面的时间复杂度定义。

2.基本优化

基于时间复杂度与程序运行效率并不绝对一致这样的前提，上面的三种基本算法在不改变算法思想的前提下仍然存在优化空间，例如基础插入排序中，内层循环所做的工作可以描述为为当前元素在左侧已排序列中找到正确的位置，换句话说，找到正确位置之前，通过swap( )方法交换相邻元素的位置的动作是可以不必执行的。

当针对更大的问题规模时，从基本算法出发，融入其他诸如“分治”，“减治”的思想，就可以得到更高级的算法，时间复杂度也更低。

3. 如何区分三种基础排序算法

对于三种基本排序算法还不是很清楚的读者，可以自行搜索“图解算法”相关的博文进行查看，这三种算法的时间复杂度是一样的（都是两层循环），只需要区分其主要排序思想的原则差异，并不难记忆。

• 冒泡排序——大数右移

• 选择排序——按位入坑

• 选择排序——小数左移