• 源碼

• 代碼

// 分區(qū)
// 將比pivot小的左移展姐，比pivot大的右移。
// 返回pivot的位置
//
func partition(data []int, left, right int) int {
    // 交換數(shù)據(jù)的位置
    store := left
    for j := left; j < right; j++ {
        // pivot為right位置的值
        if data[j] <= data[right] {
            // 交換數(shù)據(jù)
            if store != j {
                data[store], data[j] = data[j], data[store]
            }
            store++
        }
    }
    // 將基準(zhǔn)元素放置到最后的正確位置上
    data[store], data[right] = data[right], data[store]
    return store
}

// 遞歸調(diào)用
//
func quickSort(data []int, left, right int) {
    if left < right {
        idx := partition(data, left, right)
        quickSort(data, left, idx-1)
        quickSort(data, idx+1, right)
    }
}

// 對(duì)data進(jìn)行正向排序
// 1串结、在數(shù)據(jù)集之中第岖，選擇中間元素作為基準(zhǔn)（pivot）。
// 2霞掺、所有小于基準(zhǔn)的元素坛掠，都移到基準(zhǔn)的左邊耳璧；所有大于基準(zhǔn)的元素辅鲸，都移到基準(zhǔn)的右邊格郁。
// 這個(gè)操作稱為分區(qū) (partition) 操作，分區(qū)操作結(jié)束后独悴，基準(zhǔn)元素所處的位置就是最終排序后它的位置例书。
// 3、對(duì)基準(zhǔn)左邊和右邊的兩個(gè)子集刻炒，不斷重復(fù)第1步和第2步决采，直到所有子集只剩下一個(gè)元素為止。
// 難度系數(shù) O(n^2)
// 不穩(wěn)定排序
//
func QuickSort(data []int) {
    quickSort(data, 0, len(data)-1)
}

• 測(cè)試

func TestQuickSort(t *testing.T) {
    data := []int{0, 2, 4, 6, 8, 10, 9, 7, 5, 3, 1,8}
    fmt.Println("sort before", data)
    sort2.QuickSort(data)
    fmt.Println("sort after", data)
}

• 分析

sort before [0 2 4 6 8 10 9 7 5 3 1 8]
-----
partition store j left right data data[j] data[right] data[j]<=data[right]
0 0 0 11 [0 2 4 6 8 10 9 7 5 3 1 8] 0 8 true
1 1 0 11 [0 2 4 6 8 10 9 7 5 3 1 8] 2 8 true
2 2 0 11 [0 2 4 6 8 10 9 7 5 3 1 8] 4 8 true
3 3 0 11 [0 2 4 6 8 10 9 7 5 3 1 8] 6 8 true
4 4 0 11 [0 2 4 6 8 10 9 7 5 3 1 8] 8 8 true
5 5 0 11 [0 2 4 6 8 10 9 7 5 3 1 8] 10 8 false
5 6 0 11 [0 2 4 6 8 10 9 7 5 3 1 8] 9 8 false
5 7 0 11 [0 2 4 6 8 10 9 7 5 3 1 8] 7 8 true
6 8 0 11 [0 2 4 6 8 7 9 10 5 3 1 8] 5 8 true
7 9 0 11 [0 2 4 6 8 7 5 10 9 3 1 8] 3 8 true
8 10 0 11 [0 2 4 6 8 7 5 3 9 10 1 8] 1 8 true
9 0 11 [0 2 4 6 8 7 5 3 1 8 9 10]
quickSort left 0 right 11 idx 9 data [0 2 4 6 8 7 5 3 1 8 9 10]
-----
partition store j left right data data[j] data[right] data[j]<=data[right]
0 0 0 8 [0 2 4 6 8 7 5 3 1 8 9 10] 0 1 true
1 1 0 8 [0 2 4 6 8 7 5 3 1 8 9 10] 2 1 false
1 2 0 8 [0 2 4 6 8 7 5 3 1 8 9 10] 4 1 false
1 3 0 8 [0 2 4 6 8 7 5 3 1 8 9 10] 6 1 false
1 4 0 8 [0 2 4 6 8 7 5 3 1 8 9 10] 8 1 false
1 5 0 8 [0 2 4 6 8 7 5 3 1 8 9 10] 7 1 false
1 6 0 8 [0 2 4 6 8 7 5 3 1 8 9 10] 5 1 false
1 7 0 8 [0 2 4 6 8 7 5 3 1 8 9 10] 3 1 false
1 0 8 [0 1 4 6 8 7 5 3 2 8 9 10]
quickSort left 0 right 8 idx 1 data [0 1 4 6 8 7 5 3 2 8 9 10]
-----
partition store j left right data data[j] data[right] data[j]<=data[right]
2 2 2 8 [0 1 4 6 8 7 5 3 2 8 9 10] 4 2 false
2 3 2 8 [0 1 4 6 8 7 5 3 2 8 9 10] 6 2 false
2 4 2 8 [0 1 4 6 8 7 5 3 2 8 9 10] 8 2 false
2 5 2 8 [0 1 4 6 8 7 5 3 2 8 9 10] 7 2 false
2 6 2 8 [0 1 4 6 8 7 5 3 2 8 9 10] 5 2 false
2 7 2 8 [0 1 4 6 8 7 5 3 2 8 9 10] 3 2 false
2 2 8 [0 1 2 6 8 7 5 3 4 8 9 10]
quickSort left 2 right 8 idx 2 data [0 1 2 6 8 7 5 3 4 8 9 10]
-----
partition store j left right data data[j] data[right] data[j]<=data[right]
3 3 3 8 [0 1 2 6 8 7 5 3 4 8 9 10] 6 4 false
3 4 3 8 [0 1 2 6 8 7 5 3 4 8 9 10] 8 4 false
3 5 3 8 [0 1 2 6 8 7 5 3 4 8 9 10] 7 4 false
3 6 3 8 [0 1 2 6 8 7 5 3 4 8 9 10] 5 4 false
3 7 3 8 [0 1 2 6 8 7 5 3 4 8 9 10] 3 4 true
4 3 8 [0 1 2 3 4 7 5 6 8 8 9 10]
quickSort left 3 right 8 idx 4 data [0 1 2 3 4 7 5 6 8 8 9 10]
-----
partition store j left right data data[j] data[right] data[j]<=data[right]
5 5 5 8 [0 1 2 3 4 7 5 6 8 8 9 10] 7 8 true
6 6 5 8 [0 1 2 3 4 7 5 6 8 8 9 10] 5 8 true
7 7 5 8 [0 1 2 3 4 7 5 6 8 8 9 10] 6 8 true
8 5 8 [0 1 2 3 4 7 5 6 8 8 9 10]
quickSort left 5 right 8 idx 8 data [0 1 2 3 4 7 5 6 8 8 9 10]
-----
partition store j left right data data[j] data[right] data[j]<=data[right]
5 5 5 7 [0 1 2 3 4 7 5 6 8 8 9 10] 7