Javascript实现冒泡排序与快速排序以及对快速排序的性能优化

dadong 发布于2019-08-23 15:08 / 3607人阅读

摘要：实现快速排序介绍通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

冒泡排序 介绍

重复遍历要排序的元素列，依次比较两个相邻的元素，前一个元素若比后一个元素大则互换位置。以升序排序为例，最大的元素会在第一次遍历后“冒泡”到数组的末端。假如数组长度为n，在n-1次遍历后可完成排序。

实现

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function bubbleSort(arr) {
  let time = arr.length - 1
  while (time) {
    let i = 0
    while (i arr[i+1]) [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      i ++
    }    
    time --
  }
}

bubbleSort(arr)

快速排序 介绍

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

实现

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function quickSort(arr) {
  if (arr.length <= 1) return arr
  let pivotVal = arr[0],
  smallers = [], 
  biggers = [], 
  idx = 1
  while (idx < arr.length) {
    if (pivotVal > arr[idx]) {
      smallers.push(arr[idx])
    } else {
      biggers.push(arr[idx])
    }
    idx ++
  }
  return quickSort(smallers).concat(pivotVal, quickSort(biggers))
}

quickSort(arr)

这种方法较好理解，就是找一个基准元素，一般是数组的第1位，然后遍历数组，比基准元素大的元素扔进去一个临时数组里，较小的扔进另一个临时数组里，最后把这两个数组和基准元素按顺序拼接起来。当然临时数组还要递归调用方法来对内部继续进行拆分，直到最后产生的临时数组长度为0或1为止。

接下来对此方法进行优化，毕竟这样一套递归下来，新建了不少临时数组，对性能会有一定的影响。

优化

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function quickSort2(arr, start, end) {
  while(start >= end) return
  let pivot = start,
  pivotVal = arr[pivot],
  idx = pivot + 1
  while (idx <= end) {
    if (arr[idx] < pivotVal) {
      pivot ++
      if (arr[pivot] != arr[idx]) {
        [arr[pivot], arr[idx]] = [arr[idx], arr[pivot]]
      }
    }
    idx ++
  }
  [arr[pivot], arr[start]] = [arr[start], arr[pivot]]
  quickSort2(arr, pivot + 1, end)
  quickSort2(arr, 0, pivot - 1)
}

quickSort2(arr, 0, arr.length-1)

原理就是以数组的第一个元素为基准元素，从第二个元素开始对基准元素进行比较，如果比基准元素小则让基准点前进一位，同时把现基准点上的值与对比元素的值对换。一次遍历下来后，现基准点所在的位置就是最后一个比基准元素小的元素所在的位置，右边是大于或者等于基准元素的元素，左边是小于基准元素的元素（除了第一位，第一位是基准元素），所以最后一步操作就是让现基准点上的元素和第一位上的元素（基准元素）互换，确保基准点和基准元素对应上。之后递归调用就可以完成。

快速排序，简单高效，但是当序列长度在5到25之间时，直接插入排序的速度比快速排序快至少10%， 改进后的快速排序，当数据规模小于25时，采用直接插入排序。

插入排序 介绍

当插入第i(i ≥ 1)个元素时，假设前面从arr[0]到arr[i-1]已经有序，那么只需将arr[i]和前面那些有序的数值进行比较，找到自己应该插入的位置即可，原来位置上的元素一次向后顺移。

实现

let arr = [0, 99, 2, 6, 1, 10, 2, 3, 1, 9, 0]

function insertSort(arr) {
  let idx = 1
  while(idx < arr.length) {
    while(idx > 0) {
      if (arr[idx] >= arr[idx-1]) break
      [arr[idx], arr[idx-1]] = [arr[idx-1], arr[idx]]    
      idx --
    }
    idx ++
  }
}

insertSort(arr)

云服务器 GPU云服务器最好的快速排序算法最快速的排序算法快速排序快速排序函数

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

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

JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法为王。想学好前端，先练好内功，内功不行，就...

zsy888 2019-08-26 10:27 评论0 收藏0
JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，...

canger 2019-08-26 10:15 评论0 收藏0
JavaScript各种排序算法的实现及其速度性能分析

摘要：今天我们来讨论的问题有两个如何用实现选择排序冒泡排序插入排序快速排序归并排序堆排序对生成的万个随机数进行排序，各个排序算法的性能分析。快速排序快速排序算法基本上是面试必考排序算法，也是传闻最好用的算法。今天我们来讨论的问题有两个：如何用JavaScript实现选择排序、冒泡排序、插入排序、快速排序、归并排序、堆排序；对生成的10万个随机数进行排序，各个排序算法的性能分析。创...

yuanxin 2019-08-20 19:03 评论0 收藏0
JS数据结构与算法_排序和搜索算法

摘要：上一篇数据结构与算法树写在前面这是学习数据结构与算法的最后一篇博客，也是在面试中常常会被问到的一部分内容排序和搜索。上一篇：JS数据结构与算法_树写在前面这是《学习JavaScript数据结构与算法》的最后一篇博客，也是在面试中常常会被问到的一部分内容：排序和搜索。在这篇博客之前，我每每看到排序头就是大的，心里想着类似冒泡排序，两层遍历啪啪啪就完事了，然后再也无心去深入研究排序相...

姘搁『 2019-08-23 16:26 评论0 收藏0