go常用排序算法

go常用排序算法

go常用排序算法

之前写过一篇用java实现的常用排序算法的博客，可以参考，这次改用go语言实现，一来用来复习下排序算法，二来也可以学习下go语言，​​java常用排序算法总结​​

一，冒泡排序

/**冒泡排序 */func bubbleSort(data []int){ for i := 0;i < len(data) - 1;i++{ for j := 0;j < len(data) - i - 1;j++{ if data[j] > data[j + 1]{ //交换 data[j],data[j + 1] = data[j + 1],data[j] } } }}

在乱序的条件下，时间复杂度是O(N^2)，有序条件下时间复杂度是O(N)稳定排序空间复杂度：O(1)

二，选择排序

首先找到数组中的最小元素，然后将这个最小元素和数组的第一个元素交换位置，如果第一个元素就是最小元素，就和自己交换位置；再次，在剩下的元素中找到最小元素和数组中的第二个元素交换位置，如此往复，直到将整个数组排序，一句话总结就是，不断在剩余元素中找最小元素

/**选择排序 */func selectSort(data []int){ for i := 0;i < len(data) - 1;i++{ //每次循环找出 i + 1到数组最后一个元素的这个区间的最小值，然后最小值和当前元素data[i]比较 minIndex := i for j := i+1;j < len(data);j++{ if data[j] < data[minIndex]{ minIndex = j } } if i != minIndex{ data[i],data[minIndex] = data[minIndex],data[i] } }}

不稳定排序时间复杂度：O(n^2)空间复杂度：O(1)选择排序是数据移动最少的，每次交换两会改变两个数组元素的值，因此选择排序用了N次交换，交换次数和数组大小是线性关系

三，插入排序

与选择排序一样，当前索引左边的所有元素都是有序的，但是他们的最终位置还不确定，为了给更小的元素腾出空间，他们可能会被移动，但是当索引到达数组的末端，数组排序就完成了

/**插入排序 */func insertSort(data []int){ var j int for i := 1;i < len(data);i++{ temp := data[i] for j = i;j > 0 && temp < data[j - 1];j--{ data[j] = data[j - 1] } data[j] = temp }}

稳定排序时间复杂度分析：O(N^2)，如果序列在排序前已经是有序序列，则为O(N)空间复杂度分析：O(1)数据量较少时效率高。插入排序适合数据量少的情况算法的实际运行效率优于选择排序和冒泡排序。插入排序对于部分有序的数组很有效，部分有序的数组类如数组中每个元素距离他的最终位置不远，一个有序的大数组接一个小数组，数组中只有几个元素的位置不正确

四，希尔排序

希尔排序是一种基于插入排序的快速排序算法，对于大规模的数据，插入排序很慢，因为随着数据规模的增大，移动规模也可能随着增大，因为插入排序只会交换相邻的元素，元素只能一点点的从数组一端移动到指定位置，但是希尔排序是使用一种步长的思想，根据指定步长分为h个子数组，每个子数组进行插入排序，形成了h个有序子数组

/**希尔排序 */func shellSort(data []int){ var j int for h := len(data)/2;h > 0;h/=2{ //外层循环控制步长 for i := h;i < len(data);i++{ //内层循环是对步长个子数组做插入排序 temp := data[i] for j = i;j >= h && temp < data[j - h];j-=h{ data[j] = data[j - h] } data[j] = temp } }}

不稳定排序希尔排序的时间复杂度较直接插入排序低，它的时间是所取“增量”（步长gap）序列的函数。最好时间复杂度： O(n) – 有序情况下平均时间复杂度： O(1.2^n ~ 1.5^n) – Hibbard最坏时间复杂度： O(n^2) — 希尔增量空间复杂度：O(1)

五，快速排序

快速排序是将一个数组分成两个子数组，将两个子数组分别独立排序，当两个子数组有序时数组就有序，需要找到一个基准值来划分数组成两个子数组，分别是比基准值大和比基准值小，递归的进行排序

/**快速排序 */func quickSort(data []int){ if len(data) < 1{ return } l,r := 0,len(data) - 1 //基准值 base := data[0] for i := 0;i <= r;{ //比基准值大的放右边 if data[i] > base{ data[r],data[i] = data[i],data[r] r-- }else{ //比基准值小或等于的放左边 data[l],data[i] = data[i],data[l] l++ i++ } } quickSort(data[:l]) quickSort(data[l + 1:])}

时间复杂度：O(nlogn)空间复杂度：O(1)不稳定排序算法思想：分治

快速排序优化：

对于小数组，快速排序比插入排序要慢，所以当对小数组进行排序时，可以切换到插入排序

六，堆排序

堆排序是基于二叉堆（优先队列）实现的，通过建立最大堆或者最小堆，删除堆顶的最值元素后将堆顶元素放入指定集合，重新建堆，最后集合便是有序序列

/**堆排序*/func heapSort(data []int){ m := len(data) s := m / 2 for i := s;i >= 0;i--{ heap(data,i,m - 1) } for i := m - 1;i > 0;i--{ data[i], data[0] = data[0], data[i] heap(data, 0, i-1) }}//以i为根节点建堆func heap(data []int,i int,end int){ //左子节点 l := 2 * i + 1 if l > end{ return } n := l //右子节点 r := 2 * i + 2 //当前最大元素是右子节点 if r <= end && data[r] > data[n]{ n = r } if data[i] > data[n]{ return } //比根节点大则交换 data[i],data[n] = data[n],data[i] //往下建堆 heap(data,n,end)}

不稳定排序时间复杂度：O(nlogn)

七，归并排序

归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序

/**归并排序 */func mergeSort(data []int)(result []int){ if len(data) <= 1{ return data } mid := len(data) / 2 //分治排序左子数组 left := mergeSort(data[:mid]) //分治排序右子数组 right := mergeSort(data[mid:]) //分开排序后合并成一个新数组，此时原数组已经有序 return merge(left,right)}func merge(left []int,right []int)(result []int){ l,r := 0,0 //排序，左右两边比较，放入result for l < len(left) && r < len(right){ if left[l] > right[r]{ result = append(result,left[l]) l++ }else{ result = append(result,right[r]) r++ } } result = append(result,left[l:]...) result = append(result,right[r:]...) return}

算法思想：分治时间复杂度：O(nlogn)空间复杂度：O(n)稳定排序

八，计数排序

/**计数排序 */func countSort(data []int){ min := getMin(data) max := getMax(data) //建立辅助数组 c := make([]int, max - min + 1) for i := range data{ //以跟最小值的差为下标计数 j := data[i] - min c[j]++ } k := 0 //恢复数组 for i := range c{ for ; c[i] != 0 ;{ data[k] = i + min k++ c[i]-- } }}func getMax(data []int)(m int){ max := 0 for i := 0;i < len(data);i++{ if max < data[i]{ max = data[i] } } return max}func getMin(data []int)(m int){ min := 0 for i := 0;i < len(data);i++{ if min > data[i]{ min = data[i] } } return min}

稳定排序其空间复杂度和时间复杂度均为O(n+k)线性时间复杂度，其中k是整数的范围（取决于辅助数组大小）非比较排序计数排序其实是桶数取 max - min + 1最大时的桶排序

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。