饿虎岗资源网 Design By www.oxmxm.com
再次研究了插入排序的概念:定义一个有序的数据序列a,将待排序的序列b中的数依次插入到a的合适位置,插入后仍然有序
总结其与冒泡、选择的区别在于,内部迭代的次数是逐渐增大的,二后两者随着排序进行迭代次数逐渐减少
尝试基于Go的实现:
插入排序都采用in-place在数组上实现。具体算法描述如下:
- 从第一个元素开始,该元素可以认为已经被排序 取出下一个元素
- 在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后
- 将新元素插入到该位置后
- 重复步骤2~5
两种实现方式:1,新建切片; 2,在原切片中进行元素交换
方式一:新建切片
package main import "fmt" func main() { arr := []int{1, 0, 5, 7, 8, 5, 3, 6, 9, 2, 54, 33, 66} newArr := []int{} insertionSort(arr, &newArr) fmt.Println(newArr) } /** 插入排序法:取原数组old中第一个值作为新数组中的第一个值,然后遍历old,将每个元素按照条件插入到新数组中 时间复杂度:O(n^2) */ func insertionSort(old []int, new *[]int) { if len(*new) == len(old) { return } current := len(*new) *new = append(*new, old[current]) sort(*new) insertionSort(old, new) } func sort(arr []int) { for i := len(arr) - 1; i > 0; i-- { if arr[i] < arr[i-1] { arr[i], arr[i-1] = arr[i-1], arr[i] } } }
注意:insertionSort()函数中的第二个参数为切片的指针,不然打印出来的的新数组为空
原因:虽然切片是指针传递,这是指切片内的各个元素是指针传递,对于切片本身仍是值传递
证明:
package test import ( "fmt" "testing" ) func TestSlice(t *testing.T) { slice1 := []string{"zhang", "san"} fmt.Printf("%p\n", &slice1) fmt.Printf("%p\n", &slice1[1]) modify(slice1) fmt.Println(slice1) } func modify(data []string) { fmt.Printf("%p\n", &data) fmt.Printf("%p\n", &data[1]) data[1] = "si" }
打印结果:
0xc0420e4680
0xc0420e46b0
0xc0420e46c0
0xc0420e46b0
[zhang si]
引申:Go 语言里的引用类型有如下几个:切片、映射、通道、接口和函数类型。当声明上述类型的变量时,创建的变量被称作标头(header)值。从技术细节上说,字符串也是一种引用类型。每个引用类型创建的标头值是包含一个指向底层数据结构的指针。因为标头值是为复制而设计的,所以永远不需要共享一个引用类型的值。标头值里包含一个指针,因此通过复制来传递一个引用类型的值的副本,本质上就是在共享底层数据结构
结论:不会对切片进行增加或删除操作时(也就是长度不会改变),切片作为参数在函数间的传递不需使用指针。但是如果切片需要进行增加或删除元素的操作,并且原函数需要调用更新后的切片,那么在原函数调用其它函数时,就需要用切片的指针作为参数。
方式二:在原切片中进行元素交换
func method2(arr []int) { if len(arr) < 2 { return } for i := 1; i < len(arr); i++ { for j := i; j > 0; j-- { if arr[j] < arr[j-1] { arr[j], arr[j-1] = arr[j-1], arr[j] } } } }
由于不用创建新的切片,不用进行插入操作,只需要交换操作,所以要较方法一速度快些
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
饿虎岗资源网 Design By www.oxmxm.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
饿虎岗资源网 Design By www.oxmxm.com
暂无评论...
更新日志
2024年05月20日
2024年05月20日
- 张琍敏1978-雪中莲[台湾复刻版][WAV+CUE]
- 叶蕴仪1993-睡美人[日本版][WAV+CUE]
- 夜晚助兴音乐-群星《新时代床头音乐-性能量》2CD[WAV]
- 24K德国HD金碟《历届奥斯卡获奖金曲》3CD[WAV整轨]
- 邰正宵《重燃爱恋 贰 Walk On》[FLAC/分轨][431.72MB]
- 苏文劭《雨停出来走走》[320K/MP3][81.11MB]
- 苏文劭《雨停出来走走》[FLAC/分轨][210.76MB]
- 群星《2024好听新歌04》十倍音质WAV分轨
- 陈宁《弹指之间HQ》头版限量[低速原抓WAV+CUE]
- 陈宁《故人还》HQCDII限量签名版[低速原抓WAV+CUE]
- 苏文劭《春曲(Lessons)》[320K/MP3][39.8MB]
- 苏文劭《春曲(Lessons)》[FLAC/分轨][97.78MB]
- 群星《2006香港高级视听展原音精选 SACD》[ISO][2G]
- 张琍敏1977-枫林小雨[台湾复刻版][WAV+CUE]
- 林一峰2014-COOKINGMUSIC[香港首版][WAV+CUE]