题目描述

输入一组数组，使用快速排序算法对其进行排序

  • 示例1

输入

1
{5，7，2，9，10，4}

输出

1
{2，4，5，7，9，10}

快速排序

  1. 取第一个作为基准数

  2. 将小于pri的数放在基准数的左边，将大于基准数的放在其右边

  3. 以基准数为界限，将之前的川切割成两个字串

  4. 分别对两个字串递归执行步骤1，2，3

解题思维

对于

  1. pri为第一个元素值, left为第一个元素下标， right为最后一个元素下标

1
2
3
4

left = 0
pri = arr[left]
right = len(arr) - 1
  1. 从最右边开始，如果right指向的值大于则right减1，否则就将当前right所指向的值放在left位置，然后执行3。如此循环一直到left=right.

  1. 从最左边开始,如果right指向的值大于则right加1，否则就将当前left所指向的值放在right位置，然后执行2。如此循环一直到left=right.

  1. 上面循环执行的展示过程

  1. 当left=right, 那么就把基准值赋给left位置,至此就完成了把小于基准值放在左侧，大于基准值放在右侧的任务。

  1. 然后以上面left将原数组切割成两个字串，分别递归执行上面的步骤

源码理解更深刻

强烈建议自己看懂之后手动实现一篇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func partion(arr []int, left, right int) int {
	pri := arr[left]
	fmt.Printf("left: %d, right: %d", left, right)

	for left < right {
		for left < right && arr[right] >= pri {
			right--
		}
		arr[left] = arr[right]

		for left < right && arr[left] <= pri {
			left++
		}
		arr[right] = arr[left]

	}
	arr[left] = pri

	return left
}

func QuickSort(arr []int, left, right int) {
	if left < right {
		par := partion(arr, left, right)
		fmt.Println(par)

		QuickSort(arr, left, par-1)
		QuickSort(arr, par+1, right)
	}
}