Golang 希尔排序 VS 插入排序

希尔排序 VS 插入排序

package main

import (
	"fmt"
	"helper/number"
	"helper/time"
)

func main() {
	data := number.GenerateInt(100000, 1000)
	dataCopy := make([]int, len(data))
	copy(dataCopy, data)

	start := time.CurrentMillis()
	// fmt.Printf("insert sort: before data = %v\n", data)
	insertSort(data)
	// fmt.Printf("insert sort: after data = %v\n", data)
	fmt.Printf("insert cost %v ms\n", time.CurrentMillis()-start)

	start = time.CurrentMillis()
	// fmt.Printf("shell sort: before data = %v\n", dataCopy)
	shellSort(dataCopy)
	// fmt.Printf("shell sort: after data = %v\n", dataCopy)
	fmt.Printf("shell sort cost %v ms\n", time.CurrentMillis()-start)
}

func shellSort(data []int) {
	//一共有多少列: 4 -> 2 -> 1
	for col := len(data) / 2; col >= 1; col = col / 2 {

		//对每一列处理 0 -> col（即每一次循环，就是处理该列的排序）
		for i := 0; i < col; i++ {

			//从每一列的第二个数开始进行插入排序（因为只有 >= 2 个元素时，才有可比性）
			n := 1
			//i + col * n 表示该列的下一个元素的位置 , 它要 < len(data)
			for i+col*n < len(data) {

				//保存当前元素的位置（因为它要不断地与位置比它小的进行交换（即插入排序）
				k := i + col*n
				for k >= 0 && (k-col) >= 0 {

					//不断地与前一个元素进行比较（直到 前一个元素 >= 即可停止）这里是开始排序
					if data[k] < data[k-col] {
						data[k], data[k-col] = data[k-col], data[k]
						k = k - col
					} else {
						break
					}

				}

				//该列的下一个元素
				n++
			}
		}
	}
}

func insertSort(data []int) {
	//从第二个元素开始排序，第一个为 i = 0
	for i := 1; i < len(data); i++ {

		//保存当前位置的一个副本，因为它要不断地减小，（因为要不断地缩小并比较之前的数据，以便进行交换）
		currentIndex := i
		//不断与前一个相比较
		for currentIndex-1 >= 0 {
			//符合条件则交换
			if data[currentIndex] < data[currentIndex-1] {
				data[currentIndex], data[currentIndex-1] = data[currentIndex-1], data[currentIndex]
				currentIndex--
			} else {
				break
			}

		}
	}
}

性能比较:

[23:04:37] emacsist:test4 $ go build insert_sort_vs.go && ./insert_sort_vs
insert cost 5295 ms
shell sort cost 22 ms
[23:09:15] emacsist:test4 $ go build insert_sort_vs.go && ./insert_sort_vs
insert cost 5220 ms
shell sort cost 17 ms
[23:09:23] emacsist:test4 $

Contents

希尔排序 VS 插入排序