- 最近刷leet-code的一到题目时, 找到第
k大的数字, 需要对一个数组进行排序. - 发现自己只会最基础的冒泡排序, 插入排序.
- 然后就去补习了一下插入排序, 对着网上给的动态图, 写了一份自己的快速排序, 代码都差不多.
|
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
// 1. 选择一个基准数量(可选第一个, 也可随机选数组的一个) // 2. 双指针遍历, 右指针先动 // 3. 右指针找到比基准小的数, 停下 // 4. 左指针开始动, 当找到比基准打的数,停下 // 5. (3,4)步骤找到的数交换 // 6. 重复(3,4,5), 直到满足条件 7 // 7. 左右指针碰撞, 再交换一次值(防止之前是一个倒序数组) func quickSort(data []int, left, right int) { if left >= right { return } pivotIndex := partition(data, left, right) quickSort(data, left, pivotIndex - 1) quickSort(data, pivotIndex + 1, right) } func partition(data []int, left, right int) int { pivotIndex := left pivot := data[pivotIndex] for left != right { if data[right] > pivot { right -- continue } // 增加等于符号, 防止基准位置右边有和基准数一样的数字 // 导致进入死循环不停的交换两个值 if data[left] <= pivot { left ++ continue } data[left], data[right] = data[right], data[left] } data[left], data[pivotIndex] = data[pivotIndex], data[left] return left } |
