1.排序算法

经典的排序算法

insertion sort 插入排序

排序实现原理

将元素不断地插入已经排序好的 array 中

• 起始只有一个元素5，其本身是一个有序序列
• 后续元素插入序列中，不断交换，直到找到第一个比其小的元素

代码实现

// 插入排序
func InsertionSort(arr []int) []int {
    for i := 1; i < len(arr); i++ {
        k := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > k {
            arr[j+1] = arr[j]
            j = j - 1
        }
        arr[j+1] = k
    }
    return arr
}

//i = 1 k = 5 j = 0 arr[j] = 6 arr = 6 6 2 1 3 4 j = -1 arr = 5 6 2 1 3 4
//i = 2 k = 2 j = 1 arr[j] = 6 arr = 5 6 6 1 3 4 j = 0 arr = 5 5 6 1 3 4 j = -1 arr = 2 5 6 1 3 4
......

func TestInsertionSort(t *testing.T) {
    a := []int{6, 5, 2, 1, 3, 4}
    fmt.Println(InsertionSort(a))
}

时间复杂度

• 最好情况时间复杂度O(n)
• 平均最坏情况时间复杂度O(n^2)

quick sort 快速排序

排序实现原理

分治思想，不断分割序列直到序列整体有序

• 选定一个pivot(轴点)
• 使用pivot分割序列，分成元素比pivot大和元素比pivot小两个序列

代码实现

func QuickSort(arr []int, left, right int) []int {
    if left >= right {
        return arr
    } // 左指针大于右指针递归结束

    l, r, cur := left, right, arr[left]
    for l < r { // l == r 所有值被变量
        for l < r && arr[r] >= cur { //轴点取最左边值 需要先移动右指针
            r--
        }
        for l < r && arr[l] <= cur {
            l++
        }
        arr[l], arr[r] = arr[r], arr[l]
    }
    arr[left], arr[r] = arr[r], arr[left]
    QuickSort(arr, left, l-1)
    QuickSort(arr, l+1, right)
    return arr
}

// cur = 6 l = 0 l = 1 l = 2 l = 3 l = 4 l = 5  r = 5  arr[r] = 4 arr[l] = 6->5->2->1->3->4  a[5],a[5] = a[5],a[5] [6,5,2,1,3,4] [4,5,2,1,3,6]
// cur = 4 l = 0 l = 1 r = 4 arr[r] = 3 arr[l] = 4->5 a[1],a[4] = a[4],a[1] [4,3,2,1,5,6] l < r  l = 1 r = 3 a[1] = 3 l = 2 a[2] = 2 l = 3 a[3] = 1 [4,3,2,1,5,6] [1,3,2,4,5,6]
......

时间复杂度

• 最好平均情况时间复杂度O(n&logn)
• 最坏情况时间复杂度O(n^2)

heap sort 堆排序

排序实现原理

利用堆的性质形成的排序算法

• 构造一个大顶堆
• 将根节点（最大元素）交换到最后一个位置，调整整个堆，如此反复