Collection of algorithm for sortingheap sort 堆排序 The heapsort algorithm can be divided into two parts. In the first step, a heap is built outof the data. The heap is often placed in an array with the layout of a complete binary tree. The complete binary tree maps the binary tree structure into the array indices; each array index represents a node; the index of the n...
选择排序选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。 选择排序是不稳定的。算法复杂度是O(n ^2 )。 个人总结: 选择排序,就是要又一个游标,每次在做比较的同时,纪录最大值,或者最小值的位置,遍历一遍之后,跟外层每次纪录的位置,做位置交换。为什么叫选择排序呢,估计就是这个原因,每次遍历一遍,选个...
使用Golang实现以下排序算法:冒泡排序选择排序插入排序快速排序并打印时间进行比较。主函数package mainimport ("fmt""math/rand""sort""time" )const (num = 10000// 测试数组的长度rangeNum = 100000// 数组元素大小范围)func main() {arr := GenerateRand() //生成随机数组//排序前 复制原数组orgArr := make([]int, num)copy(orgArr, arr)start := time.Now() // 获取当前时间//bubbleSort(arr) //冒 泡//selectSort(arr...
package mainimport "fmt"func xpx(a []int){for i := 0;i<len(a);i++{min := a[i]for j := i+1;j<len(a);j++{if a[j] < min{a[i],a[j] = a[j],a[i]}}} }func tpx(a []int){max_a := a[0]for _,v := range a{if v > max_a{max_a = v}}a_l := make([]int,max_a + 1)for _,v := range a{a_l[v] += 1}for k := 0 ;k<len(a);{for i:=0;i<len(a_l);i++{if a_l[i] != 0{for j:=0;j<a_l[i];j++{a[k] = ik ++}}}}fmt.Printf("%p\n",a) }fun...
1. 插入排序 // 排序函数 func sortarr(arr *[]int) *[]int { for i := 1; i <len(*arr);i++{maxindex := (*arr)[i] // 默认一个数为最大值index := i -1 // index从0开始for index >=0&&(*arr)[index] > maxindex{ // index大于等于0,如果数组中有比maxindex值大的做下面处理(*arr)[index+1] = (*arr)[index] // 复制一个(*arr)[index]到(*arr)[index+1]占位index-- // 移动index比对下一个}if index +1 != i{ // 如果 i...
快速排序算法原理: b站https://b23.tv/uJqRYN package mainimport "fmt"//[]int{1,2,3,4,5,6,7,8} func qsort(ori []int) []int {copy := append([]int{}, ori...)var inner func(ori []int)inner = func(ori []int) {if len(ori) == 0 || len(ori) == 1 {return}//找一个参考点最左边 元素个数>=2之后进行比较ref := ori[0]var i, j intloopj := truefor i, j = 0, len(ori)-1; i != j; {if loopj {if ori[j] < ref {ori[i] = or...
插入排序 插入排序,一般我们指的是简单插入排序,也可以叫直接插入排序。就是说,每次把一个数插到已经排好序的数列里面形成新的排好序的数列,以此反复。 插入排序属于插入类排序算法。 除了我以外,有些人打扑克时习惯从第二张牌开始,和第一张牌比较,第二张牌如果比第一张牌小那么插入到第一张牌前面,这样前两张牌都排好序了,接着从第三张牌开始,将它插入到已排好序的前两张牌里,形成三张排好序的牌,后面第四张牌继续插入...
希尔排序 1959 年一个叫Donald L. Shell (March 1, 1924 – November 2, 2015)的美国人在Communications of the ACM 国际计算机学会月刊发布了一个排序算法,从此名为希尔排序的算法诞生了。 注:ACM = Association for Computing Machinery,国际计算机学会,世界性的计算机从业员专业组织,创立于1947年,是世界上第一个科学性及教育性计算机学会。 希尔排序是直接插入排序的改进版本。因为直接插入排序对那些几乎已经排好序的数...
排序算法 人类的发展中,我们学会了计数,比如知道小明今天打猎的兔子的数量是多少。另外一方面,我们也需要判断,今天哪个人打猎打得多,我们需要比较。 所以,排序这个很自然的需求就出来了。比如小明打了5只兔子,小王打了8只,还有部落其他一百多个人也打了。我们要论功行赏,谁打得多,谁就奖赏大一点。 如何排序呢,怎么在最快的时间内,找到打兔子最多的人呢,这是一个很朴素的问题。 经过很多年的研究,出现了很多的排序算...
选择排序 选择排序,一般我们指的是简单选择排序,也可以叫直接选择排序,它不像冒泡排序一样相邻地交换元素,而是通过选择最小的元素,每轮迭代只需交换一次。虽然交换次数比冒泡少很多,但效率和冒泡排序一样的糟糕。 选择排序属于选择类排序算法。 我打扑克牌的时候,会习惯性地从左到右扫描,然后将最小的牌放在最左边,然后从第二张牌开始继续从左到右扫描第二小的牌,放在最小的牌右边,以此反复。选择排序和我玩扑克时的排序...