算法 - 快排序

• 源码

• 代码

// 分区
// 将比pivot小的左移，比pivot大的右移。
// 返回pivot的位置
//
func partition(data []int, left, right int) int {
    // 交换数据的位置
    store := left
    for j := left; j < right; j++ {
        // pivot为right位置的值
        if data[j] <= data[right] {
            // 交换数据
            if store != j {
                data[store], data[j] = data[j], data[store]
            }
            store++
        }
    }
    // 将基准元素放置到最后的正确位置上
    data[store], data[right] = data[right], data[store]
    return store
}

// 递归调用
//
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)
    }
}

// 对data进行正向排序
// 1、在数据集之中，选择中间元素作为基准（pivot）。
// 2、所有小于基准的元素，都移到基准的左边；所有大于基准的元素，都移到基准的右边。
// 这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
// 3、对基准左边和右边的两个子集，不断重复第1步和第2步，直到所有子集只剩下一个元素为止。
// 难度系数 O(n^2)
// 不稳定排序
//
func QuickSort(data []int) {
    quickSort(data, 0, len(data)-1)
}

• 测试

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