归并排序与快速排序

归并排序

归并排序的核心实现就是分治，主要利用一个递归无限的把一个数组分为左右2部分，然后利用一个合并函数把排好序的数组退回去。理解起来比较容易

思路

1. 分解2个函数 meage_sort 负责递归分解出数组，meage负责合并排序数组
2. 找到数组的中间数，即长度/2，递归的中断条件为传递进去的长度为0
3. 通过中间数把meage_sort拆分迭下去，它的参数就是 中间数的左边元素和右边元素
4. meage函数中需要有2个指针，分别指向 left和right数组的第一个元素
5. 以 left和right 长度为结构体条件，循环比较他们的大小，同时移动指针指向下一位直到一边全部放入临时数组
6. 把剩下的另一边数据塞回meage的返回值

func meage_sort(nums []int) []int{
	length := len(nums)
	if length <= 1  {
		return nums
	}
	p := length/2

	left := meage_sort(nums[:p])
	right := meage_sort(nums[p:])
	return meage(left, right)
}

func meage (left []int, right []int) (m []int){
	l,r := 0,0
	
	for l < len(left) && r < len(right){
		if left[l] > right[r] {
			m = append(m, right[r])
			r++
		} else {
			m = append(m, left[l])
			l++
		}
	}
	//剩下的放入末尾
	m = append(m,right[r:]...)
	m = append(m,left[l:]...)
	return
}

时间和空间复杂度都为 o(n log n) 属于稳定排序，非原地排序

快排

快排是能用到实战中的基础算法知识，掌握细节还是很值得的。

思路

• 找一个基准值这用数组第一个（如果追求极致可以单独把取基准值拎出来做成函数，取3-5个值取中间值）

• 从数组最左边和最右边取值和基准值做对比，左边小右边大。如果条件不符合，位置做交换

• 左边第一个值（基准值会被覆盖，所以代码顺序必须是先从右边开始），左边第一个值放入临时对比基准变量 p

• 值交换完成后执行移位操作，因为这个值是目标位置，避免下面循环再次比对

• 临时值复位，递归左右两边

func quick_sort(nums []int ,left int ,rigth int){

	if (left>=rigth){
		return
	}
	l,r,p := left,rigth,nums[left]

	for r>l{
		for r>l && nums[r] > p{
			r--
		}
		if r>l {
			nums[l] =  nums[r]
			l++
		}
		for r>l && nums[l] < p{
			l++
		}

		if r>l {
			nums[r] =  nums[l]
			r--
		}

	}
	nums[l] = p
	quick_sort(nums,left, l-1)
	quick_sort(nums,l+1, rigth)

}