快速排序
在解释之前，先上一张快排的图，我发现直接看图理解算法更简单
首先需要了解的是，快速排序的过程是递归调用的。
步骤：
- 先选出一个参考值，用来进行比较。这个参考值可以从待排序的数组里任选一个，一般选择第一个或者最后一个。
- 在选出一个参考值之后，开始遍历数组，把比参考值小的放到它的左边，大于等于它的放到右边；在实现的时候就是交换位置。在实现的时候，需要维护两个指针，头指针和尾指针，如果遍历的数比参考值小，就让这个数和头指针指向的数交换位置，并且头指针向右移动一步，类似的，尾指针则是向左移动一步。
代码实现
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/2^k) = T(1) 时，即 n/2^k = 1，所以 k = logn,代入上面的公式得 T(n)=Cn+nlog2n，即 O(nlogn)。
但是快速排序的性能与它的分区点选取是有关系的，如果一个有序的数组，我们每次都选取了最后一个来作为参考，这样就需要进行 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)。
公众号：没有梦想的阿巧 后台回复 "群聊"，一起学习，一起进步
网友评论