资讯专栏INFORMATION COLUMN

基本算法学习之(二)快速排序与归并排序

Songlcy / 344人阅读

摘要:快速排序看名字知特点就是快效率高它是处理大数据最快的排序算法之一奇妙的记忆点内排序不稳定基本思想通过一趟排序把待排序记录分为独立的两部分其中一部分记录的关键字都比另一部分的关键字笑则分别对两部分继续进行排序以达到整个序列有序自己的理解其实就

快速排序(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 ]      */
记忆点

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

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

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

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/80445.html

相关文章

  • 基础算法习之(三):堆排序

    摘要:奇妙的记忆点不稳定内排序基本思想分为两步建堆与维持堆的性质首先我们要先理解堆是什么东西堆其实就是一个完全二叉树我们可以使用顺序表存储一个二叉树如下图所示来存储其中分为最大堆最小堆而最大堆就是上头大下头小最小堆则反之明白了堆的定义我们就可以开 奇妙的记忆点: 不稳定 内排序 基本思想: 分为两步,建堆与维持堆的性质,首先我们要先理解堆是什么东西.堆其实就是一个完全二叉树,我们可以使用...

    mrli2016 评论0 收藏0
  • 排序算法(Java)——那些年面试常见的排序算法

    摘要:下面会介绍的一种排序算法快速排序甚至被誉为世纪科学和工程领域的十大算法之一。我们将讨论比较排序算法的理论基础并中借若干排序算法和优先队列的应用。为了展示初级排序算法性质的价值,我们来看一下基于插入排序的快速的排序算法希尔排序。 前言   排序就是将一组对象按照某种逻辑顺序重新排列的过程。比如信用卡账单中的交易是按照日期排序的——这种排序很可能使用了某种排序算法。在计算时代早期,大家普遍...

    Harpsichord1207 评论0 收藏0
  • 归并排序 - Algorithms, Part I, week 3 MERGESORTS

    摘要:两个单元素数组的合并实际就是对这两个数进行了排序,即变为,同样再对后一组的两个数归并排序,即变为,再将两单元数组归并成四单元数组即和归并为。 前言 本周讲解两个50多年前发明,但今天仍然很重要的经典算法 (归并排序和快速排序) 之一 -- 归并排序,几乎每个软件系统中都可以找到其中一个或两个的实现,并研究这些经典方法的新变革。我们的涉及范围从数学模型中解释为什么这些方法有效到使这些算法...

    Jokcy 评论0 收藏0
  • 各种排序算法总结

    摘要:排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势。今天,来总结下各种排序算法。 排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势。今天,来总结下各种排序算法。 下面这个表格...

    null1145 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<