使用Golang实现经典排序算法【一】

实现冒泡排序、选择排序、插入排序、希尔排序。

排序的基本概念

  1. 排序的稳定性：
    分数名字
    10甲
    20乙
    10丁
    对上述表格按分数从小到大排序之后，甲还是在丁的上面，原排列位置不变，就说明排序是稳定的；反之，排序之后，丁出现在甲的上面，则说明排序是不稳定的。
  2. 内排序与外排序
    内排序：是整个排序过程中，所有记录全部放在内存中；如：插入排序、选择排序、交换排序、归并排序。
    外排序：是由于需要排序的记录太多，不能同时放在内存中，整个排序过程需要在内外存之间多次交换数据。

冒泡排序

平均复杂度：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))
}

待续：堆排序，归并排序，快速排序.(已更)
【二】— 堆排序、归并排序、快速排序