快速排序(Quick Sort)

看名字知特点,就是快,效率高.它是处理大数据最快的排序算法之一.

奇妙的记忆点:

内排序

不稳定

基本思想

通过一趟排序把待排序记录分为独立的两部分,其中一部分记录的关键字都比另一部分的关键字笑,则分别对两部分继续进行排序,以达到整个序列有序.

自己的理解:

其实就是用分治法的思路,将一个数组分为两半,进行无线分割排序.

首先在数列中取一个值,成为"关键字/基准"(pivot);

然后比它小的放前面,大的放后面,相同的话随便放.

递归的把我们分为两半的数组再次分半排序.

快速排序(代码)

//方法一function quickSort(array, left, right) {//传入参数为数组,left,right为排序区域下标    console.time('1.快速排序耗时');    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') {//判断传入参数的正确性        if (left < right) { //正确性判断            var x = array[right], i = left - 1, temp;//x变量为待排序数组末尾            for (var j = left; j <= right; j++) {    //从左到右                if (array[j] <= x) {                    i++;//注意i先增在交换                    temp = array[i];                    array[i] = array[j];                    array[j] = temp;                }            }            quickSort(array, left, i - 1);            quickSort(array, i + 1, right);        }        console.timeEnd('1.快速排序耗时');        return array;    } else {        return 'array is not an Array or left or right is not a number!';    }}//方法二var quickSort2 = function(arr) {    console.time('2.快速排序耗时');　　if (arr.length <= 1) { return arr; }　　var pivotIndex = Math.floor(arr.length / 2);　　var pivot = arr.splice(pivotIndex, 1)[0];　　var left = [];　　var right = [];　　for (var i = 0; i < arr.length; i++){　　　　if (arr[i] < pivot) {　　　　　　left.push(arr[i]);　　　　} else {　　　　　　right.push(arr[i]);　　　　}　　}console.timeEnd('2.快速排序耗时');　　return quickSort2(left).concat([pivot], quickSort2(right));};var arr=[3,49,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]console.log(quickSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

记忆点

best condition: T(n) = O(nlog n)

baddest condition: T(n) = O(n^2)

average condition: T(n) = O(nlog n)

归并排序(Merge Sort)

不受输入数据影响,但是表现比选择排序好.代价是需要额外的内存空间.

奇妙的记忆点:

外排序(需要额外的内存空间)

稳定的排序算法(排序后元素原始顺序不会变化)

基本思想:

分治法(Divide and Conquer)

将已有序的子序列合并,从而得到完全有序的序列.也称为2-路归并.

归并排序:代码

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 = [];//新建变量用于保存结果    console.time('归并排序耗时');    while (left.length && right.length) { //当左区间右区间存在时        if (left[0] <= right[0]) {  //将区间中较小的一位从区间数组中放到结果数组中.            result.push(left.shift());        } else {            result.push(right.shift());        }    }    //下面两个while是为了解决遗留元素问题    while (left.length)         result.push(left.shift());    while (right.length)        result.push(right.shift());    console.timeEnd('归并排序耗时');    return result;//返回结果}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(mergeSort(arr));/*10次归并归并排序耗时: 0ms归并排序耗时: 0ms归并排序耗时: 0ms归并排序耗时: 0ms归并排序耗时: 0ms归并排序耗时: 0ms归并排序耗时: 0ms归并排序耗时: 0ms归并排序耗时: 0ms归并排序耗时: 0ms[ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]      */