经过改进的快速排序的算法
时间: 2023-06-23 07:50:12 浏览: 89
快速排序是一种常用的排序算法,它的基本思想是通过选取一个基准元素,将数组中小于基准元素的元素放置在它的左边,大于基准元素的元素放置在它的右边,然后对左右两个子数组分别递归地进行快速排序。
快速排序的时间复杂度为 O(nlogn),但在最坏情况下会退化为 O(n^2)。为了避免这种情况,可以对快速排序进行改进,以保证其性能更稳定。
经过改进的快速排序算法中,选取基准元素的方式有所改变。具体来说,选取基准元素时,不再选择第一个元素,而是从数组中随机选取一个元素作为基准元素。这样可以避免在某些特定情况下,如数组已经有序时,快速排序算法的性能降低。
另外,在进行划分子数组时,可以采用三分法,即将数组分成三部分:小于基准元素、等于基准元素和大于基准元素。这样可以避免数组中有大量重复元素时,快排算法的性能降低。
下面是经过改进的快速排序的 C++ 实现代码:
```c++
#include <iostream>
#include <cstdlib>
#include <ctime>
void quickSort(int arr[], int left, int right);
int partition(int arr[], int left, int right);
int main() {
int arr[] = {5, 2, 4, 6, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
void quickSort(int arr[], int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
int partition(int arr[], int left, int right) {
// 从数组中随机选取一个元素作为基准元素
srand(time(NULL));
int pivotIndex = left + rand() % (right - left + 1);
int pivotValue = arr[pivotIndex];
// 交换基准元素和最后一个元素
std::swap(arr[pivotIndex], arr[right]);
// 三分法划分子数组
int i = left - 1, j = right;
while (true) {
while (arr[++i] < pivotValue);
while (j > left && arr[--j] > pivotValue);
if (i >= j) {
break;
}
std::swap(arr[i], arr[j]);
}
std::swap(arr[i], arr[right]);
return i;
}
```
在这个实现中,quickSort 函数是快速排序的主函数,它递归地对子数组进行排序。partition 函数是划分子数组的函数,它使用三分法将子数组分成三部分。在 partition 函数中,首先从数组中随机选取一个元素作为基准元素,并将其与最后一个元素交换。然后,使用三分法将子数组划分成三部分,并返回基准元素的最终位置。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)