使用Golang实现经典排序算法【一】
实现冒泡排序、选择排序、插入排序、希尔排序。
文章目录
排序的基本概念
- 排序的稳定性:
分数 名字 10 甲 20 乙 10 丁 - 内排序与外排序
内排序:是整个排序过程中,所有记录全部放在内存中;如:插入排序、选择排序、交换排序、归并排序。
外排序:是由于需要排序的记录太多,不能同时放在内存中,整个排序过程需要在内外存之间多次交换数据。
冒泡排序
平均复杂度:O(n2) , 稳定性:稳定
package main
import "fmt"
func main() {
s := []int{1, 44, 4, 6, 74, 42, 346, 536, 453, 0, 0, 1, 1, 32, 3}
fmt.Println(bubbleSort2(s))
}
// 冒泡
func bubbleSort(s []int) []int {
for i := 0; i < len(s); i++ { // 控制次数
for j := 0; j < len(s)-1-i; j++ { //迭代比较
if s[j] < s[j+1] {
s[j], s[j+1] = s[j+1], s[j]
}
}
}
return s
}
// 增加哨兵提前结束的冒泡
func bubbleSort2(s []int) []int {
for i := 0; i < len(s); i++ {
mark := false
for j := 0; j < len(s)-1-i; j++ {
if s[j] < s[j+1] {
s[j], s[j+1] = s[j+1], s[j]
mark = true
}
}
if !mark {
fmt.Println("结束循环", i)
break
}
}
return s
}
简单选择排序
平均复杂度:O(n2) , 稳定性:稳定
/* 简单选择排序 */
func selectSort(s []int) []int {
for i := 0; i < len(s); i++ {
for j := i + 1; j < len(s); j++ {
if s[i] < s[j] { //相邻之间才叫做冒泡
s[j], s[i] = s[i], s[j]
}
}
}
return s
}
直接插入排序
平均复杂度:O(n2) , 稳定性:稳定
/* 直接插入排序
插入排序对数据的有要求,数据如果基本有序,那么效率就高。
与前两个的区别就是第二个循环不是写死的。
*/
func insertSort(s []int) []int {
for i := 1; i < len(s); i++ {
if s[i-1] < s[i] {
s[i-1], s[i] = s[i], s[i-1]
for j := i - 1; j > 0; j-- {
if s[j-1] < s[j] {
s[j-1], s[j] = s[j], s[j-1]
}
}
}
}
return s
}
希尔排序
平均复杂度:O(nlogn) ~ O(n2) , 最好的情况:O(n1.3) , 稳定性:稳定
/* 希尔排序
就是插入排序的近一步升级,跳动着来完成step步长的排序,
最后在步长为1的时候,执行插入排序
*/
func shellSort(s []int) []int {
length := len(s)
for step := length / 2; step > 0; step /= 2 { //这个循环是控制步长(通过步长分段)——最后一个一定要1
for j := 0; j+step <= len(s)-1; j += step { //开始执行循环,从头开始以步长step遍历
if s[j] < s[j+step] { //需要交换位置
s[j], s[j+step] = s[j+step], s[j]
for i := j; i-step > 0; i -= step { //换完位置后,执行插入排序的思路,完成之前需要的交换,达到基本有序
if s[i] > s[i-step] {
s[i], s[i-step] = s[i-step], s[i]
}
}
}
}
}
return s
}
主函数:
package main
import "fmt"
func main() {
s := []int{1, 44, 4, 6, 74, 42, 346, 536, 453, 0, 0, 1, 1, 32, 3}
// s := []int{1, 4, 5, 3, 6, 7, 8, 9}
// fmt.Println(bubbleSort2(s))
// fmt.Println(selectSort(s))
// fmt.Println(insertSort(s))
fmt.Println(s)
fmt.Println(shellSort(s))
fmt.Println(insertSort(s))
}
待续:堆排序,归并排序,快速排序.