JavaScript排序算法

在我们的日常生活中，排序是经常会被使用到的，因此排序算法也会广泛的应用到解决日常问题上面。
所有的排序算法已经上传到了git的master/my_app/sort.html文件。

排序算法

在我们开始排序算法之前，先创建一个数组来表示待排序和搜索的数据结构。

function ArrayList(){
  var array = []; //(1)
  this.insert = function (item){  //(2)
  arry.push(item);
  };
  this.toString = function (){  //(3)
    return array.join();
  };
}

上面的数据结构中，(1)的作用是将项添加到数组里面。（2）是一个像数组中插入元素的方法，第三个方法是使用JavaScript原生的join方法，来拼接数组中的所有的元素，这样我们就可以通过调用该方法在浏览器的控制台轻松的打出结果了。

冒泡排序

我们在编程的过程中，最开始学的都是冒泡排序，因为它是排序算法最简单的，但是从运行的时间角度来看，冒泡的时间也是最差的。
冒泡排序的思路（从小到大排序）：冒泡排序是比较任何两个相邻的项，如果第一个比第二个大，交换他们的位置。元素项向上移动至正确的位置，就像气泡升至表面的样子，冒泡排序因此得名。

let arr = [5,4,3,2,1];
    let bubbleSort = function (arr){
        var length = arr.length;
        for(let i = 0;i < length; i++){
            for(let j = 0; j < length -1; j++){
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    };
let swap = function (array,index1,index2){
    var aux = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = aux;
};
bubbleSort(arr);

我们使用swap函数用来存储中间变量，传入的参数分别为数组，将要交换位置的两个数组的下标。现在我们看一下在当前数组的情况下冒泡排序的工作流程。

冒泡排序工作流程

在冒泡排序中我们注意到，在算法执行第二轮的时候，数字4和5的顺序已经是正确的顺序了，但是我们在后面还是一直将他们进行比较着，但是这个比较是不必要的，所以我们可以对冒泡排序进行简单的改进。
改进后的冒泡排序

let modifiedBubbleSort = function(arr){
    let length = arr.length;
    for(let i = 0; i < length; i++){
        for(let j = 0; j < length - 1-i ; j++){ //改变在这里
            if(arr[j] > arr[j+1]){
                swap(arr,j,j+1);
            }
        }
    }
}

如果内循环减去外循环中已经跑过的轮数，就可以避免不必要的循环，看一下改进后的算法的工作流程。

改进后的冒泡排序的原理

选择排序

思路：在数据结构中寻找最小值并将其放在位置的第一位，接着找到第二小的值放在第二位。
编程思路：声明一些将要咋算法内使用的变量，外循环(2)迭代数组，用来控制轮速(数组的第n个值 -- 下一个最小值)，假设本轮迭代的第一个值为数组的最小值，然后会跳出if的判断，因为第1个值为小值，所以不会进行交换顺序（如果有），内循环结束，接下来跑到了外循环中，然后一次遍历，直到外循环的

let selectionSort = function(){
    let length = arr.length,indexmin;  // (1)
        for(let i = 0; i < length - 1; i++){  //(2)
            indexmin = i;        //(3)
            for(let j = i; j < length; j++){ //(4)
                if(arr[indexmin] > arr[j]){  //(5)
                    indexmin = j; //(6)
                }
            }
            if(i !== indexmin){  //(7)
                swap(arr,i,indexmin)
            }
    }       
};

选择排序的原理

插入排序

思路：每次排一个数组，用这个方式来构建最后的排序数组。假设第一项已经排序了，接着，它和第二项进行比较，那么第二项是应该待在原来的位置还是再第一项之前呢？接下来，让我们看下面的算法，来进行具体的阐述。

let insertionSort = function(arr){
    let length= arr.length,
    j,temp;
    for(let i = 1; i<length; i++){
        j = i;
        temp = arr[i];
        while(j>0 && arr[j-1] >temp){
            arr[j] = arr[j -1];
            j--;
        }
        arr[j] = temp;
    }
}

排序的原理

对于上面的原理解释一下：
(1)3已经被排序，所以我们从第二个值5开始。3比5小，所以5待在原来的位置。3和5排序完毕。
(2)下一个待排序和插入到正确位置的值是1，5比1大，所以，5被移到了第三位去，我们检查一下1是否应该被插入到第二位，--1比3大吗？不，所以3被移到了第二位去，接着，我们的索引已经到了第一位，已经到了数组最开始的位置，所以1必须被插入到第一位，现在 1.3.5 都已经排序完毕了。
(3)4是保持在当前位置，还是移到索引比较低的位置呢？因为4比5小，所以，5移到了4的位置上面去，那么4应该被插入到索引为2的位置吗？4比3要大，所以4插入到了索引为3的位置。
(4)下一个插入的数字是2,5大于2，所以5后移，同理3,4 也要后移，知道和1进行比较，1<2,所以1插入到2的后面，致辞排序结束。
ps：排序小型数组的时候，此算法比选择排序和冒泡排序性能要好。

归并排序

归并排序是一种分治的算法，思想是将原数组且分为比较小的数组，直到小数组只有一个元素，接着将小数组合并为大数组，直到最后只有一个排序完毕的大数组。因为是分治法，所以归并排序也是递归的:

function mergeSort(arr) {  //采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
    var result = [];
    while (left.length >0 && right.length >0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length){
        result.push(left.shift());
    }
    while (right.length){
        result.push(right.shift());
    }
    return result;
}
let arr = [8,7,6,5,4,3,2,1];
let res = mergeSort(arr);
console.log(res);

思路：归并排序将大数组转换为多个小数组，直到只有一个项，因为是递归算法，所以我们需要一个停止的条件，在该递归算法中，停止的条件是数组的长度为1，如果是，直接返回这个长度为1的数组，因为它已经排序了。
如果数组长度比1大，那么我们就将其划分为小数组，为此，我们先找到数组的中间位，找到后，我们将数组划分为两个小数组，分别叫做left和right，接下来就是调用merge的函数，这个函数负责合并小数组来产生大的数组，一直到原始数组排序完毕，会返回一个排序过后的新的数组，我们将这个数组return出来，并打出，查看结果。
merge函数接受两个数组作为参数，并将它们归并至一个大数组，排序发生在归并的过程中，需要声明归并过程中腰创建的新数组以及需要进行迭代两个数组的变量。

归并排序过程图

快速排序

快速排序和归并排序一样，快速排序也是用分治的方法，将原始的数组划分为比较小的数组，但是它并没有像归并排序那样将他们划分开来。算法比较复杂，我们一步步拆分来看：
（1）首先从数组中选择中间一项作为主元
（2）创建两个指针，左边一个指向数组的第一项，右边指向数组的最后一项。移动左指针知道我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交换他们，重复这个过程，知道左指针超过了右指针，这个过程将使得比主元小的值都在主元之前，比主元大的元素都在后面，这一步叫做划分。
（3）接着，算法对划分后的小数组重复之前的过程，知道数组被完全排序。

let quickSort = function(arr){
    quick(arr,0,arr.length - 1);
}
let quick = function (arr,left,right){debugger
    let index;
    if(arr.length > 1){
        index = partition (arr, left,right);
        if(left < index -1){
            quick(arr, left,index -1);
        }
        if(index < right){
            quick(arr, index ,right);
        }
    }
};
let partition = function(arr,left,right){
    var pivot = arr[Math.floor((right + left)/2)],
        i = left;
        j = right;
        while (i <= j){
            while(arr[i] < pivot){
                i++;
            }
            while(arr[j] > pivot){
                j--;
            }
            if(i <= j){
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        return i ;
}

排序算法的第一轮过程详解 排序算法的第二轮过程详解 排序算法的第三轮过程详解 排序算法的第四轮过程详解 排序算法的第五轮过程详解 算法的时间复杂度和空间复杂度