排序算法javascript的实现与讲解

冒泡的原理是让最大元素或者最小元素”浮起来“

 

思路

依次比较相邻的两个数，将小数放在前面，大数放在后面。

 

step1：比较第1个和第2个数，将小数放前，大数放后。比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。

step2：在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。

如此下去，重复以上过程，直至最终完成排序。

由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

function bubble_sort(array) {
    var l = array.length;
    for (var i = 0; i < l-1; i++) {
        //注意我们只需要循环到倒数第二即可。因为这里取的任意一位数都是跟后面一位数做比较的。
        for (var j = 1; j < l-i; j++) {
            //内嵌交换的次数是从第一个数比较到倒数第(总长减n)个数。
            if (array[j] < array[j - 1]) {
                //发现前一位大于后一位数时
                array[j] = [array[j - 1], array[j - 1] = array[j]][0];
                //在这里交换元素，巧用 b=[a,a=b][0]互换变量方法
            }
        }
    }
    return array;
}

动画效果：

选择排序原理与冒泡非常相似，不同的是只有找到目标才交互元素。这也是一种简单的排序算法。

 

思路

循环把最小或最大的元素找出来，扔到数组里的一端，以此类推。

 

非常简单，就是我们摸牌插牌的步骤！

 

思路

 

先建一个空数组A，然后循环原数组每次取一个数出来。从A数组最后一个数作比较，发现比这个数还小时，就插入到当前，否则当前的数向后移动一个位置，然后继续向前一位比较。每次比较数组都增大一个元素。

function insert_sort(array){
    var l = array.length,arr = [];//新建一个空数组
    for(var i = 0 ;i < l; i++){
        var v = array[i];//循环整个数组，一次取一位数出来作比较
        for(var j = arr.length; j>=0; j--){
            if(j == 0){
                arr[0] = v;//如果第一次比较或者是v小于数组的任何一位数时
            }else{
                if(v >= arr[j-1]){
                    arr[j] = v;//发现了不比v小的数，就替换当前的位置
                    break;//并跳出循环
                }else{
                    arr[j] = arr[j-1];//新数组中每个比v大的数都向后移动一位
                }
                //arr.splice(j-1,0,v);break;等同此功能
            }
        }
    }
    return arr;
}

动画效果：

快速排序是目前最强大的排序算法，算法利用了递归的思想。

 

思路

 

function quick_sort(arr) {
    var l = arr.length;//缓存数组长度
    if(arr.length <= 1){return arr} //如果长度比1还小就不再排序了
    var num = Math.floor(arr.length / 2);//取数组中间的那个数。注意length/2不一定是整数，用Math.floor取整
    var numValue = arr.splice(num, 1)[0];//利用splice方法，取一个基准元素出来，注意语法
    var left  = [];//创建左边基准容器
    var right = [];//创建右边基准容器
    for (var i = 0; i < l - 1; i ++) {
    //开始遍历数组 必须 -1 因为已经截取了一个中间值
        arr[i] < numValue ? left.push(arr[i]) : right.push(arr[i]);
        //相对于基准元素，比它小的在左边，比它大的在右边。
    }
    return quick_sort(left).concat([numValue], quick_sort(right));
    //递归，继续对左右数组进行操作。
}