Categories
程式開發

用go語言實現快排


面試的時候,常會讓你手寫快排代碼。思路清楚了,在10分鐘是可以寫出來的。關於快排,需要注意一下幾點:

快排是本地排序快排有遞歸快排需要分割數據,分割函數(建議)以最後一個數據為參考,將數據分割為大小兩列,最後返回參考數據所在的位置

好的函數名可以更好地體現思路。這是最近重構的版本,重新修改了函數名,理順了一下思路,在這裡做個記錄。

package algorithm

import (
"math/rand"
"testing"
"time"
)

func quickSort(data []int) {
sortWithinScope(data, 0, len(data)-1)
}

// 在指定范围内排序
func sortWithinScope(data []int, start int, end int) {
if start < end { pivot := partition(data, start, end) sortWithinScope(data, start, pivot-1) sortWithinScope(data, pivot+1, end) } } // 将指定范围内的数据分成大小两列,返回中间参考值的位置 func partition(data []int, start int, end int) int { ref := data[end] nextLowerIndex := start for i := start; i < end; i++ { if data[i] < ref { data[nextLowerIndex], data[i] = data[i], data[nextLowerIndex] nextLowerIndex++ } } data[nextLowerIndex], data[end] = data[end], data[nextLowerIndex] return nextLowerIndex } // 比较两列数据是否相同 func equal(a, b []int) bool { if len(a) != len(b) { return false } for i, v := range a { if v != b[i] { return false } } return true } func TestEmpty(t *testing.T) { count := 10 toSort := make([]int, 0) expect := make([]int, 0) for i := 0; i < count; i++ { toSort = append(toSort, i) expect = append(expect, i) } // 打乱有序数组 rand.Seed(time.Now().UnixNano()) rand.Shuffle(len(toSort), func(i, j int) { toSort[i], toSort[j] = toSort[j], toSort[i] }) quickSort(toSort) if !equal(expect, toSort) { t.Error("soft failed") } }