算法篇03：排序算法

排序算法是接触最多也是考察最多的一个知识点，最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。其中可以按照时间复杂度把冒泡和插入归并为O(n^2)一类，归并和快排归并为O(n*log(n))一类，后三者归为O(n)一类。

分析排序算法主要从执行效率、内存消耗和稳定性三个角度去衡量，执行效率就是常说的时间复杂度，内存消耗主要说的是空间复杂度，这里还引入了一个原地排序概念（就是特指空间复杂度是 O(1) 的排序算法，可以理解为就在原内存空间上做数值交换），稳定性则是考虑待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

一、冒泡or插入

1.冒泡排序
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。冒泡排序是只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。最好情况时间复杂度是 O(n)，最坏情况时间复杂度为 O(n^2)。下面给出go实现demo：

import "fmt"

func main() {
    values := []int{4, 93, 84, 85, 80, 37, 81, 93, 27,12}
    fmt.Println(values)
    bubbleSort(values)
}

//冒泡排序（排序10000个随机整数，用时约145ms）  
func bubbleSort(nums []int) {  
    for i := 0; i < len(nums); i++ {  
        for j := 1; j < len(nums)-i; j++ {  
            if nums[j] < nums[j-1] {  
                //交换  
                nums[j], nums[j-1] = nums[j-1], nums[j]  
            }  
        }  
    }  
}

【golang实现冒泡排序】

2.插入排序
插入排序的原理是，从第二个数开始向右侧遍历，每次均把该位置的元素移动至左侧，放在放在一个正确的位置（比左侧大，比右侧小）。同样的，插入排序是一个稳定的原地排序算法，时间复杂度上和冒泡排序一致。

//插入排序（排序10000个整数，用时约30ms）  
func insertSort(nums []int) {  
    for i := 1; i < len(nums); i++ {  
        if nums[i] < nums[i-1] {  
            j := i - 1  
            temp := nums[i]  
            for j >= 0 && nums[j] > temp {  
                nums[j+1] = nums[j]  
                j--  
            }  
            nums[j+1] = temp  
        }  
    }  
}

3.为什么更推荐插入排序方法？
同等情况下，插入排序比冒泡排序效果更好，冒泡交换要比插入交换的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要 1 个。这种情况在数据量较大的情况下对比会比较明显，同等大数据量的排序算法下插入会比冒泡省1/3的时间。

//冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

//插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

二、归并or快排

归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分而治之的思想，代码通过递归来实现，过程非常相似。归并排序的重点是递推和 merge() 合并函数，而快排的重点递推公式和partition() 分区函数。归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，但也使之存在致命的缺点，归并排序不是原地排序算法，空间复杂度比较高，是 O(n)，数据量大的情况下就很容易消耗内存空间，因此通常情况下这二者之间快速排序的应用更加广泛，这里也主要学习快速排序算法。

const MAX = 10
 
var sortArray = []int{41, 24, 76, 11, 45, 64, 21, 69, 19, 36}
 
func main() {
    fmt.Println("before sort：")
    show()
    quickSort(sortArray, 0, MAX-1)
    fmt.Println("after sort:")
    show() 
}
 
func quickSort(sortArray []int, left, right int) {
    if left < right {
        pos := partition(sortArray, left, right)
        partition(sortArray, left, pos-1)
        partition(sortArray, pos+1, right)
    }
}

func partition(sortArray []int, left, right int) int {
    key := sortArray[right]
    i := left - 1
    for j := left; j < right; j++ {
        if sortArray[j] <= key {
            i++
            swap(i, j)
        }
    }
    swap(i+1, right) 
    return i + 1
}
 
// Swap the position of a and b
func swap(a, b int) {
    sortArray[a], sortArray[b] = sortArray[b], sortArray[a]
}
 
// foreach
func show() {
    for _, value := range sortArray {
        fmt.Printf("%d\t", value)
    }
}

快排是一种原地、不稳定的排序算法。快速排序算法虽然最坏情况下的时间复杂度是O(n )，但是平均情况下时间复杂度都是O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 O(n ) 的概率非常小。

【图解数据结构——排序】包含各种排序算法的对比
【go语言实现快速排序】