使用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))
}

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