部分排序算法总结
关于排序通常所说的排序是指内部排序,即在内存里进行排序。相对应的有外部排序,当待排序数据比较多时,排序过程需要使用闪存。 排序算法大体可分为两种: 排序算法稳定性说明:如果待排序序列A中两个元素相等,即Ai = Aj,排序前Ai在Aj之前,排序后Ai还在Aj之前,则称这种排序算法是稳定的。就是保证排序前后两个相等的元素的相对顺序不变 以下为各算法的时间复杂度等对比
一些共用方法main包用来执行,myAlgo包为具体方法实现 //以下为共用方法 //交换两个元素位置 package myAlgo func exchange(arr []int,a int,b int) { temp := arr[a] arr[a] = arr[b] arr[b] = temp } //返回序列最小值下标 func selectMin(arr []int,i int) int { length := len(arr) minKey := i minValue := arr[minKey] //从下标为i及之后的元素中找出值最小的元素 for k := minKey + 1; k < length; k++ { if minValue > arr[k] { //修改下标 minKey = k minValue = arr[k] } } return minKey } 1、冒泡排序冒泡排序算法运行方式如下: 示意图
package main import ( "fmt" "myAlgo" ) func main() { arr := []int{15,45,42,25,20,63,23,29,100,9} myALgo.BubbleSort(arr); } package myAlgo import "fmt" func bubbleSort(arr []int) { length := len(arr) for j := length - 1; j > 0; j-- { //外层循环控制循环次数 for i := 0; i < j; i++ { //内层循环控制交换 if arr[i] > arr[i+1] { //交换顺序 exchange(arr,i,i+1) } } fmt.Println(arr) } } 结果如下
2、简单选择排序思路如下: 示意图 go实现 package main import "fmt" func main() { arr := []int{15,9} fmt.Println(arr) myAlgo.SelectSort(arr) } package myAlgo import "fmt" func SelectSort(arr []int) { fmt.Println("开始排序") length := len(arr) for i := 0; i < length; i++ { //每循环一次都找出当前未排序元素中的最小值,和当前元素进行交换 minKey := selectMin(arr,i) exchange(arr,minKey) } fmt.Println(arr) } 执行结果 3、直接插入排序这个类似于玩扑克牌,一张一张的将牌拿出来插到部分已经有序序列中的合适位置,具体如下: 示意图 go实现 package main import ( "fmt" "myAlgo" ) func main() { arr := []int{15,9} fmt.Println(arr) myAlgo.InsertSort(arr) } package myAlgo import "fmt" func InsertSort(arr []int) { fmt.Println("开始排序") //获取当前数组长度 length := len(arr) for i := 1; i < length; i++ { //当前值 now := arr[i] //如果当前元素小于之前序列中的某一个元素的值,则序列从此元素向后整体移动一位 for j := i - 1; j >= 0; j-- { if now < arr[j] { arr[j+1] = arr[j] arr[j] = now } else { arr[j+1] = now break } } fmt.Println(arr) } } 运行结果
快速排序算法原理: 示意图 go实现 package main import ( "fmt" "myAlgo" ) func main() { arr := []int{40,50,9} fmt.Println(arr) myAlgo.QuickSort(arr,len(arr) - 1) } package myAlgo import "fmt" func QuickSort(arr []int,left int,right int) { //设置基准数,选择第一个作为基准数 baseKey := left baseValue := arr[baseKey] fmt.Println("当前序列",arr[left:right+1],"基准值为",baseValue) fmt.Println("开始排序") i := left j := right for i < j { //先从右向左找,直到找到一个小于基准数的值 for (arr[j] >= baseValue) && (i < j) { j-- } if i < j { //将j的值放到i的空位上 arr[i] = arr[j] } //从左向右找,直到找到一个大于基准数的值 for (i < j) && (arr[i] < baseValue) { i++ } if i < j { //将此时的i放到之前j产生的空位上 arr[j] = arr[i] } fmt.Println(arr[left:right+1]) } arr[i] = baseValue fmt.Println("子序列结果",arr[left:right+1]) fmt.Println("总序列",arr) fmt.Println("--------------------") if left < i-1 { QuickSort(arr,left,i-1) } if i+1 < right { QuickSort(arr,i+1,right) } } 运行结果
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |