回顾Quick Sort(Javascript 实现)

Introduction

QuickSort的时间复杂度渐近函数虽然不能达到MergeSort般的O(nlgn),但因其良好的时间常量以及平均运行时间而被广泛使用。
下图解释了QuickSort的过程。

作为一种典型的分治法，QuickSort选取某一特殊点作为支点(pivot)，并根据目标区域元素大小较于支点作为重新分配元素位置的基准，以此为分。而不断再遍历支点两边的区域，作为治。

First Implementation

根据分治法的原理图形，于是有了下面的第一个实现。

  function QuickSort(array, bottomIndex, topIndex){if(bottomIndex >= topIndex) {return}var middleIndex = Arrange(array, bottomIndex, topIndex)QuickSort(array, bottomIndex, middleIndex - 1)QuickSort(array, middleIndex + 1, topIndex)}function Arrange(array, bottomIndex, topIndex){var middleIndex = topIndexvar rightMostValue = array[middleIndex]var length = topIndex - bottomIndex + 1var valuesLowerThanPivot = []var valuesHigherThanPivot = []//Do not compare itself, that's why minus 1for(var i = 0; i < length - 1; i++) {if(array[bottomIndex + i] <= rightMostValue) {valuesLowerThanPivot.push(array[bottomIndex + i])}else {valuesHigherThanPivot.push(array[bottomIndex + i])}}var length = valuesLowerThanPivot.lengthfor(var i = 0; i < length; i++) {array[bottomIndex + i] =  valuesLowerThanPivot[i]}middleIndex = bottomIndex + lengtharray[middleIndex] = rightMostValuevar length = valuesHigherThanPivot.lengthfor(var i = 0; i < length; i++) {array[middleIndex + 1 + i] =  valuesHigherThanPivot[i]}return middleIndex}//testCasevar array = [1, 3, 8, 9, 2, 4, 6, 19, 88, 77, 11]QuickSort(array, 0, array.length - 1)//The result should be [1, 2, 3, 4, 6, 8, 9, 11, 19, 77, 88]console.log(array)

功能是实现了，但是代码还可以改进很多，我们可以将目标区域分组化。

Second Implementation

  function QuickSort(array, bottomIndex, topIndex){if(bottomIndex >= topIndex) {return}var middleIndex = Arrange(array, bottomIndex, topIndex)QuickSort(array, bottomIndex, middleIndex - 1)QuickSort(array, middleIndex + 1, topIndex)}function swapElements(array, indexA, indexB){var temp = array[indexA]array[indexA] = array[indexB]array[indexB] = temp}function Arrange(array, bottomIndex, topIndex){var rightMostValue = array[topIndex]var length = topIndex - bottomIndexvar lGroupIndex = 0for(var i = 0; i < length; i++){ if(array[bottomIndex + i] < rightMostValue){swapElements(array, bottomIndex + lGroupIndex++, bottomIndex + i)}}swapElements(array, bottomIndex + lGroupIndex, topIndex)return bottomIndex + lGroupIndex}//testCasevar array = [1, 3, 8, 9, 2, 4, 6, 19, 88, 77, 11]QuickSort(array, 0, array.length - 1)//The result should be [1, 2, 3, 4, 6, 8, 9, 11, 19, 77, 88]console.log(array)

是不是好多啦 :)

转载于:https://www.cnblogs.com/E-WALKER/p/5118330.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！