package main import ( "fmt" "math/rand" "time" // "os" // "os/signal" ) const ( num = 100000 rangeNum = 100000 ) func main() { randSeed := rand.New(rand.NewSource(time.Now().Unix() + time.Now().UnixNano())) var buf []int for i := 0; i < num; i++ { buf = append(buf, randSeed.Intn(rangeNum)) } t := time.Now() //冒泡排序 // maopao(buf) // 选择排序 // xuanze(b...阅读全文
归并排序的基本思想 将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。 综上可知： 归并排序其实要做两件事： （1）“分解”——将序列每次折半划分。 （2）“合并”——将划分后的序列段两两合并后排序。 归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。 如 设有数列{6，202，100，301，38，8，1} 初始状态：6,202,100,301,38,8，1 第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3； 第二次归并后：{6,100,202,301...阅读全文
封装成函数： //自顶向下归并排序func MergeSortUpToDown(s []int) { aux := make([]int, len(s)) //辅助切片 mergeSortUpToDown(s, aux, 0, len(s)-1)} //自底向上归并排序func MergeSortDownToUp(s []int) { aux := make([]int, len(s)) //辅助切片 n := len(s) for sz := 1; sz < n; sz *= 2 { for lo := 0; lo < n-sz; lo += 2 * sz { merge(s, aux, lo, lo+sz-1, min(lo+2*sz-1, n-1)) } }} func mergeSo...阅读全文
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) } 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]...阅读全文
最近对go语言发生了兴趣，发现go语言语法简洁，非常适合算法的描述和实现，于是对归并排序进行了实现。 例子中需要排序的队列是长度为100的从100到1的数列，排序算法是正序排序，排序正确的话，结果应当为1到100。 因为已设定数组最大值为100，因此“哨兵”简略设置为1000，因为不是算法核心部分，此处“哨兵”最大值处理省略。 1 /* 2 归并排序的go语言实现 3 */ 4 package main 5 6 import fmt "fmt" 7 8 func main () { 9 /* 10 生成需要排序的队列100~1 11 */ 12 length:=100 13 A:=make([]int,length) 14 j:=length 15 for i:=0;i
查看完整的代码，点击这里 不了解归并排序的可以查看百度百科的分析 归并排序的实现 基本实现 package main import "fmt" // 合并 [l,r] 两部分数据，mid 左半部分的终点，mid + 1 是右半部分的起点 func merge(arr []int, l int, mid int, r int) { // 因为需要直接修改 arr 数据，这里首先复制 [l,r] 的数据到新的数组中，用于赋值操作 temp := make([]int, r-l+1) for i := l; i <= r; i++ { temp[i-l] = arr[i] } // 指向两部分起点 left := l right := mid + 1 for i := l; i <= r; i++...阅读全文
归并排序的操作步骤如下： 首先将数组一份为二，分别为左数组和右数组 若左数组的长度大于1，那么对左数组实施归并排序 若右数组的长度大于1， 那么对右数组实施归并排序 将左右数组进行合并 代码如下： package main import ( "fmt" ) // mergerSort func mergerSort(arr []int, a, b int) { if b-a <= 1 { return } c := (a + b) / 2 mergerSort(arr, a, c) mergerSort(arr, c, b) arrLeft := make([]int, c-a) arrRight := make([]int, b-c) copy(arrLeft, arr[a:c]) cop...阅读全文
归并排序 在这里插入图片描述 func sortArray(nums []int) []int { if len(nums) <= 1 { return nums } partA := sortArray(nums[:len(nums)/2]) partB := sortArray(nums[len(nums)/2:]) temp := make([]int, len(partA) + len(partB)) aPointer := 0 bPointer := 0 i := 0 for aPointer < len(partA) && bPointer < len(partB) { if partA[aPointer] < partB[bPointer] { temp[i] = partA[...阅读全文
