快速排序的算法优化
代码如下:
正常的写法:
#include <iostream>
#include <algorithm>
int partition(int arr[], int left, int right) {int pivot = arr[left]; int i = left + 1; int j = right; while (true) {while (i <= right && arr[i] <= pivot) {i++;}while (j >= left && arr[j] > pivot) {j--;}if (i >= j) break; std::swap(arr[i], arr[j]); }std::swap(arr[left], arr[j]);return j;
}
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 main() {int arr[] = {10, 7, 8, 9, 1, 5, 12, 11, 6, 4, 3, 2};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);std::cout << "排序后的数组: ";for (int i = 0; i < n; ++i) {std::cout << arr[i] << " ";}std::cout << std::endl;return 0;
}
优化算法
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
void insertionSort(int arr[], int left, int right) {for (int i = left + 1; i <= right; ++i) {int key = arr[i];int j = i - 1;while (j >= left && arr[j] > key) {arr[j + 1] = arr[j];--j;}arr[j + 1] = key;}
}
int medianOfThree(int arr[], int left, int right) {int mid = left + (right - left) / 2;if (arr[left] > arr[mid]) std::swap(arr[left], arr[mid]);if (arr[left] > arr[right]) std::swap(arr[left], arr[right]);if (arr[mid] > arr[right]) std::swap(arr[mid], arr[right]);return arr[mid];
}
int hoarePartition(int arr[], int left, int right) {int pivot = medianOfThree(arr, left, right); int i = left - 1;int j = right + 1;while (true) {do {i++;} while (arr[i] < pivot);do {j--;} while (arr[j] > pivot);if (i >= j) return j;std::swap(arr[i], arr[j]);}
}
int randomPartition(int arr[], int left, int right) {int randomIndex = left + rand() % (right - left + 1);std::swap(arr[randomIndex], arr[right]); return hoarePartition(arr, left, right);
}
void quickSort(int arr[], int left, int right) {const int threshold = 10; while (left < right) {if (right - left <= threshold) {insertionSort(arr, left, right);break;}int pivotIndex = hoarePartition(arr, left, right);if (pivotIndex - left < right - pivotIndex) {quickSort(arr, left, pivotIndex); left = pivotIndex + 1; } else {quickSort(arr, pivotIndex + 1, right); right = pivotIndex; }}
}
int main() {int arr[] = {10, 7, 8, 9, 1, 5, 12, 11, 6, 4, 3, 2};int n = sizeof(arr) / sizeof(arr[0]);srand(time(0));quickSort(arr, 0, n - 1);std::cout << "排序后的数组: ";for (int i = 0; i < n; ++i) {std::cout << arr[i] << " ";}std::cout << std::endl;return 0;
}