部分排序算法总结

关于排序

通常所说的排序是指内部排序，即在内存里进行排序。相对应的有外部排序，当待排序数据比较多时，排序过程需要使用闪存。

排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

排序算法稳定性说明：如果待排序序列A中两个元素相等，即A_i = A_j，排序前A_i在A_j之前，排序后A_i还在A_j之前，则称这种排序算法是稳定的。就是保证排序前后两个相等的元素的相对顺序不变

以下为各算法的时间复杂度等对比

一些共用方法

main包用来执行，myAlgo包为具体方法实现

//以下为共用方法

//交换两个元素位置
package myAlgo
func exchange(arr []int, a int, b int) {
    temp := arr[a]
    arr[a] = arr[b]
    arr[b] = temp
}

//返回序列最小值下标
func selectMin(arr []int, i int) int {
    length := len(arr)
    minKey := i
    minValue := arr[minKey]
    //从下标为i及之后的元素中找出值最小的元素
    for k := minKey + 1; k < length; k++ {
        if minValue > arr[k] {
            //修改下标
            minKey = k
            minValue = arr[k]

        }
    }
    return minKey
}

1、冒泡排序

冒泡排序算法运行方式如下：
假设待排序序列有n个元素
第一次循环
1.从首元素开始比较相邻的元素，如果顺序不对，就把它们两个调换位置，直至最后一个，此时可以保证最后一个元素是最大的（或最小的）
2.重复以上操作，每次循环都可以将无序序列（序列无序元素数量每次循环后都在减少）最大（最小）的一个元素移至最右边，所以第k次循环后前n-k个元素是无序的，后k个元素是有序且依次递增（递减）的

示意图

package main

import (
    "fmt"
    "myAlgo"
)

func main() {
    arr := []int{15, 45, 42, 25, 20, 63, 23, 20, 29, 100, 9}
    myALgo.BubbleSort(arr);
}

package myAlgo
import "fmt"
func bubbleSort(arr []int) {
    length := len(arr)
    for j := length - 1; j > 0; j-- {
        //外层循环控制循环次数
        for i := 0; i < j; i++ {
            //内层循环控制交换
            if arr[i] > arr[i+1] {
                //交换顺序
                exchange(arr, i, i+1)
            }
        }
        fmt.Println(arr)
    }
}

结果如下

2、简单选择排序

思路如下：
1.首先，找到序列中最小的那个元素，将它和第一个元素交换位置。
2.在剩下的元素中找到最小元素，将它与序列的第二个元素交换位置
3.按照以上方式如此往复，直至将整个序列排序。
因为它在不断的选择剩余元素之中的最小者，所以叫选择排序。

示意图

go实现

package main
import "fmt"
func main() {
    arr := []int{15, 45, 42, 25, 20, 63, 23, 20, 29, 100, 9}
    fmt.Println(arr)    
    myAlgo.SelectSort(arr)
}

package myAlgo
import "fmt"
func SelectSort(arr []int) {
    fmt.Println("开始排序")
    length := len(arr)
    for i := 0; i < length; i++ {
        //每循环一次都找出当前未排序元素中的最小值，和当前元素进行交换
        minKey := selectMin(arr, i)
        exchange(arr, i, minKey)
    }
    fmt.Println(arr)
}

执行结果

3、直接插入排序

这个类似于玩扑克牌，一张一张的将牌拿出来插到部分已经有序序列中的合适位置，具体如下：
1.第一个元素可以看成是有序的
2.从有序序列下一个元素开始，用这个元素a从后向前，依次和有序序列元素b进行比较，如果元素a小于元素b,则将元素a插入到元素b之前，原有序序列b之后的元素均向后移动一个位置，此时生成一个新的有序序列。
3.重复操作2

示意图

go实现

package main

import (
    "fmt"
    "myAlgo"
)
func main() {
    arr := []int{15, 45, 42, 25, 20, 63, 23, 20, 29, 100, 9}
    fmt.Println(arr)
    myAlgo.InsertSort(arr)
}

package myAlgo
import "fmt"
func InsertSort(arr []int) {
    fmt.Println("开始排序")
    //获取当前数组长度
    length := len(arr)
    for i := 1; i < length; i++ {
        //当前值
        now := arr[i]
        //如果当前元素小于之前序列中的某一个元素的值，则序列从此元素向后整体移动一位
        for j := i - 1; j >= 0; j-- {
            if now < arr[j] {
                arr[j+1] = arr[j]
                arr[j] = now
            } else {
                arr[j+1] = now
                break
            }
        }
        fmt.Println(arr)
    }
}

运行结果

快速排序

算法原理：
将未排序元素根据一个作为基准的“主元”（Pivot）分为两个子序列，其中一个子序列的记录均大于主元，而另一个子序列均小于主元，然后递归地对这两个 子序列用类似的方法进行排序。本质上，快速排序使用分治法，将问题的规模减小，然后再分别进行处理。

示意图

go实现

package main

import (
    "fmt"
    "myAlgo"
)
func main() {    
    arr := []int{40, 45, 42, 25, 20, 63, 23, 20, 50, 29, 100, 9}
    fmt.Println(arr)    
    myAlgo.QuickSort(arr, 0, len(arr) - 1)
}

package myAlgo
import "fmt"
func QuickSort(arr []int, left int, right int) {

    //设置基准数，选择第一个作为基准数
    baseKey := left
    baseValue := arr[baseKey]
    fmt.Println("当前序列", arr[left:right+1],"基准值为",baseValue)
    fmt.Println("开始排序")
    i := left
    j := right
    for i < j {
        //先从右向左找,直到找到一个小于基准数的值
        for (arr[j] >= baseValue) && (i < j) {
            j--
        }
        if i < j {
            //将j的值放到i的空位上
            arr[i] = arr[j]

        }
        //从左向右找，直到找到一个大于基准数的值
        for (i < j) && (arr[i] < baseValue) {
            i++
        }
        if i < j {
            //将此时的i放到之前j产生的空位上
            arr[j] = arr[i]
        }
        fmt.Println(arr[left:right+1])

    }
    arr[i] = baseValue
    fmt.Println("子序列结果", arr[left:right+1])
    fmt.Println("总序列", arr)
    fmt.Println("--------------------")
    if left < i-1 {
        QuickSort(arr, left, i-1)
    }
    if i+1 < right {
        QuickSort(arr, i+1, right)
    }

}

运行结果