疾速排序

在解释之前，先上一张快排的图，我发现间接看图了解算法更简略

首先须要理解的是，疾速排序的过程是递归调用的。

步骤：

  • 先选出一个参考值，用来进行比拟。这个参考值能够从待排序的数组里任选一个，个别抉择第一个或者最初一个。
  • 在选出一个参考值之后，开始遍历数组，把比参考值小的放到它的右边，大于等于它的放到左边；在实现的时候就是替换地位。在实现的时候，须要保护两个指针，头指针和尾指针，如果遍历的数比参考值小，就让这个数和头指针指向的数替换地位，并且头指针向右挪动一步，相似的，尾指针则是向左挪动一步。

代码实现

package main

func quickSort(nums []int) {
    if len(nums) < 2 {
        return
    }
    head, tail := 0, len(nums)-1
    Reference := nums[0]
    i := 1
    for head < tail {
        if nums[i] < Reference {
            nums[i], nums[head] = nums[head], nums[i]
            head++
            i++
        } else {
            nums[i], nums[tail] = nums[tail], nums[i]
            tail--
        }
    }
    quickSort(nums[:head])
    quickSort(nums[head+1:])
}

能够看到，最初对参考值右边和左边的数进行递归排序，始终到只剩下两个数的时候，失去了正确的程序之后返回之前的调用，最终就失去了排序后的后果。

空间复杂度： O(1), 在执行过程中只申请了一个 reference，因而空间复杂度是 O(1)

工夫复杂度： O(nlogn), 这里贴个计算公式，

T(1) = C；   n=1时，只须要常量级的执行工夫，所以示意为C。
T(n) = 2*T(n/2) + n； n>1

解释一下：数组的工夫复杂度为 T(n)，那么当分为两局部之后，每一个局部的工夫复杂度应为 T(n/2)，而合并两个数组的工夫复杂度是 n，因而总的工夫复杂度是 2*T(n/2) + n。这个公式是计算递归算法工夫复杂度的一个公式，快排能够用，归并排序也能够同样的计算。

求解 T(n) 的过程:


T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

下面的求解过程其实并不是很合乎疾速排序，因为把数组一分为二的前提是选取的参考值正好是整个能让整个数组一分为二。瞎蒙一个都有这种成果，显然概率是比拟小的，然而在估算的时候就先这么算吧。。。非要去推导公式我也不会。。。

T(n)=Cn+nlog2n

然而疾速排序的性能与它的分区点选取是有关系的，如果一个有序的数组，咱们每次都选取了最初一个来作为参考，这样就须要进行 n-1 次分区，使得快排的工夫复杂度进化到 O(n^2)

归并排序

还是先上一张归并排序的动图

与疾速排序不同的是，归并排序不须要选参考值，间接从两头离开，始终分到最初一个一组，再合并起来，最重要的也是这个 merge 操作，创立一个长期数组，因为待合并的两个数组都是有序的，因而能够把两个待合并的数组按从小到大的程序插入长期数组中。最终合并到只剩下一个数组的时候就是后果了。

代码实现

package main

func mergeSort(nums []int, left int, right int) {
    if left >= right { 
        return 0
    }
    tmp := []int{}
    mid := left + (right-left)/2
    mergeSort(nums, left, mid) 
    mergeSort(nums, mid+1, right)
    i, j := left, mid+1

    for i <= mid && j <= right { // merge 操作
        if nums[i] <= nums[j] {
            tmp = append(tmp, nums[i])
            count += j - (mid + 1)
            i++
        } else {
            tmp = append(tmp, nums[j])
            j++
        }
    }

    for ; i <= mid; i++ { //左边没有数据了，右边还有
        tmp = append(tmp, nums[i])
    }
    for ; j <= right; j++ {
        tmp = append(tmp, nums[j]) //左边都是有序的了
    }
    for i := left; i <= right; i++ {
        nums[i] = tmp[i-left] //拷贝回原数组
    }
}

工夫复杂度: O(nlogn)，能够看下面的递推公式，原理都是一样的

空间复杂度：O(n)，如果依照下面的公式递推，其实空间复杂度应该是 O(nlogn) 才对，然而每次合并实现后，占用的内存空间都被零碎开释了，因而同一时刻只有一个长期数组占用了空间，因而工夫复杂度是 O(n)。

公众号：没有幻想的阿巧 后盾回复 “群聊”，一起学习，一起提高