冒泡排序

funcBubbleSort(vector[]int){
fmt.Println("BubbleSort")
fmt.Println(vector)
fori:=0;i<len(vector);i++{
tag:=true//为了剪枝
//每一趟将最大的数冒泡
forj:=0;j<len(vector)-i-1;j++{
ifvector[j]>vector[j+1]{/*vector[j]<vector[j+1]*/
temp:=vector[j]
vector[j]=vector[j+1]
vector[j+1]=temp
tag=false
}
}
iftag{
break//0~len(vector)-i没有发生交换说明已经有序
}
fmt.Println(vector)
}
}

插入排序

funcInsertSort(vector[]int){
fmt.Println("InsertSort")
fmt.Println(vector)
fori:=1;i<len(vector);i++{
//每一趟不满足条件就选择i为哨兵保存，将哨兵插入0~i-1有序序列（0~i-1始终是有序的）
ifvector[i]<vector[i-1]{/*vector[i]>vector[i-1]*/
temp:=vector[i]
//后移直到找到哨兵合适的位置
j:=i-1
for;j>=0&&vector[j]>temp;j--{/*vector[j]<temp*/
vector[j+1]=vector[j]
}
//插入位置前后都是有序的，最后也是有序的
vector[j+1]=temp
}
fmt.Println(vector)
}
}

选择排序

funcSelectSort(vector[]int){
fmt.Println("SelectSort")
fmt.Println(vector)
fori:=0;i<len(vector);i++{
//选择最小的元素
k:=i
forj:=i+1;j<len(vector);j++{
ifvector[k]>vector[j]{
k=j
}
}
//交换
ifk!=i{
temp:=vector[i]
vector[i]=vector[k]
vector[k]=temp
}
fmt.Println(vector)
}
}

二元选择排序

funcBinarySelectSort(vector[]int){
fmt.Println("SelectSort")
fmt.Println(vector)
n:=len(vector)
fori:=0;i<n/2;i++{
//选择最小的元素和最大元素
k:=i
t:=n-i-1
forj:=i+1;j<=n-i-1;j++{
ifvector[k]>vector[j]{
k=j
}
ifvector[t]<vector[j]{
t=j
}
}
//交换
ifk!=i{
temp:=vector[i]
vector[i]=vector[k]
vector[k]=temp
}
ift!=n-i-1{
temp:=vector[n-i-1]
vector[n-i-1]=vector[t]
vector[t]=temp
}
fmt.Println(vector)
}
}

快速排序

简单的说快速排序就是挖坑填数然后分治，公认效率最好，这个必须会

funcQuickSort(vector[]int,low,hightint){
	fmt.Println(vector)
	iflow<hight{
		i:=low
		j:=hight
		temp:=vector[low]//开始挖坑填数
		fori<j{
			fori<j&&vector[j]>=temp{
				j--
			}
			vector[i]=vector[j]
			fori<j&&vector[i]<=temp{
				i++
			}
			vector[j]=vector[i]
		}
		vector[i]=temp
		QuickSort(vector,i-1)//分治
		QuickSort(vector,i+1,hight)
	}
}

常见问题，已知序列WAUSTHKO，将第一个数作W为基数，问：

1，第一趟后的序列是多少？假设递归同时进行

1），OAUSTHKW

2），KAHOTSUW

3），HAKOSTUW

4），AHKOSTUW

2，排序过程中那些数会被作为选基数？

以上标记的都是：W，O，K、T，H

3，基数的选择直接影响到效率，同时排序末尾显然有效率问题，可以用其他算法替换。