针对主要的几种的排序算法的理解。 用Go 再实现一遍吧。
package main
import (
"fmt"
"math/rand"
"reflect"
"runtime"
"time"
)
func shuffle(list []int) {
r := rand.New(rand.NewSource(time.Now().Unix()))
size := len(list)
for x := range list {
randomNum := r.Intn(size)
list[x],list[randomNum] = list[randomNum] ,list[x]
}
}
func checkList(list []int) bool {
for x ,val := range list {
if x != val {
return false
}
}
return true
}
// 冒泡排序 将就是像 气泡从底下往冒， 就是
// App elapsed: 14.197123932s 100000的 list
// O(n^2)
func buboo(result []int ) {
for ind_i := range result {
for ind_j:= ind_i+1; ind_j < len(result); ind_j++ {
if result[ind_i] > result[ind_j] {
result[ind_i],result[ind_j] = result[ind_j],result[ind_i]
}
}
}
}
//App elapsed: 4.677840984s 100000的 list
// 选择排序 每次将剩下的一部分中， 选择 最大的一个放到队列里。
// O(n^2)
func selectSort(result []int){
resultLen := len(result)
for i :=0; i < resultLen ; i++ {
v := result[i]
m := i
j := resultLen-1
// 冒泡算法？ 一次 一个 冒一个
for ;j > i; j-- {
if result[j] < v {
m = j
v = result[j]
}
}
result[i],result[m] = result[m] ,result[i]
}
}
// 插入排序 main.insertSort function elapsed: 1.638001664s 100000 element
func insertSort(result []int) {
for i:=1;i<len(result);i++ {
j := i - 1
temp := result[i]
for ; j >= 0 && temp < result[j]; j-- {
result[j+1] = result[j] //将大于temp的值整体后移一个单位
}
result[j+1] = temp
}
}
// 冒泡 与 选择排序 之间有2倍以上的效率问题。
// 快排 果然快 选择排序 快 一个单位了。。。
//App elapsed: 7.602426ms 100000的 list
func quickSort(result []int){
resultLen := len(result)
if resultLen == 1 || resultLen == 0 {
return
}
mid := result[resultLen-1]
head , tail := 0,resultLen-2
for ;head <= tail ; {
if result[head] > mid {
result[head],result[tail] = result[tail],result[head]
tail--
}else{
head ++
}
}
result[head] ,result[resultLen-1] = result[resultLen-1],result[head]
quickSort(result[:head])
quickSort(result[head+1:])
}
// 冒泡 与 选择排序 之间有2倍以上的效率问题。
// 快排 果然快 选择排序 快 一个单位了。。。
//App elapsed: 7.602426ms 100000的 list
func QuickSort(result []int){
resultLen := len(result)
if resultLen == 1 || resultLen == 0 {
return
}
mid := result[resultLen-1]
head , tail := 0,resultLen-2
for ;head <= tail ; {
if result[head] > mid {
result[head],result[tail] = result[tail],result[head]
tail--
}else{
head ++
}
}
result[head] ,result[resultLen-1] = result[resultLen-1],result[head]
quickSort(result[:head])
quickSort(result[head+1:])
}
// App elapsed: 6.602426ms 100000的 list 稍微快点吧。
// some 优化。 优化的第一步 优化个锤子。 其实就是专业
// The actual implementation uses two optimizations:
//Firstly, if the number of elements to be sorted is less than a certain threshold, selection sort is used.
//Secondly, the recursive calls are made for the smaller of the two sub-arrays, thereby the stack size is bounded by
// 优化的两个方向，在一个threadhold (阈值) 在当前的数量少于一个特定值 就使用选择排序。 然后第二个方式就是 选择更小的子集数组进行递归， 这样减少递归的层次。
// 顺带提一句 Go的 sort.Sort 用的主要是快排 堆排 ，选择排序。附上源码。
/*
当 需要排序范围 小于12 之后就直接用插入排序 取处理， 每次用快排处理， 当深度达到一定threadhold 就切换 堆排序。 总体就是这样 。
func quickSort(data Interface, a, b, maxDepth int) {
for b-a > 12 { // Use ShellSort for slices <= 12 elements
if maxDepth == 0 {
heapSort(data, a, b)
return
}
maxDepth--
mlo, mhi := doPivot(data, a, b)
// Avoiding recursion on the larger subproblem guarantees
// a stack depth of at most lg(b-a).
if mlo-a < b-mhi {
quickSort(data, a, mlo, maxDepth)
a = mhi // i.e., quickSort(data, mhi, b)
} else {
quickSort(data, mhi, b, maxDepth)
b = mlo // i.e., quickSort(data, a, mlo)
}
}
if b-a > 1 {
// Do ShellSort pass with gap 6
// It could be written in this simplified form cause b-a <= 12
for i := a + 6; i < b; i++ {
if data.Less(i, i-6) {
data.Swap(i, i-6)
}
}
insertionSort(data, a, b)
}
}
// Insertion sort
func insertionSort(data Interface, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && data.Less(j, j-1); j-- {
data.Swap(j, j-1)
}
}
}
// 堆排序
func heapSort(data Interface, a, b int) {
first := a
lo := 0
hi := b - a
// Build heap with greatest element at top.
for i := (hi - 1) / 2; i >= 0; i-- {
siftDown(data, i, hi, first)
}
// Pop elements, largest first, into end of data.
for i := hi - 1; i >= 0; i-- {
data.Swap(first, first+i)
siftDown(data, lo, i, first)
}
}
*/
func quickSort_Op(result []int){
resultLen := len(result)
if resultLen == 1 || resultLen == 0 {
return
}
if(resultLen < 32) {
insertSort(result)
return
}
mid := quickSort_GetMidVal(result)
head , tail := 0,resultLen-1
for ;; {
for ;result[head]< mid; head++{}
for ;result[tail]> mid; tail--{}
if head < tail {
result[head],result[tail] = result[tail],result[head]
}
if(head == tail ){
break
}
}
quickSort_Op(result[:head])
quickSort_Op(result[head+1:])
}
func quickSort_GetMidVal(result []int) int{
max := result[len(result)-1]
mid := result[len(result)/2]
min := result[0]
if max > min {
if max < mid {
return max
}else {
if mid < min {
return min
}else{
return mid
}
}
}else{
if max > mid {
return max
}else{
if mid < min {
return min
}else{
return mid
}
}
}
}
func maxHeadfy(arr []int, i ,end int) {
dad := i
leftSon := 2 *i + 1
for ; leftSon <= end ; {
// 如果左子节点+1 还是存在， 并且 左子节点小于 父节点 ，
if leftSon +1 <= end && arr[leftSon+1 ] > arr[leftSon] {
// 目的选出最大的一个子节点的index
leftSon++
}
if arr[leftSon] < arr[dad] {
return
}else{
arr[leftSon], arr[dad] = arr[dad] , arr[leftSon]
dad = leftSon
leftSon = dad *2 +1
}
}
}
// 堆排序 main.heapSort function elapsed: 14.310156ms 100000 element
func heapSort(arr []int ) {
var i int
// 从最底层的父节点开始。（ 由于完美二叉树的特性 前2分之一 都是 有子节点的。
for i = len(arr)/2-1 ; i>=0 ; i-- {
maxHeadfy(arr, i , len(arr) -1)
}
// 依次取 堆顶
for i = len(arr)-1 ; i > 0; i-- {
arr[0], arr[i] = arr[i] , arr[0]
maxHeadfy(arr, 0, i - 1)
}
}
func testFunc(list2 []int) {
list1 := make([]int,100000)
copy(list2,list1)
for x:=0 ; x < 100000; x++ {
list1[x] = x
}
shuffle(list1)
t1 := time.Now() // get current time
quickSort_Op(list1)
fmt.Println("quickSort_Op App elapsed: ", time.Since(t1))
fmt.Println(checkList(list1))
}
func testFuncSpeed(list []int ,fun func( []int )){
listLen := len(list)
list1 := make([]int,listLen)
copy(list1,list)
t1 := time.Now() // get current time
var m1 runtime.MemStats
runtime.ReadMemStats(&m1)
fun(list1)
var m2 runtime.MemStats
runtime.ReadMemStats(&m2)
//fmt.Printf("%d KB \n", (m2.Alloc - m1.Alloc))
fmt.Printf("%s function elapsed: %s \n", runtime.FuncForPC(reflect.ValueOf(fun).Pointer()).Name(),time.Since(t1))
fmt.Println(checkList(list1))
}
func main() {
list1 := make([]int,100000)
for x:=0 ; x < 100000; x++ {
list1[x] = x
}
shuffle(list1)
fmt.Println(checkList(list1))
testFuncSpeed(list1, buboo)
fmt.Println(checkList(list1))
testFuncSpeed(list1, selectSort)
fmt.Println(checkList(list1))
testFuncSpeed(list1, insertSort)
fmt.Println(checkList(list1))
testFuncSpeed(list1, heapSort)
fmt.Println(checkList(list1))
testFuncSpeed(list1, quickSort)
fmt.Println(checkList(list1))
testFuncSpeed(list1, quickSort_Op)
}