全文所说排序默认升序
- 插入排序
- 直接插入
- 二分插入
- 希尔排序
- 交换排序
- 冒泡排序
- 快速排序
- 选择排序
- 简单选择排序
- 堆排序
- 归并排序
一、插入排序
选择一个元素插入到有序序列中去，使序列仍保持有序
1.直接插入排序：从序列中选择一个元素 p ，依次和它前面的每个元素 f 比较，如果 p < f，就把 f 向后移动，直到最终 p >= f，则将p的值放在当前 f 的后面
func SInsertSort(arr []int) {
for i:=1;i<len(arr);i++ {
p := arr[i]
j := i-1
for j>=0 && p < arr[j] {
arr[j+1] = arr[j]
j--
}
arr[j+1] = p
}
}
最坏时间复杂度：元素arr[i]要和前面的每一个元素比较，比较次数为 i*i。
所以 1 + 2 +... + n-1 = O(n^2) =
平均时间复杂度：因为arr[i]的平均比较次数为 。
所以 ≈
=
空间复杂度：S(n) = O(1)
稳定性：稳定（原来相等的元素相对位置不会边）
2.二分插入排序：
利用二分查找确定应该插入的位置，可以较少比较次数，但是元素移动次数不会减少
func BInsertSort(arr []int) {
for i := 1; i < len(arr); i++ {
p := arr[i]
left := 0
right := i - 1
for right >= left {
mid := (left + right) / 2
if p < arr[mid] {
right = mid - 1
} else {
left = mid + 1
}
}
for j := i - 1; j >= left; j-- { //left就是p应该放置的位置
arr[j+1] = arr[j]
}
arr[left] = p
}
fmt.Println("二分插入", arr)
}
left就是p最终放置位置的原因：
right >= left 最后一次为true时，只能是right-left == 0；或者right-left=1；分析这两种情况，可以发现left都应该是最终放置位置。
因为只是减少了一些比较的次数，移动次数还是不变，所以耗时是要少一些，但复杂度肯定仍旧是
最坏时间复杂度： =
平均时间复杂度： =
空间复杂度：S(n) = O(1)
稳定性：稳定（原来相等的元素相对位置不会边）
3.希尔排序：二分和直插的移动过程，都是每次移动一步，比如第9个元素，确定其最终该放置在arr[2]，那就要依次移动[2,8]的所有元素，要移动7次。希尔排序的出发点是希望降低移动次数。希尔排序是设计想法是多次排序，刚开始每次移动一大步，使其离最终位置比较接近。
过程：确定一组降序的增量序列，比如9，5，3，1，依次用来对原序列进行排序。比如用9排序，将如下位置的元素排序
[0] [9] [18] [27]... 排序,假如为abcd，排序后变成[0]=c, [9]=a, [18]=b, [27]=d
[1] [10] [19] [28]... 排序
[2] [11] [20] [29]... 排序
....
用增量5对新序列再次排序
[0] [5] [10] [15]...
[1] [6] [11] [16]...
[2] [7] [12] [17]...
5排序就是把afk三个之间交换位置，bgl三个之间交换位置...
func ShellSort(arr []int) {
ds := []int{9, 5, 3, 1}
for i := 0; i < len(ds); i++ {
d := ds[i]
for j := d; j < len(arr); j++ {
p := arr[j]
k := j - d
for k >= 0 && p < arr[k] { // 对每个子序列进行直接插入排序，也可以改成二分或其他
arr[k+d] = arr[k]
k -= d
}
arr[k+d] = p
}
}
fmt.Println("希尔排序", arr)
}
// 希尔+二分插入
func ShellSort(arr []int) {
ds := []int{3, 1}
for i := 0; i < len(ds); i++ {
d := ds[i]
for j := d; j < len(arr); j++ {
p := arr[j]
left := j % d
right := j - d
for right >= left {
mid := ((right-left)/d/2)*d + left
if p < arr[mid] {
right = mid - d
} else {
left = mid + d
}
}
for k := j - d; k >= left; k -= d {
arr[k+d] = arr[k]
}
arr[left] = p
}
}
fmt.Println("希尔排序", arr)
}
增量序列的选取要求：
- 递减
- 最后一个值必须是1
时间复杂度： 与增量序列的选取有关，分析难度较大，下面是几个序列的结论
空间复杂度：S(n) = O(1)稳定性：不稳定。比如 1，3，2，2' 增量序列选 2，1，得到 1 2' 2 3
二、交换排序
比较元素的大小，根据结果交换位置
1.冒泡排序
下降法：从开头向后扫描，将大的放到后面去
上升法：从末尾向前扫描，将小的放到前面去
func BubbleSort() {
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
for sortedLen := 0; sortedLen < len(arr)-1; sortedLen++ {
for j := len(arr) - 1; j >= 1+sortedLen; j-- {
p := arr[j]
if p < arr[j-1] {// 上升法，把小的换到前
arr[j] = arr[j-1]
arr[j-1] = p
}
}
}
fmt.Println("冒泡排序", arr)
}
缺点：该序列已经全部有序时，程序不能感知到。比如 1,2,5,3，第一次上升后就已经全部有序了。
改进：
func BubbleSort() {
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
sortedLen := 0
hasUnSorted := true
for hasUnSorted {
hasUnSorted = false
for j := len(arr) - 1; j >= 1+sortedLen; j-- {
p := arr[j]
if p < arr[j-1] {
arr[j] = arr[j-1]
arr[j-1] = p
hasUnSorted = true
}
}
sortedLen++
}
fmt.Println("冒泡排序", arr)
}
该版本还有缺点，每次可能还会和已经有序的部分比较一下。比如4,5,6,9,8,7，第一轮从头到尾交换后，得到4,5,6,7,9,8, 第二轮比较就应该在7之后的位置停止
下面是一个改进，记录了上一轮冒泡将最小元素放在了x处，下一次上升的上限就应该是停止处之后（记作x+1）。
func BubbleSort() {
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
i := 0
for i <= len(arr)-2 {
j := len(arr) - 2
for j >= i {
p := arr[j]
if p > arr[j+1] {
arr[j] = arr[j+1]
arr[j+1] = p
}
j--
}
i = j + 2
}
fmt.Println("冒泡排序", arr)
}
最坏时间复杂度：任意两个元素之间都逆序，最多就有个逆序，每次交换能减少一个逆序。
=
平均时间复杂度： 逆序平均为，所以
=
≈
空间复杂度：S(n) = O(1)
稳定性：稳定（原来相等的元素相对位置不会边）
2.快速排序
快速排序，任意选择一个元素，将比它大的放在其后，比它小的放在它前面。然后再分别对前后两端再次执行此操作。
func QuickSort(arr []int, i int, j int) {
v := arr[i]
pv := i
d := "end"
for j > i {
if d == "end" {
if arr[j] < v {
arr[i] = arr[j]
pv = j
i++
d = "start"
} else {
j--
}
}
if d == "start" {
if arr[i] > v {
arr[j] = arr[i]
pv = i
j--
d = "end"
} else {
i++
}
}
}
arr[pv] = v
if pv-1-i > 0 {
QuickSort(arr, i, pv-1)
}
if j-pv-1 > 0 {
QuickSort(arr, pv+1, j)
}
}
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
QuickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
最好时间复杂度：O(nlogn)
最坏时间复杂度：O(n^2)
平均时间复杂度：O(nlogn)
空间复杂度：O(logn)
三、选择排序
每次选出最大或最小的放到后面或前面
1.简单选择排序
func SimpleSelectSort(arr []int) {
for i:=0;i<len(arr)-1;i++ {
min := i
for j:=i+1;j<len(arr);j++ {
if arr[j] < arr[min] {
min = j
}
}
v := arr[i]
arr[i] = arr[min]
arr[min] = v
}
}
时间复杂度： =
空间复杂度：S(n) = O(1)
稳定性：稳定（原来相等的元素相对位置不会边）
2.堆排序
堆是一种特殊的完全二叉树，如果 父节点p子节点c，称大根堆。父节点p
子节点c，称小根堆。
堆排序就是将序列排成堆（利用顺序存储的话，只需要调整序列位置即可），这样根结点就是最大值（大根堆），然后将根结点和尾结点交换，这样就最大元素就放在了正确的位置上，然后再重新堆化前面的序列，再选出当前堆的最大，放到倒数第二个位置上...
举例说明：
原始序列[]int{9, 5, 47, 11, 19, 6, 34, 31, 2, 10,}待使用堆排序方法排序。
将其看作一棵顺序存储的完全二叉树
从最后一个非叶结点开始向前遍扫描，遇到不符合堆序的就调整顺序。
- arr[4]=19，符合堆序（大于它的所有子节点）
- arr[3]=11，不符合堆序，arr[3] < arr[7]，交换arr[3]和arr[7]，得到arr[3]=31,arr[7]=11
- arr[2]=47，符合堆序
- arr[1]=5，不符合堆序，arr[1]<arr[3]=31，交换arr[1]和arr[3]，得到arr[1]=31，arr[3]=5。此时arr[3]=5<arr[7]=11，再次不符合堆序，交换arr[3]和arr[7]，得到arr[3]=11,arr[7]=5
- arr[0]=9，不符合堆序，arr[0]<arr[2]...
这样就得到了堆化好的序列 []int{47,31,34,11,19,6,9,5,2,10,}
完成了堆化之后，只需要重复 “找最大值(即当前堆根)” + “和堆尾元素交换位置” + “堆长度-1” + “重新堆化”，n-1遍即可。
第一步，交换arr[0]和arr[9]，堆范围从arr[0]~arr[9]变成arr[0]~arr[8]
第二步，重新堆化，只需从根开始调整就行
重复...
func HeapSort() {
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
for i := (len(arr) - 2) / 2; i >= 0; i-- {
// (len(arr) - 2)/2是最后一个结点的父节点，也就是最后一个非叶结点
heapfy(arr, i, len(arr)-1)
}
for j := 0; j < len(arr)-1; j++ {
max := arr[0]
arr[0] = arr[len(arr)-1-j]
arr[len(arr)-1-j] = max
heapfy(arr, 0, len(arr)-1-j-1)
}
fmt.Println("堆排序", arr)
}
func heapfy(arr []int, root int, end int) {
leftSon := 2*root + 1
if leftSon > end {
return
}
rightSon := 2*root + 2
max := leftSon
v := arr[root]
if rightSon <= end && arr[rightSon] > arr[leftSon] {
max = rightSon
}
if v < arr[max] {
arr[root] = arr[max]
arr[max] = v
if max*2+1 <= end {
heapfy(arr, max, end)
}
}
}
完全二叉树的顺序存储，通常从数组位置1开始存储，这样比较方便计算父子结点位置。如果一个结点在数组中的index是i，那其左子结点是2i，右子是2i+1，父结点是i/2（向下取整）。如果要从0开始存储的话，每个元素的index都会减少1，i变成i-1，设i-1=k，2i变成2i-1=2k+1，... 可以推出新的关系是 原结点k，左子节点2k+1， 右子结点2k+2 父结点 (k-1)/2 (下整)
平均时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定
归并排序
归并排序是利用分治思想，欲排序abcd，先将ab，cd分别排序，然后再合并两个有序表。
func MergeSort(arr []int) {
if len(arr) < 2 {
return
}
if len(arr) == 2 {
v := arr[0]
if v > arr[1] {
arr[0] = arr[1]
arr[1] = arr[0]
}
return
}
mid := len(arr) / 2
MergeSort(arr[:mid])
MergeSort(arr[mid:])
merge(arr)
}
func merge(arr []int) {
mid := len(arr) / 2
i := 0
j := mid
k := 0
tempArr := make([]int, len(arr))
for i < mid && j < len(arr) {
if arr[i] <= arr[j] {
tempArr[k] = arr[i]
i++
k++
} else {
tempArr[k] = arr[j]
j++
k++
}
}
for i < mid {
tempArr[k] = arr[i]
i++
k++
}
for j < len(arr) {
tempArr[k] = arr[j]
j++
k++
}
for i2, v := range tempArr {
arr[i2] = v
}
}
非递归版本如下：
func MergeSort(arr []int) {
segLen := 1
for segLen < len(arr) {
for i := 0; i < len(arr); i += 2 * segLen {
merge(arr, i, i+segLen)
}
segLen *= 2
}
fmt.Println("归并排序", arr)
}
func merge(arr []int, start1 int, start2 int) {
if start2 > len(arr)-1 {
return
}
segLen := start2 - start1
end2 := start2 + segLen - 1
if end2 > len(arr)-1 {
end2 = len(arr) - 1
}
p1 := start1
p2 := start2
i := 0
tempArr := make([]int, end2-start1+1)
for p1 < start2 && p2 <= end2 {
if arr[p1] <= arr[p2] {
tempArr[i] = arr[p1]
i++
p1++
} else {
tempArr[i] = arr[p2]
i++
p2++
}
}
for p1 < start2 {
tempArr[i] = arr[p1]
i++
p1++
}
for p2 <= end2 {
tempArr[i] = arr[p2]
i++
p2++
}
for j := 0; j < len(tempArr); j++ {
arr[start1+j] = tempArr[j]
}
}
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定
