资讯专栏INFORMATION COLUMN

算法学习笔记:排序算法(二)

William_Sang / 2086人阅读

摘要:上一篇中已经介绍了几个简单的排序算法,这一篇文章我将继续向大家介绍排序算法相关的内容,本篇的会介绍希尔排序快速排序归并排序以及分治算法的思想,希望通过本文章能够加深大家对排序算法的理解。

上一篇中已经介绍了几个简单的排序算法,这一篇文章我将继续向大家介绍排序算法相关的内容,本篇的会介绍希尔排序、快速排序、归并排序以及分治算法的思想,希望通过本文章能够加深大家对排序算法的理解。

希尔排序

希尔排序又叫缩小增量排序,希尔排序的主要思想是使数组中任意相隔h的元素都是有序的,h就是希尔增量,实现的希尔排序的方法就是:对相隔h的元素进行分组,对每组进行使用插入排序,使子序列变成有序序列,增量逐渐递减一直到1为止,在例子中我将h增量设为array.length/2,递减的过程就是不断除以2,是不是被我的解释弄的有点晕,让我们先来看一个演示过程理解一下:

如图所示,一共15个元素,增量就是15/2为7,第一轮的分组即为[2, 26, 48],[44, 26],[38, 2],[5, 46],[47, 4],[15, 19],[36, 50],然后进行插入排序,得到新的序列[ 3, 27, 2, 5, 4, 15, 36, 26, 44, 38, 46, 47, 19, 50, 48 ],然后在进行分组,增量为7/2为3:

第二轮分组[3, 5, 36, 2, 19],[44, 47, 26, 46, 50], [38, 15, 27, 4, 48],然后进行插入排序,得到序列[ 3, 4, 2, 5, 26, 15, 19, 27, 44, 36, 46, 47, 38, 50, 48 ],然后再进行分组,增量为3/2为1,再插入排序得到的就是一个有序序列了,最好让我们来看具体的代码实现:

function shellSort(arr) {
  var n = arr.length
  for (var gap = parseInt(n/2); gap > 0; gap=parseInt(gap/2)) {
    for (var i=gap; i temp) {
        arr[j+gap] = arr[j]
        j = j - gap
      }
      arr[j+gap] = temp
    }
  }
  console.log(arr)
}
shellSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])

其实希尔排序也不难,只要按照上面的分解图示一步一步的理解去编写,相信大家都能写得出来,上面这种形式的增量设置就是二分的形式设置,然后插入排序,还有一种希尔排序的写法就是自定义增量,然后子序列里的元素两两比较,来看具体代码:

function shellSort(arr) {
  var n = arr.length, gap = 1
  while (gap < n / 3) {
    gap = gap * 3 + 1
  }
  for (gap; gap > 0; gap=parseInt(gap/3)) {
    for (var i=gap; i= 0; j-=gap) {
        if (arr[j] > arr[j+gap]) {
          var temp = arr[j+gap]
          arr[j+gap] = arr[j]
          arr[j] = temp
        }
      }
    }
  }
  console.log(arr)
}
shellSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])

希尔排序更高效的原因在于它权衡了子数组的规模和有序性,各个子数组都很短,排序之后的子数组都是部分有序的,因此在希尔排序的效率要比插入排序高。

分治法

在介绍归并排序和快速排序有必要先介绍一下分治法相关的内容,为什么呢?因为归并排序和快速排序都是分治法的典型应用。
分治法的设计思路就是:将一个大问题分解成若干个规模娇小的相同子问题,这些子问题互相独立且与原问题形式相同,递归地解决这些子问题,然后将各个子问题的解合并得到原问题的解
分治法所能解决的问题一般有如下几个特点:

把该问题缩小到一定规模就可以容易解决

该问题可以被分解为若干个规模较小的相同问题

利用该问题的子问题的解向上合并可以得到该问题的解

该问题分解出的子问题是相互独立的

归并排序

归并排序就是分治法的典型应用之一,归并排序的实现有两种,一种是自顶向下的归并排序,另一种就是自底向上的归并排序。

自顶向下的归并排序

向来看第一种,自顶向下的归并排序的实现思路是不断二分,然后对二分后的最小序列分别进行排序后,再将排序后的结果向上合并得到最终的有序数组,让我们先通过一个树结构来理解归并排序的过程:

从图中可以看到将一个数组0-14的元素不断二分,分到最后一层,然后互相比较,得到新的有序序列,然后向上合并,在进行比较,不断反复,合并出最终的有序序列,这就是自顶向下的归并排序的思路,通过这个思路你是否能自己写出排序的方法呢?

好了,接下来就让我们看看具体的代码实现:

function sort(arr) {
  var n = arr.length
  if (n < 2) return arr
  var mid = Math.ceil(n / 2)
  var left = arr.slice(0, mid)
  var right = arr.slice(mid)
  return merge(sort(left), sort(right));
}

function merge(left, right){
  var result = []
  while (left.length && right.length) {
    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;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(sort(arr))

代码实现是不是很容易理解呢?相信大家经过仔细的思考过后都能看得懂,为了方便更好的理解,来看一下动图的排序过程:

自底向上的归并排序

自底向上的归并排序思路是将长度为n的数组看成n个长度为1的数组,然后两两向上归并排序,得到新的数组,不断向上归并排序,直到得到长度为n的数组,这样的排序比之前自顶向下的排序代码要少,下面来看具体的代码实现:

function merge(arr, start, mid, end){
  var i = start, j= mid + 1, copy = []
  for (var k = start; k <= end; k++) {
    copy[k] = arr[k]
  }
  for (var k = start; k <= end; k++) {
    if (i > mid) { // 左边取完取右边的元素
      arr[k] = copy[j]
      j++
    } else if (j > end) { // 右边取完取左边的元素
      arr[k] = copy[i]
      i++
    } else if (copy[j] < copy[i]) { // 右边的元素小于左边的元素,取右边的元素
      arr[k] = copy[j]
      j++ 
    } else { // 左边的元素小于右边的元素,取左边的元素
      arr[k] = copy[i]
      i++
    }
  }
  console.log(arr)
}

function sort(arr) {
  var n = arr.length
  for (var i = 1; i < n; i = i + i) { // i子数组的大小
    for (var j = 0; j < n - i; j = j + i + i) { // j数组的索引
      var start = j
      var end = Math.min(j + i + i - 1, n-1)
      var mid = parseInt((start + end) / 2)
      merge(arr, start, mid, end)
    }
  }
}

var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
sort(arr)

为了方便理解,已经在代码中加了必要的注释,可能这段代码比之前的要难理解一些,需要大家耐心多花一些时间去理解

快速排序

快速排序也是一种分治的排序算法,由于它实现简单并且效率比一般的排序算法高,因此,它的应用范围非常广泛,接下来让我们来看快速排序的排序过程:

将数组的第一个元素做为基准,从数组末尾开始找比基准小的数,找到就停下来,记下索引j,然后从基准右边开始找比基准大的数找到停下来,记下索引i,然后交换i和j上的元素,得到数组:

然后继续从44的位置开始找比基准3小的一直移动到2,此时索引i和索引j相等,将基准3和i、j对应的值交换位置得到:

此时基准数3前面的元素都是比它小的数,后面元素都是比它大的数,然后从基准数前后拆成两个数组,在递归执行前面同样的操作。
看来上面的排序过程,你是不是有代码的实现了呢?可以先试着写一下实现的代码,这样更容易理解,接下来就让我来看一下具体代码:

function sort(arr, left, right) {
  var temp = arr[left],i = left, j = right, t;
  if (left < right) {
    while (i != j) {
      while (arr[j] >= temp && i < j) {
        j--
      }
      while (arr[i] <= temp && i < j) {
        i++
      }
      if (i < j) {
        t = arr[i]
        arr[i] = arr[j]
        arr[j] = t
      }
    }
    arr[left] = arr[i]
    arr[i] = temp
    sort(arr, left, i - 1)
    sort(arr, i + 1, right)
  }
  return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(sort(arr, 0, arr.length - 1))

看了代码之后是不是觉得并不难呢?这种快速排序的实现其实有一个问题不知道大家注意到没有,当数组中有多个重复元素的时候,重复的元素只要排了一个就不需要重复排了,但是这中快速排序的实现并没有考虑这种情况,即便重复的元素还是会执行排序,因此有人提出了更优的快速排序方法“三向切分的快速排序”,让我们先来看代码实现有什么不同:

function sort(arr, left, right) {
  var temp = arr[left],i = left, j = right,k = left + 1, t;
  if (left < right) {
    while (k <= j) {
      if (arr[k] < temp) {
        t = arr[k]
        arr[k] = arr[i]
        arr[i] = t
        i++;
        k++;
      } else if (arr[k] > temp) {
        t = arr[k]
        arr[k] = arr[j]
        arr[j] = t
        j--;
      } else {
        k++;
      }
    }
    sort(arr, left, i - 1)
    sort(arr, j + 1, right)
  }
  return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48,44,38];
console.log(sort(arr, 0, arr.length - 1))

总体思路和之前的一样保证基准值前面的比它小后面的比它大,唯一不同的地方就是用了一个临时下标k去作比较,把小的丢到基准值前面,大的值就和末尾的值交换,得到新值再与基准值比较,当与基准值相等的时候,就只需要将临时下标的值+1而不需要排序了

总结

这篇文章详细介绍了希尔排序、归并排序、快速排序这三种排序的思想和实现方式,希望大家看完之后都能自己去多实践,多思考,算法还是需要自己多动手,否则光看作用不大。
如果有错误或不严谨的地方,欢迎批评指正,如果喜欢,欢迎点赞收藏

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

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

相关文章

  • CSS技巧

    摘要:技巧使你的更加专业这是上关于技巧的一篇译文,另外你也可以在本项目看到原文。列举了一些很实用的技巧,比如给空内容的标签添加内容,逗号分隔列表等等。排序算法看源码,把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。 成为专业程序员路上用到的各种优秀资料、神器及框架 成为一名专业程序员的道路上,需要坚持练习、学习与积累,技术方面既要有一定的广度,更要有自己的深度。 Java...

    DangoSky 评论0 收藏0
  • CSS技巧

    摘要:技巧使你的更加专业这是上关于技巧的一篇译文,另外你也可以在本项目看到原文。列举了一些很实用的技巧,比如给空内容的标签添加内容,逗号分隔列表等等。排序算法看源码,把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。 成为专业程序员路上用到的各种优秀资料、神器及框架 成为一名专业程序员的道路上,需要坚持练习、学习与积累,技术方面既要有一定的广度,更要有自己的深度。 Java...

    zgbgx 评论0 收藏0
  • 算法学习笔记排序算法(一)

    摘要:如果有错误或不严谨的地方,欢迎批评指正,如果喜欢,欢迎点赞收藏 算法对大多数前端工程师来说都是一个比较不愿意提及的话题,因为学了,感觉在工作中直接应用的场景不多,不学,大厂面试必考算法,总结来说就是:没有学习算法的源动力,为面试学习算法总不会令人动力去学习,没有动力想要学好算法自然也很难,对我来说,学习算法的动力就是希望写出更高效率的代码,更好的理解各种前端框架的设计思路,因此,后面会...

    renweihub 评论0 收藏0
  • 数据结构与算法学习笔记 - 优先队列、叉堆、左式堆

    摘要:模型优先队列是允许至少下列两种操作的数据结构以及找出返回并删除优先队列中最小的元素。左式堆也是二叉树,左式堆和二叉堆的唯一区别是左式堆不是理想平衡,而实际上趋向于非常不平衡。事实上,沿左式堆的右路径是该堆中的最短路径。 6.1 模型 优先队列是允许至少下列两种操作的数据结构:insert 以及 deleteMin(找出、返回并删除优先队列中最小的元素)。 insert 操作等价于 en...

    SunZhaopeng 评论0 收藏0

发表评论

0条评论

William_Sang

|高级讲师

TA的文章

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