缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

快速排序(Quick Sort)

  1. 快速排序算法首先会在序列中随机选择一个基准值（pivot），
  2. 然后将除了基准值以外的数, 
  3. 分为“比基准值小的数”和“比基准值大的数”这两个类别，
  4. 再将其排列成以下形式:
  5. [ 比基准值小的数 ] 基准值 [ 比基准值大的数 ]
  7. 接着，对两个“[]”中的数据进行排序之后，
  8. 整体的排序便完成了。
  10. 对“[]”里面的数据进行排序时同样也会使用快速排序。
  12. 快速排序是一种“分治法”。
  13. 它将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），
  14. 然后再分别解决这两个问题(递归地)。
  16. 平均运行时间为O(nlogn)
  18. 摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

流程(非递归, 原地快速排序)

  1. 给定待排序数组data[N]
  2. 定义待排序栈stack, 其中元素是一个(left, right)整型坐标, 表示待排序子序列的范围
  3. 初始时, 将(0, N-1)压入stack, 表示需要将整个序列进行排序
  4. 当stack不为空时, 循环执行:
    1. 待排序子序列出栈: left, right = stack.pop()
    2. 取基准值v = data[left], 然后data[left]置为nil, 腾出一个格子备用
    3. 取左指针l = left, 右指针r = right, 当前指针标识(左/右)rside = true
    4. 如果rside == true, 将右指针r向左移动, 直到: data[r] < v, 或r=l
    5. 如果找到data[r] < v, 则把data[r]置入data[l]指向的空位, data[r]设nil, 腾出一个格子
    6. 如果rside == false, 将左指针l向右移动, 直到: data[l] > v, 或l=r
    7. 如果找到data[l] > v, 则把data[l]置入data[r]指向的空位, data[l]设nil, 腾出一个格子
    8. 如果l == r, 左右序列切分完成, 将基准值v置入data[l], 返回
    9. 循环执行步骤4-8
  5. stack为空, 排序完成

为什么要非递归

  • 极端情况下(比如特别大的数组, 刚好已经是倒序排列, 而每次取基准值是取left位置), 递归算法可能导致栈嵌套过深, 一个是占用大量内存, 二个是可能导致栈溢出错误.

  • 快速排序需要左右子序列的中间结果, 再进行合并, 因此无法通过尾递归优化消除栈嵌套

    目标

  • 实现并验证快速排序

  • 使用辅助的子序列坐标栈, 实现非递归执行
  • 原地排序, 不占用额外空间

设计

  • ISorter: 定义排序器接口. 定义值比较函数以兼容任意数值类型, 通过调整比较函数实现倒序排序
  • tQStack: 实现一个堆栈, 辅助快速排序时, 记录待排序的子序列坐标
  • tQuickSort: 非递归的原地快速排序器, 实现ISorter接口, 使用辅助栈消除递归

单元测试

quick_sort_test.go, 测试过程与堆排序, 归并排序类似, 样本规模为10万元素

  1. package sorting
  3. import (
  4.     "fmt"
  5.     "learning/gooop/sorting"
  6.     "learning/gooop/sorting/quick_sort"
  7.     "math/rand"
  8.     "testing"
  9.     "time"
  10. )
  12. func Test_QuickSort(t *testing.T) {
  13.     fnAssertTrue := func(b bool, msg string) {
  14.         if !b {
  15.             t.Fatal(msg)
  16.         }
  17.     }
  19.     reversed := false
  20.     fnCompare := func(a interface{}, b interface{}) sorting.CompareResult {
  21.         i1 := a.(int)
  22.         i2 := b.(int)
  24.         if i1 < i2 {
  25.             if reversed {
  26.                 return sorting.GREATER
  27.             } else {
  28.                 return sorting.LESS
  29.             }
  30.         } else if i1 == i2 {
  31.             return sorting.EQUAL
  32.         } else {
  33.             if reversed {
  34.                 return sorting.LESS
  35.             } else {
  36.                 return sorting.GREATER
  37.             }
  38.         }
  39.     }
  41.     fnTestSorter := func(sorter sorting.ISorter) {
  42.         reversed = false
  44.         // test simple array
  45.         samples := []interface{} { 2,3,1,5,4,7,6 }
  46.         samples = sorter.Sort(samples, fnCompare)
  47.         fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 2 3 4 5 6 7]",  "expecting 1,2,3,4,5,6,7")
  48.         t.Log("pass sorting [2 3 1 5 4 7 6] >> [1 2 3 4 5 6 7]")
  50.         // test 10000 items sorting
  51.         rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
  52.         for plus := 0;plus < 5;plus++ {
  53.             sampleCount := 100 * 1000 + plus
  54.             t.Logf("prepare large array with %v items", sampleCount)
  55.             samples = make([]interface{}, sampleCount)
  56.             for i := 0; i < sampleCount; i++ {
  57.                 samples[i] = rnd.Intn(sampleCount * 10)
  58.             }
  60.             t.Logf("sorting large array with %v items", sampleCount)
  61.             t0 := time.Now().UnixNano()
  62.             samples = sorter.Sort(samples, fnCompare)
  63.             cost := time.Now().UnixNano() - t0
  64.             for i := 1; i < sampleCount; i++ {
  65.                 fnAssertTrue(fnCompare(samples[i-1], samples[i]) != sorting.GREATER, "expecting <=")
  66.             }
  67.             t.Logf("end sorting large array, cost = %v ms", cost/1000000)
  68.         }
  70.         // test 0-20
  71.         sampleCount := 20
  72.         t.Log("sorting 0-20")
  73.         samples = make([]interface{}, sampleCount)
  74.         for i := 0;i < sampleCount;i++ {
  75.             for {
  76.                 p := rnd.Intn(sampleCount)
  77.                 if samples[p] == nil {
  78.                     samples[p] = i
  79.                     break
  80.                 }
  81.             }
  82.         }
  83.         t.Logf("unsort = %v", samples)
  85.         samples = sorter.Sort(samples, fnCompare)
  86.         t.Logf("sorted = %v", samples)
  87.         fnAssertTrue(fmt.Sprintf("%v", samples) == "[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]", "expecting 0-20")
  88.         t.Log("pass sorting 0-20")
  90.         // test special
  91.         samples = []interface{} {}
  92.         samples = sorter.Sort(samples, fnCompare)
  93.         t.Log("pass sorting []")
  95.         samples = []interface{} { 1 }
  96.         samples = sorter.Sort(samples, fnCompare)
  97.         t.Log("pass sorting [1]")
  99.         samples = []interface{} { 3,1 }
  100.         samples = sorter.Sort(samples, fnCompare)
  101.         fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 3]",  "expecting 1,3")
  102.         t.Log("pass sorting [1 3]")
  104.         reversed = true
  105.         samples = []interface{} { 2, 3,1 }
  106.         samples = sorter.Sort(samples, fnCompare)
  107.         fnAssertTrue(fmt.Sprintf("%v", samples) == "[3 2 1]",  "expecting 3,2,1")
  108.         t.Log("pass sorting [3 2 1]")
  109.     }
  111.     t.Log("\ntesting QuickSorter")
  112.     fnTestSorter(quick_sort.QuickSorter)
  113. }

测试输出

  • 快速排序真的很快, 与堆排序,归并排序是一个数量级, 10万随机元素排序耗时仅数十毫秒
  • 对随机数据的排序比归并排序还稍快一些, 这可能是因为原地排序不需要预分配缓冲区
    1. $ go test -v quick_sort_test.go 
    2. === RUN   Test_QuickSort
    3.   quick_sort_test.go:111: 
    4.       testing QuickSorter
    5.   quick_sort_test.go:48: pass sorting [2 3 1 5 4 7 6] >> [1 2 3 4 5 6 7]
    6.   quick_sort_test.go:54: prepare large array with 100000 items
    7.   quick_sort_test.go:60: sorting large array with 100000 items
    8.   quick_sort_test.go:67: end sorting large array, cost = 27 ms
    9.   quick_sort_test.go:54: prepare large array with 100001 items
    10.   quick_sort_test.go:60: sorting large array with 100001 items
    11.   quick_sort_test.go:67: end sorting large array, cost = 28 ms
    12.   quick_sort_test.go:54: prepare large array with 100002 items
    13.   quick_sort_test.go:60: sorting large array with 100002 items
    14.   quick_sort_test.go:67: end sorting large array, cost = 33 ms
    15.   quick_sort_test.go:54: prepare large array with 100003 items
    16.   quick_sort_test.go:60: sorting large array with 100003 items
    17.   quick_sort_test.go:67: end sorting large array, cost = 32 ms
    18.   quick_sort_test.go:54: prepare large array with 100004 items
    19.   quick_sort_test.go:60: sorting large array with 100004 items
    20.   quick_sort_test.go:67: end sorting large array, cost = 27 ms
    21.   quick_sort_test.go:72: sorting 0-20
    22.   quick_sort_test.go:83: unsort = [11 3 4 2 9 19 18 7 12 6 13 5 10 0 15 14 17 1 8 16]
    23.   quick_sort_test.go:86: sorted = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]
    24.   quick_sort_test.go:88: pass sorting 0-20
    25.   quick_sort_test.go:93: pass sorting []
    26.   quick_sort_test.go:97: pass sorting [1]
    27.   quick_sort_test.go:102: pass sorting [1 3]
    28.   quick_sort_test.go:108: pass sorting [3 2 1]
    29. --- PASS: Test_QuickSort (0.18s)
    30. PASS
    31. ok      command-line-arguments  0.184s

ISorter.go

定义排序器接口. 定义值比较函数以兼容任意数值类型, 通过调整比较函数实现倒序排序

  1. package sorting
  3. type ISorter interface {
  4.     Sort(data []interface{}, comparator CompareFunction) []interface{}
  5. }
  7. type CompareFunction func(a interface{}, b interface{}) CompareResult
  9. type CompareResult int
  10. const LESS CompareResult = -1
  11. const EQUAL CompareResult = 0
  12. const GREATER CompareResult = 1

tQStack.go

实现一个堆栈, 辅助快速排序时, 记录待排序的子序列坐标

  1. package quick_sort
  3. type tQStack struct {
  4.     stack []tIntPair
  5.     capacity int
  6.     size int
  7. }
  9. type tIntPair [2]int
  10. var gEmptyPair = [2]int{ -1, -1 }
  12. func newQStack() *tQStack {
  13.     return &tQStack{
  14.         stack: make([]tIntPair, 0),
  15.         capacity: 0,
  16.         size: 0,
  17.     }
  18. }
  20. func (me *tQStack) push(left,right int) {
  21.     node := tIntPair([2]int{left,right})
  22.     if me.size < me.capacity {
  23.         me.stack[me.size] = node
  24.     } else {
  25.         me.stack = append(me.stack, node)
  26.         me.capacity++
  27.     }
  28.     me.size++
  29. }
  31. func (me *tQStack) pop() (left, right int) {
  32.     me.size--
  33.     it := me.stack[me.size]
  34.     me.stack[me.size] = gEmptyPair
  35.     return it[0], it[1]
  36. }
  38. func (me *tQStack) isEmpty() bool {
  39.     return me.size <= 0
  40. }
  42. func (me *tQStack) isNotEmpty() bool {
  43.     return me.size > 0
  44. }

tQuickSort.go

非递归的原地快速排序器, 实现ISorter接口, 使用辅助栈消除递归

  1. package quick_sort
  3. import (
  4.     "learning/gooop/sorting"
  5. )
  7. type tQuickSort struct {
  8. }
  10. func newQuickSort() sorting.ISorter {
  11.     return &tQuickSort{}
  12. }
  14. func (me *tQuickSort) Sort(data []interface{}, comparator sorting.CompareFunction) []interface{} {
  15.     if data == nil {
  16.         return nil
  17.     }
  19.     size := len(data)
  20.     if size <= 1 {
  21.         return data
  22.     }
  24.     if size == 2 {
  25.         if comparator(data[0], data[1]) == sorting.GREATER {
  26.             data[0],data[1] = data[1], data[0]
  27.             return data
  28.         }
  29.     }
  31.     stack := newQStack()
  32.     stack.push(0, size - 1)
  33.     me.qsort(data, comparator, stack)
  34.     return data
  35. }
  37. func (me *tQuickSort) qsort(data []interface{}, comparator sorting.CompareFunction, stack *tQStack) {
  38.     for ;stack.isNotEmpty(); {
  39.         left, right := stack.pop()
  40.         lfrom, lto, rfrom, rto := me.split(data, comparator, left, right)
  42.         if lfrom < lto {
  43.             stack.push(lfrom, lto)
  44.         }
  45.         if rfrom < rto  {
  46.             stack.push(rfrom, rto)
  47.         }
  48.     }
  49. }
  51. func (me *tQuickSort) split(data []interface{}, comparator sorting.CompareFunction, left int, right int) (lfrom, lto, rfrom, rto int) {
  52.     if left >= right {
  53.         return
  54.     }
  56.     v := data[left]
  57.     l := left
  58.     r := right
  59.     rside := true
  61.     for {
  62.         hit := false
  63.         if rside {
  64.             for ; r > l; r-- {
  65.                 if comparator(data[r], v) == sorting.LESS {
  66.                     hit = true
  67.                     break
  68.                 }
  69.             }
  71.             if hit {
  72.                 data[l], data[r] = data[r], nil
  73.                 l++
  74.                 rside = false
  75.             }
  76.         } else {
  77.             for ; l < r;l++ {
  78.                 if comparator(data[l], v) == sorting.GREATER {
  79.                     hit = true
  80.                     break
  81.                 }
  82.             }
  84.             if hit {
  85.                 data[r], data[l] = data[l], nil
  86.                 r--
  87.                 rside = true
  88.             }
  89.         }
  91.         if l == r {
  92.             data[l] = v
  93.             break
  94.         }
  95.     }
  97.     return left, l - 1, r + 1, right
  98. }
  100. var QuickSorter = newQuickSort()

(end)