一、原理
选择排序的原理是分治,把排序序列切分成若干个小组后分别排序。每次排序都以随机的一个元素作为哨兵 (一般都以排序区间的中间元素或者首元素作为哨兵),比他大的元素都放到右边,比它小的都放到左边。然后分别对该元素左边和右边的元素再法排序,直到所有的元素都是有序状态。
具体的排序过程描述为:
- 选取一个哨兵元素 temp,设置两个指针 low 和 high 分别从数组的两端开始遍历。
- high 指针从右到左遍历,当遇到 A[high] < temp 的时候,设置 A[left] 的值为 A[high] 。
- low 指针从左到右遍历,当遇到 A[high] > temp 的时候,设置 A[high] 的值为 A[left] 。
- 重复执行 2 、 3 步,直到 low 和 high 相遇,设置 low 元素的值为 temp 。此时 low 左边的元素都小于 temp,low 右边的元素都大于 temp 。再分别对左右子区间的元素分别排序。
图例:
以数组 [54, 15, 34, 82, 15, 46, 85, 43] 为例,初始状态时设置 low 指针指向第一个元素,high 指针指向最后一个元素,temp 为第一个元素的值 54:
遍历 high 指针,从右到左找到第一个小于 54 的元素 43,赋值给 low:
遍历 low 指针,从左到右找到第一个大于 54 的元素 82,赋值给 high:
遍历 high 指针,从右到左找到一个小于 54 的元素 46,赋值给 low:
遍历 low 指针,继续寻找第一个大于 54 的元素。但是直到遇见 high 指针,都没有找到再比 54 大的元素,把 temp 值赋值给 low:
此时第一轮排序完成,54 左边的元素都比它小,右边的元素都比它大。因此按照这个操作,继续对左边和右边的区间再执行相同的操作,多次排序即可完成整个数组的排序。
复杂度分析:
最坏的情况下,数组无序,快速排序和冒泡排序差不多。
- 时间复杂度:最坏情况下,时间复杂度为 O(n2);最好的情况和平均情况下算法复杂度为 O(nlog(n))。
- 空间复杂度:最坏情况下,空间复杂度为 O(n);平均情况下空间复杂度为 O(log(n)) 。
二、代码实现
快排的写法多样,以下实现了 C++和 Python 两种语言的快速排序算法实现。
其中 C++选取的哨兵是数组第一个元素,python 选取的哨兵是数组中间元素。
2.1 C++实现
以区间中点作为排序标杆:
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 |
/* * 快速排序算法实现,对 [left, right) 部分的数组排序。 * @data 待排序数组 * @left 左区间,包含该下标元素 * @right 右区间,不包含该下标元素 */ template<typename T> void quick_sort(vector<T> &data, int left, int right) { int i = left, j = right - 1; T temp; if (right <= left) { return; } temp = data[i]; while (i < j) { // 从右到左遍历找到一个比 temp 小的 while (i < j && data[j] >= temp) { j--; } if (i < j && data[j] < temp) { data[i] = data[j]; } // 从左到右遍历找到一个比 temp 大的 while (i < j && data[i] <= temp) { i++; } if (i < j && data[i] > temp) { data[j] = data[i]; } } data[i] = temp; // 排序的区间是左闭右开 quick_sort(data, left, i); quick_sort(data, i + 1, right); } |
2.2 python
以区间中点元素作为标杆:
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 |
import math def quick_sort(data, left, right): """ 快速排序算法,对 [left, right) 区间的元素排序 :param data: 待排序数组 :param left: 待排序数组的左区间,包含对对该下标元素排序 :param right: 待排序数组的右区间,不包含对该下标元素排序 :return: """ i, j = left, right - 1 if i >= j: return # 选择区间中点元素作为哨兵 mid = math.floor((i + j) / 2) temp = data[mid] data[i], data[mid] = data[mid], data[i] while i < j: while i < j and data[j] >= temp: j -= 1 if i < j and data[j] < temp: data[i] = data[j] while i < j and data[i] <= temp: i += 1 if i < j and data[i] > temp: data[j] = data[i] data[i] = temp quick_sort(data, left, i) quick_sort(data, i + 1, right) |
2020-02-29 刷 leetcode 添加,使用数组中间元素作为哨兵:
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 |
/* * 快速排序,对 [left, right] 区间内的元素排序 * @nums 排序数组 * @left 左边界 * @right 右边界,包含该下标元素 */ func doQuickSort(nums []int, left, right int) { i, j := left, right if left >= right { return } // 取中间元素作为哨兵 mid := (i + j) / 2 x := nums[mid] nums[mid], nums[i] = nums[i], nums[mid] for i < j { for nums[j] >= x && i < j { j -= 1 } if i < j && nums[j] < x { nums[i] = nums[j] } for nums[i] <= x && i < j { i += 1 } if i < j && nums[i] > x { nums[j] = nums[i] } } nums[i] = x doQuickSort(nums, left, i-1) doQuickSort(nums, i+1, right) } func quickSort(nums []int) []int { doQuickSort(nums, 0, len(nums)-1) return nums } |
评论