快速排序(QuickSort),又称分区交换排序(partition-exchange sort),简称快排。快排是一种通过基准划分区块,再不断交换左右项的排序方式,其采用了分治法,减少了交换的次数。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归或迭代进行,以此让整个数列变成有序序列。
解释:以某个数字为基点,这里取最右侧的数字8,以基点划分为两个区间,将小于8的数字放在左侧区间,将大于8的数字放在右侧区间。再将左侧区间和右侧区间分别放到递归,按照最右侧为基点,继续分解。直到分解完毕,排序完成。这是其中一种常见的分区递归法,除了这种方式外,还有其他实现方式。
这个版本是最常见的标准分区版本,简单好懂。先写一个分区函数,依据基准值把成员项分为左右两部分。基准值可以是数列中的任意一项,为了交换方便,基准值一般最左或最右侧项。把小于基准值的放在左侧,大于基准值的放在右侧,最后返回分区索引。这样就得到一个基于基准值的左右两个部分。再将左右两个部分,分别进行分区逻辑的递归调用,当左右值相等,也就是最小分区只有1项时终止。
- (function () {
- const arr = [7, 11, 9, 10, 12, 13, 8]
- // 构建数列,可以任意构建,支持负数,也不限浮点
- // const arr = [17, 31, 12334, 9.545, -10, -12, 1113, 38]
- console.time('sort1')
- const arr1 = arr.slice(0)
- console.log('sort1 origin:', arr1)
- console.log('\r\nquickSort1 sorted:', quickSort1(arr1))
- console.timeEnd('sort1')
- console.time('sort2')
- const arr2 = arr.slice(0)
- console.log('sort2 origin:', arr2)
- console.log('\r\nquickSort2 sorted:', quickSort2(arr2))
- console.timeEnd('sort2')
- console.time('sort3')
- const arr3 = arr.slice(0)
- console.log('sort3 origin:', arr3)
- console.log('\r\nquickSort3 sorted:', quickSort3(arr3))
- console.timeEnd('sort3')
- console.time('sort4')
- const arr4 = arr.slice(0)
- console.log('sort4 origin:', arr4)
- console.log('\r\nquickSort4 sorted:', quickSort4(arr4))
- console.timeEnd('sort4')
- })()
- /**
- // 测试结果
- jarry@jarrys-MacBook-Pro quicksort % node quick_sort.js
- sort1 origin: [
- 7, 11, 9, 10,
- 12, 13, 8
- ]
- origin array: [
- 7, 11, 9, 10,
- 12, 13, 8
- ]
- i=0 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
- i=1 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
- i=2 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
- i=3 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
- i=4 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
- i=5 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
- i=6 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
- origin array: [ 7, 9, 8 ]
- i=0 midIndex=1 pivot=9 arr[]=7,9,8
- i=1 midIndex=1 pivot=9 arr[]=7,9,8
- i=2 midIndex=1 pivot=9 arr[]=7,9,8
- origin array: [ 7, 8 ]
- i=0 midIndex=1 pivot=8 arr[]=7,8
- i=1 midIndex=1 pivot=8 arr[]=7,8
- origin array: [ 7 ]
- origin array: []
- sorted array: [ 7, 8 ]
- origin array: []
- sorted array: [ 7, 8, 9 ]
- origin array: [ 11, 12, 13 ]
- i=0 midIndex=1 pivot=12 arr[]=11,12,13
- i=1 midIndex=1 pivot=12 arr[]=11,12,13
- i=2 midIndex=1 pivot=12 arr[]=11,12,13
- origin array: [ 11 ]
- origin array: [ 13 ]
- sorted array: [ 11, 12, 13 ]
- sorted array: [
- 7, 8, 9, 10,
- 11, 12, 13
- ]
- quickSort1 sorted: [
- 7, 8, 9, 10,
- 11, 12, 13
- ]
- sort1: 9.824ms
- sort2 origin: [
- 7, 11, 9, 10,
- 12, 13, 8
- ]
- partitioned arr= [
- 7, 8, 9, 10,
- 12, 13, 11
- ] partitionIndex: 1 left= [ 7 ] arr[partitionIndex]= 8 right= [ 8, 9, 10, 12, 13, 11 ] [
- 7, 8, 9, 10,
- 12, 13, 11
- ]
- partitioned arr= [
- 7, 8, 9, 10,
- 11, 13, 12
- ] partitionIndex: 4 left= [ 9, 10 ] arr[partitionIndex]= 11 right= [ 11, 13, 12 ] [
- 7, 8, 9, 10,
- 11, 13, 12
- ]
- partitioned arr= [
- 7, 8, 9, 10,
- 11, 13, 12
- ] partitionIndex: 3 left= [ 9 ] arr[partitionIndex]= 10 right= [ 10 ] [
- 7, 8, 9, 10,
- 11, 13, 12
- ]
- partitioned arr= [
- 7, 8, 9, 10,
- 11, 12, 13
- ] partitionIndex: 5 left= [] arr[partitionIndex]= 12 right= [ 12, 13 ] [
- 7, 8, 9, 10,
- 11, 12, 13
- ]
- quickSort2 sorted: [
- 7, 8, 9, 10,
- 11, 12, 13
- ]
- sort2: 1.15ms
- sort3 origin: [
- 7, 11, 9, 10,
- 12, 13, 8
- ]
- arr[i] < pivot: i=0 j=6 pivot=10
- left=0 right=6 i=1 j=6 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
- arr[i] < pivot: i=2 j=5 pivot=10
- arr[j] > pivot: i=3 j=5 pivot=10
- arr[j] > pivot: i=3 j=4 pivot=10
- left=0 right=6 i=3 j=3 midIndex=3 pivot=10 arr[]=7,8,9,10,12,13,11
- left < j:recursion: left=0 right=6 i=4 j=2arr[]7,8,9,10,12,13,11
- arr[i] < pivot: i=0 j=2 pivot=8
- arr[j] > pivot: i=1 j=2 pivot=8
- left=0 right=2 i=1 j=1 midIndex=1 pivot=8 arr[]=7,8,9,10,12,13,11
- i < right:recursion: left=0 right=6 i=4 j=2arr[]7,8,9,10,12,13,11
- arr[i] < pivot: i=4 j=6 pivot=13
- left=4 right=6 i=5 j=6 midIndex=5 pivot=13 arr[]=7,8,9,10,12,13,11
- left < j:recursion: left=4 right=6 i=6 j=5arr[]7,8,9,10,12,11,13
- left=4 right=5 i=4 j=5 midIndex=4 pivot=12 arr[]=7,8,9,10,12,11,13
- quickSort3 sorted: [
- 7, 8, 9, 10,
- 11, 12, 13
- ]
- sort3: 0.595ms
- sort4 origin: [
- 7, 11, 9, 10,
- 12, 13, 8
- ]
- arr[i] < pivot: i=0 j=6 pivot=10arr[]=7,11,9,10,12,13,8
- arr[i] < pivot: i=2 j=5 pivot=10arr[]=7,8,9,10,12,13,11
- arr[j] > pivot: i=3 j=5 pivot=10arr[]=7,8,9,10,12,13,11
- arr[j] > pivot: i=3 j=4 pivot=10arr[]=7,8,9,10,12,13,11
- left < j:recursion: left=0 right=6 i=4 j=2arr[]=7,8,9,10,12,13,11
- i < right:recursion: left=0 right=6 i=4 j=2arr[]=7,8,9,10,12,13,11
- arr[i] < pivot: i=4 j=6 pivot=13arr[]=7,8,9,10,12,13,11
- left < j:recursion: left=4 right=6 i=6 j=5arr[]=7,8,9,10,12,11,13
- arr[i] < pivot: i=0 j=2 pivot=8arr[]=7,8,9,10,11,12,13
- arr[j] > pivot: i=1 j=2 pivot=8arr[]=7,8,9,10,11,12,13
- quickSort4 sorted: [
- 7, 8, 9, 10,
- 11, 12, 13
- ]
- sort4: 0.377ms
- */