不同的排序方式，如有错误请评论指出，我会及时更改
冒泡排序及其优化
冒泡排序 稳定排序，平均复杂O(n^2) 最优 O(n)
//冒泡排序及其优化，优化后最优解可以O(n),
//初始版本
func Bubble(array []int) {
//次数小于长度-1，因为内层循环会+1
for i:=0;i<len(array)-1;i++{
for j:=0;j<len(array)-i-1;j++{
if array[j]>array[j+1]{
array[j],array[j+1] = array[j+1],array[j]
}
}
}
}
//优化方式1,增加flag判断
func BubbleOne(array []int) {
flag:=false
for i:=0;i<len(array)-1;i++{
flag = false
for j:=0;j<len(array)-i-1;j++{
if array[j]>array[j+1]{
array[j],array[j+1] = array[j+1],array[j]
flag = true
}
}
//未执行则已经有序
if !flag{
return
}
}
}
//优化方式2，在1的基础上
//增加position记录最后交换的位置j，下次不再判断后面的数字
func Bubbletwo(array []int) {
//加入flag,判断是否提前结束
flag:=false
length:=len(array)-1
//记录最后一次交换的位置，后面没有交换，为有序
position:=0
for i:=0;i<len(array)-1;i++{
flag = false
for j:=0;j<length;j++ {
if array[j]>array[j+1]{
array[j],array[j+1] = array[j+1],array[j]
flag = true
position = j//记录最后一次交换次数
}
fmt.Printf("外层%d，内层%d
",i,j)
}
if !flag{
break
}
length = position
}
}
选择排序
//选择排序，选择最小和开始交换
好坏平均复杂度 O(n^2) 不稳定
func SelectSort(array []int) {
index:=0
for i:=0;i<len(array)-1;i++{
index = i
for j:=i+1;j<len(array);j++{
//比最小的小，则更新最小index
if array[index]>array[j]{
index = j
}
}
//交换
array[i],array[index]=array[index],array[i]
}
}
插入排序
插入排序 稳定排序 时间O(n^2)
func Inserts(nums []int,n int) {
var j int
for i:=1;i<n;i++{
if nums[i]<nums[i-1]{
//保存临时数据，数组数据后移
tmp:=nums[i]
//注意边界 j>0
for j=i;j>0&&nums[j-1]>tmp;j--{
nums[j] = nums[j-1]
}
nums[j] = tmp
}
}
}
快排及其优化
快排 不稳定排序 O(nlogn) 还有多路快排优化
- 初始版本
//j = len(array)-1
func Fast(array []int,i,j int) {
left:=i
right:=j
//超出范围 退出，递归停止条件
if left>right{
return
}
tmp:=array[left]
for left<right{
for left<right&&array[right]>=tmp{
right--
}
array[left] = array[right]
for left<right&&array[left]<=tmp{
left++
}
array[right] = array[left]
}
array[left] = tmp
Fast(array,i,left-1)
Fast(array,left+1,j)
}
- 三路快排
三路快排，分三部分，1小于tmp部分，等于tmp部分，大于tmp部分
var count int //可以去掉，用来打印看下是否更快
func FastThree(array []int,low,high int){
i:=low
j:=low
tmp:=array[low]
k:=high
if low>=high{
return
}
//此处为k
for i<=k{
if array[i]<tmp{
//小于部分和前面等于的最左边互换，然后当前位置不比较，++
array[i],array[j] = array[j],array[i]
i++
j++
}else if array[i]>tmp{
//大于的放在右边，然后i不加，因为更换位置后此处的大小未知
array[k],array[i] = array[i],array[k]
k--
}else{
i++
}
}
count++
fmt.Println("time",count)
FastThree(array,low,j-1)
FastThree(array,k+1,high)
}
归并排序
稳定排序 时间O(nlogn) 空间O(n) 有多路归并
归并可以结合很多其他知识 链表，树等等,分治思想很重要（至少面试会问）
海量数据排序可以使用多路归并
func MergeSort(array []int)[]int {
//单个数据时返回，递归停止条件
if len(array)<2{
return array
}
//递归分割左右，想好递归停止的条件，分治
mid:=len(array)/2
left:=MergeSort(array[:mid])
right:=MergeSort(array[mid:])
return merge(left,right)
}
//合并两个有序链表类似的做法
func merge(left,right []int) []int {
//额外的返回空间
res:=make([]int,0)
i,j:=0,0
for i<len(left)&&j<len(right){
//<=是稳定的关键点
if left[i]<=right[j]{
res = append(res,left[i])
i++
}else{
res = append(res,right[j])
j++
}
}
//这里偷懒了，可以自己写详细些
/*if i==len(left){
res = append(res,right[j:]...)
}else{
res = append(res,left[i:]...)
}*/
//详细写法
//left right 其中一个没有结束
if i<len(left){
for i<len(left){
res = append(res,left[i])
i++
}
}else{
for j<len(right){
res = append(res,right[j])
j++
}
}
return res
}
希尔排序
间隔插入排序 懒得写了
堆排序
堆排序 不稳定 时间复杂O(nlogn)
topk问题，优先队列实现，建议手动写堆写下合并链表的题目
leetcode 合并k个排序链表，最优解使用优先队列，和堆有关
func HeapSort (array []int) {
//建堆，从后向前建立堆
for i:=len(array)/2-1;i>=0;i--{
sink(array,i,len(array))
}
for i:=len(array)-1;i>=0;i--{
array[0],array[i] = array[i],array[0]
sink(array,0,i-1)
}
}
//下沉，堆排序最关键堆核心
//想得到从小到大的数据，需要大顶堆，最大放在结尾，最后是小到大顺序
func sink(array []int,start ,length int) {
for{
next:=2*start+1
//超出范围 退出循环
if next>length{
break
}
//找最大的值和上层互换 （next+1<=length不是next+1<length） 因为length不会越界
if next+1<=length&&array[next+1]>array[next]{
next++
}
//上层已经大于下面，不用下沉，直接退出循环
if array[start]>array[next]{
break
}
//互换后继续寻找，可能继续下沉
array[start],array[next] = array[next],array[start]
start = next
}
}
- 另外一种堆排写法，差不多
func sortArray(nums []int) []int {
return heapsort(nums)
}
func heapsort(nums []int)[]int{
//从后向前建堆
end:=len(nums)-1
for i:=end/2;i>=0;i--{
sink(nums,i,end)
}
//顶部最大，跟尾部互换长度减小
for i:=end;i>=0;i--{
nums[0],nums[i] = nums[i],nums[0]
end--
sink(nums,0,end)
}
return nums
}
func sink(nums []int,root int,end int){
for {
child:=2*root+1
if child>end{
return
}
if child<end&&nums[child]<=nums[child+1]{ //可以等于end
child++
}
if nums[root]>nums[child]{
return
}
//互换，下沉
nums[root],nums[child] = nums[child],nums[root]
root = child
}
}
自行验证
func main() {
array:=[]int{2,1,5,8,5,6,3,2,7}
//arra:=[]int{2,1,5,8}
//insertSort(array,9)
//Fast(array,0,8)
//CreateHeap(array)
//Inserts(array,9)
//res:=MergeSort(array)
HeapSort(array)
fmt.Println(array)
fmt.Println(array[:len(array)])
}