vlambda博客
学习文章列表

排序算法是日常使用最频繁的，工作中很多复杂的场景都需要用到排序，如将数据排序后再做查找，分析，统计等处理。

冒泡排序

基本思想：

• 基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。

• 直观表达，每一趟遍历，将一个最大的数移到序列末尾。

算法描述：

比较相邻的元素，如果前一个比后一个大，交换之。

第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。

第二趟将第二大的数移动至倒数第二位

代码可视化：

冒泡排序

代码实现：

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

选择排序

首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到第二个元素位置。以此类推，直到所有元素均排序完毕。

算法描述：

1. 在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。

2. 第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。

3. 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。

算法可视化：

选择排序

代码实现：

var example=[8,94,15,88,55,76,21,39];
function selectSort(arr){
    var len=arr.length;
    var minIndex,temp;
    console.time('选择排序耗时')；
    for(i=0;i<len-1;i++){
        minIndex=i;
        for(j=i+1;j<len;j++){
            if(arr[j]<arr[minIndex]){
                minIndex=j;
            }
        }
    temp=arr[i];
    arr[i]=arr[minIndex];
    arr[minIndex]=temp;
    }
    console.timeEnd('选择排序耗时');
    return arr;
}
console.log(selectSort(example));

选择排序与冒泡排序区别：

• 冒泡排序是左右两个数相比较，而选择排序是用后面的数和每一轮的第一个数相比较；

• 冒泡排序每轮交换的次数比较多，而选择排序每轮只交换一次；

• 冒泡排序是通过数去找位置，选择排序是给定位置去找数；

• 当一个数组遇到相同的数时，冒泡排序相对而言是稳定的，而选择排序便不稳定；

• 在时间效率上，选择排序优于冒泡排序。

其它说明

• 时间复杂度指的是一个算法执行所耗费的时间。

• 空间复杂度指运行完一个程序所需内存的大小。

• 稳定指，如果a=b，a在b的前面，排序后a仍然在b的前面。

• 不稳定指，如果a=b，a在b的前面，排序后可能会交换位置。