算法-快速排序

go快速排序

时间复杂度:O(n²)

空间复杂度:O(Nlog2n)

不稳定,较复杂

过程:

1、设置一个基点,通常为最左边或最右边,下面设置为最左边,设置设置两个指针分别指向数组两端

2、先移动右边指针,如果小于基点的值,则停止移动,并且把值覆盖到最左边的指针的值

3、覆盖之后,把最左边的指针向右移动,如大于几点,则覆盖右边指针的值,直到 左右指针指向相同位置,则把几点赋值到指针所在位置

4、把当前指针所在位置当作中间点,然后拆分左右两段,分别重复(2\3)步骤即可(下面使用递归的方式进行重复处理)

/**
 * @author Yel
 * 快速排序
 * 时间复杂度:O(n²)
 * 空间复杂度:O(Nlog2n)
 * 不稳定,较复杂
 * 过程:
 * 1\设置一个基点,通常为最左边或最右边,下面设置为最左边,设置设置两个指针分别指向数组两端
 * 2\先移动右边指针,如果小于基点的值,则停止移动,并且把值覆盖到最左边的指针的值
 * 3\覆盖之后,把最左边的指针向右移动,如大于几点,则覆盖右边指针的值,直到 左右指针指向相同位置,则把几点赋值到指针所在位置
 * 4\把当前指针所在位置当作中间点,然后拆分左右两段,分别重复(2\3)步骤即可(下面使用递归的方式进行重复处理)
 */
func Quicksort(arr []int, order string) {
	var length = len(arr)
	if length < 2 {
		return
	}
	var base = arr[0]                   // 使用左边第一个为基准
	var left, right int = 0, length - 1 // 设置左右指针

	for left != right {
		// 先把右指针向左移动,如果遇到小于基准的值,则覆盖左边位置
		for left < right {
			// 升序
			if order == "asc" {
				// 右边向左移动,遇到比基准小的,则覆盖左边位置
				if base > arr[right] {
					arr[left] = arr[right]
					break
				}
			} else {
				// 降序
				if base < arr[right] {
					arr[left] = arr[right]
					break
				}
			}
			right--
		}
		// fmt.Println(left, right)

		// 从左向右移动,找到比基准大的,覆盖右边位置
		for left < right {
			// 从左向右移动,找到比基准大的,覆盖右边位置
			// 升序
			if order == "asc" {
				if base < arr[left] {
					arr[right] = arr[left]
					break
				}
			} else {
				if base > arr[left] {
					arr[right] = arr[left]
					break
				}
			}
			left++
		}
		// fmt.Println(left, right)
	}
	// 指针左右相等,则把基准值放到指针位置
	arr[left] = base

	// 对数组左边进行快速排序
	Quicksort(arr[:left], order)
	// 对数组右边进行快速排序
	Quicksort(arr[left+1:], order)
}