vlambda博客
学习文章列表

package main
import ( "fmt" //"sort")
//InsertSort method//直接插入排序func InsertSort(a []int) { var i, j int for i = 1; i < len(a); i++ { //第一次是认为第一个元素已经是有序的,故从第二个位置开始
 temp := a[i] //将当前元素设为哨兵,临时变量temp,可以考虑直接赋值给a[0],代码改进的地方 for j = i - 1; j >= 0 && temp < a[j]; j-- { //比较元素大小,从后往前比较 a[j+1] = a[j] //向后挪位置 } a[j+1] = temp //将哨兵元素赋值到插入位置
 }
 fmt.Println(a)}


func main() { a := []int{1, 2, 6, 4, 78, 50} fmt.Println(a[1:5]) InsertSort(a) InsertSort1(a) fmt.Printf("%T\n", a) fmt.Println(a[1:5])  }

//InsertSort1 method//折半插入排序func InsertSort1(a []int) { var i, j, low, high, mid int for i = 2; i < len(a); i++ { temp := a[i] low, high = 1, i-1 if low <= high { mid = (high + low) / 2 if a[mid] > temp { high = mid - 1 } else { low = mid + 1 } for j = i - 1; j >= high+1; j-- { a[j+1] = a[j] } a[high+1] = temp } } fmt.Println(a)}

//ShellSort method//希尔排序func ShellSort(a []int) { n := len(a)  for dk := n / 2; dk >= 1; dk = dk / 2 { for i := dk + 1; i < n; i++ { temp := a[i] j:=i-dk for ; j >= 0 && temp < a[j]; j -= dk { a[j+dk] = a[j]  } a[j+dk] = temp } } fmt.Println(a)}
//代码更清楚的版本func shellSort(arr []int) { len := len(arr) // 增量 inc := 2 // 步长 step := len / inc for ; step > 0; step /= inc { for r := step; r < len; r ++ { // 最小下标为0 l := r - step tmp := arr[r] for ; l >= 0 && tmp < arr[l]; l -= step { arr[l+step] = arr[l] } arr[l+step] = tmp } } fmt.Println(arr)}

//BubbleSort method//冒泡排序func BubbleSort(a []int) { n := len(a) for i := 0; i < n-1; i++ { //总共比较i趟 flag1 := false for j := n - 1; j > i; j-- { //for j:=1; j<=n-i; j++ 第i趟需要比较n-i次 if a[j-1] > a[j] { //Swap(&a[j-1], &a[j]) a[j-1], a[j] = a[j], a[j-1] }
 flag1 = true } if flag1 == false { break } } fmt.Println(a)
}
//Swap method//交换值,注意指针传递,才会真正改变实参的值func Swap(a, b *int) { temp := *a *a = *b *b = temp
}
// func Swap1(a, b int) {// temp := a// a = b// b = temp
// }
//冒泡排序简单的一个递归算法func bubbleSort(arr []int, len int) { if len == 1 { return } for i := 0; i < len-1; i++ { if arr[i] > arr[i+1] { arr[i], arr[i+1] = arr[i+1], arr[i] } } bubbleSort(arr, len-1)}

////快速排序递归算法func qsort(array []int, low, high int) { if low < high { m := partition(array, low, high) // fmt.Println(m) qsort(array, low, m-1) qsort(array, m+1, high) }}
//划分方法func partition(array []int, low, high int) int { key := array[low] tmpLow := low tmpHigh := high for { //查找小于等于key的元素，该元素的位置一定是tmpLow到high之间，因为array[tmpLow]及左边元素小于等于key，不会越界 for array[tmpHigh] > key { tmpHigh-- } //找到大于key的元素，该元素的位置一定是low到tmpHigh+1之间。因为array[tmpHigh+1]必定大于key for array[tmpLow] <= key && tmpLow < tmpHigh { tmpLow++ }
 if tmpLow >= tmpHigh { break } // swap(array[tmpLow], array[tmpHigh]) array[tmpLow], array[tmpHigh] = array[tmpHigh], array[tmpLow] fmt.Println(array) } array[tmpLow], array[low] = array[low], array[tmpLow] return tmpLow}

//简单选择排序func selectsort(arr []int) { n := len(arr) for i := 0; i < n-1; i++ { //一共进行n-1趟 min := i //记录最小元素位置 for j := i + 1; j < n; j++ { //在arr[i...n-1]中选择最小的元素 if arr[j] < arr[min] { min = j //更新最小的元素位置 }
 } if min != i { arr[i], arr[min] = arr[min], arr[i] //与第i个位置交换 } } fmt.Println(arr)}

func mergeSort(arr []int, start, end int) { if start >= end { return }    mid:=(start + end) / 2  //从中间划分两个子序列 mergeSort(arr, start, mid) //对左侧子序列进行递归排序    mergeSort(arr, mid+1, end)  //对右侧子序列进行递归排序 merge(arr, start, mid, end) //归并}//merge()的功能是将前后相邻的两个有序表归并为一个有序表。func merge(arr []int, start, mid, end int) { var tmparr = []int{} var s1, s2 = start, mid+1 for s1<= mid && s2<= end{ if arr[s1] > arr[s2] { tmparr = append(tmparr, arr[s2]) s2++ } else { tmparr = append(tmparr, arr[s1]) s1++ } } if s1<=mid { tmparr = append(tmparr, arr[s1: mid+1]...) } if s2<=end { tmparr = append(tmparr, arr[s2: end+1]...) } for pos,item:=range tmparr{ arr[start + pos] = item }}

var a=[]int{3,4,0,1,5,6,7,8}
func main() { mergeSort(a, 0, len(a) - 1) fmt.Println(a)}