排序算法 #
快速排序 #
1、快速排序的基本过程? #
- 用分治的思想。
- 选一个基准元素。把比这个元素小的放左边,大的放右边。这时候基准元素所处的即为最终的位置。
- 递归对左右两边都采取一样的方法,直到没有元素或只有一个元素。
void quickSort(vector<int>& nums, intleft, intright) {
if (left >= right) {
return;
}
int index = partition(nums, left, right);
quickSort(nums, left, index - 1);
quickSort(nums, index + 1, right);
}
void quickSort(vector<int>& nums) {
quickSort(nums, 0, nums.size() - 1);
}
2、分割的过程是什么样的? #
- 假设 pivot 作为基准元素。
- 从数组的右端向左扫描找到第一个小于它的元素。
- 再从数组的左端向右扫描直到找到第一个大于它的元素。
- 交换这两个元素。
不断进行这个过程,就可以保证左指针 i 的左侧元素都不大于切分元素,右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时,把基准元素和相遇的这个位置交换。
int partition(vector<int>& nums, intleft, intright) {
int pivotIndex = left;
int pivot = nums[left];
while (left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
while (left < right && nums[left] <= pivot) {
left++;
}
if (left >= right) {
break;
}
swap(nums, left, right);
}
swap(nums, pivotIndex, left);
return left;
}
3、快排的复杂度是多少? #
- 平均复杂度:O(NlgN)
- 最坏复杂度:O(N方)
- 即每次分割时,O(N),要分割N次
- 好处:不需要辅助空间,原地排序。
4、有改进的方法吗? #
- 切换到插入排序
- 三数取中
- 三向切分
5、怎么找出数组第 K 个元素 #
partition() 方法,会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j],且 a[j+1..h] 大于等于 a[j],此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 k 个元素。
int selectK(vector<int>& nums, int k) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int index = partition(nums, left, right);
if (k == index) {
return nums[k];
} elseif (k < index) {
right = index - 1;
}
elseif (k > index) {
left = index + 1;
}
}
return nums[k];
}
冒泡排序 #
1. 基本算法 #
从左到右不断交换相邻逆序的元素,在一轮的循环之后,可以让未排序的最大元素上浮到右侧。
void bubbleSort(vector<int>& nums) {
int n = nums.size();
bool isSorted = false;
for (int i = 0; i < n && !isSorted; i++) {
isSorted = true;
for (int j = 0; j < n - i -1; j++) {
if (nums[j] > nums[j + 1]) {
isSorted = false;
swap(nums, j, j + 1);
}
}
}
}
2. 算法改进 #
在一轮循环中,如果没有发生交换,那么说明数组已经是有序的,此时可以直接退出。
3. 性能分析 #
平均和最坏都是 O(n^2)
稳定排序。
O(n2) #
冒泡排序
选择排序 - 不稳!
- 两层for循环每次选最小
插入排序
O(n*log2n) #
快排
堆排 - 不稳!
归并排序
- 第一步:创建一个额外大集合用于存储归并结果,长度则为那两个小集合的和,
- 第二步:我们从左自右比较两个指针指向的值,将较小的那个存入大集合中,存入之后指针移动,并继续比较,直到某一小集合的元素全部都存到大集合中
- 第三步:当某一小集合元素全部放入大集合中,则需将另一小集合中剩余的所有元素存到大集合中。
希尔排序 - 不稳!
- 希尔增量分组,组内排序
计数排序:O(n+m) - O(n+m)
桶排序:O(n) - O(m)
基数排序:O(k*n)