Golang 插入排序

插入排序 – 初版

这个版本的思想是：先找出要交换的两个位置的 index ，然后再统一移动位置.

package main

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

func main() {
	var data []int
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < 50; i++ {
		data = append(data, rand.Intn(100))
	}
	fmt.Printf("%v\n", data)
	insertSort(data)
}

func insertSort(data []int) {
	if len(data) <= 1 {
		return
	}
	//sortIndex := 1
	for i := 1; i < len(data); i++ {
		startIndex := findPosition(data, i)
		if startIndex >= 0 {
			moveRights(data, i, startIndex)
			fmt.Printf("after %v times. data = %v, startIndex = %v\n", i, data, startIndex)
		}
	}
	fmt.Printf("%v\n", data)
}

func findPosition(data []int, sortIndex int) (startIndex int) {
	startIndex = -1
	sortEle := data[sortIndex]
	if sortIndex >= 1 {
		startIndex = sortIndex - 1
		for startIndex >= 0 {
			preEle := data[startIndex]
			if startIndex >= 1 {
				prePreEle := data[startIndex-1]
				if sortEle <= preEle && sortEle >= prePreEle {
					return
				}
			} else {
				if sortEle <= preEle {
					return
				}
			}
			startIndex--
		}
	}
	return
}

// 从小到大，那就是向右移动
func moveRights(data []int, sortIndex int, startIndex int) {
	if sortIndex > startIndex {
		tmp := data[sortIndex]
		n := sortIndex - startIndex
		for n > 0 && sortIndex > 0 {
			data[sortIndex] = data[sortIndex-1]
			sortIndex--
			n--
		}
		data[startIndex] = tmp
	}
}

插入排序 – 改进版

这个版本的思想是：不断的对比，然后不断地立马交换位置。而不是像初版那样，先不断地对比，然后找出两个位置，最后再统一移动。

package main

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

func main() {
	data := number.GenerateInt(15, 1000)
	//fmt.Printf("before data = %v\n", data)
	start := time.CurrentMillis()
	insertSort(data)
	fmt.Printf("cost %v ms\n", time.CurrentMillis()-start)
	//fmt.Printf("after data = %v\n", data)

}

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
			}

		}
	}
}

Contents

插入排序 – 初版

插入排序 – 改进版