公共函数,用以测试数组相等
namespace SortCommon {
bool ArrEqual(int arr1[], int arr2[], int n) {
for (int i = 0; i < n; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
}
快速排序第一版,如果遇到重复元素较多的时候,复杂度会逼近O(N*N)
// partition
int Partition(int arr[], int l, int r) {
// 优化,随机化选择标头v,即随机置换一个数据到头部,用作标头
std::swap(arr[l], arr[rand() % (r - l + 1) + l]);
int v = arr[l];
int j = l;
// arr[l...j] 存储小于v的元素
// arr[j+1....i) 存储大于等于v的元素
for (int i = l + 1; i <= r; ++i) {
if (arr[i] < v) {
std::swap(arr[i], arr[j + 1]);
++j;
}
}
std::swap(arr[j], arr[l]);
return j;
}
void QuickSortAdaptor(int arr[], int l, int r) {
if (l >= r) {
return;
}
int p = Partition(arr, l, r);
QuickSortAdaptor(arr, l, p);
QuickSortAdaptor(arr, p + 1, r);
}
void QuickSort(int arr[], int n) {
if (n <= 1) {
return;
}
QuickSortAdaptor(arr, 0, n - 1);
}
快速排序第二版,将与标头重复的元素“均匀”分到左右两边,解决重复元素过多导致的性能下降问题
// partition优化1,将与标头v相同的元素“均匀”分布在左、右两边
int Partition(int arr[], int l, int r) {
// 优化,随机化选择v
std::swap(arr[l], arr[rand() % (r - l + 1) + l]);
int v = arr[l];
int i = l + 1;
int j = r;
// arr[l...i) 存储小于等于v的元素
// arr(j....r] 存储大于等于v的元素
while (true) {
while (i <= r && arr[i] < v) {
++i;
}
while (j >= l && arr[j] > v) {
--j;
}
if (i > j) {
break;
}
std::swap(arr[i], arr[j]);
++i;
--j;
}
return j;
}
快速排序第三版,将重复元素单独分一段,即分成 <v, ==v, >v三段,即三路快排
// partition优化2,将与标头v相同的元素单独分成一段,即三路快排
std::pair<int, int> Partition3ways(int arr[], int l, int r) {
// 优化,随机化选择标头v
std::swap(arr[l], arr[rand() % (r - l + 1) + l]);
int v = arr[l];
int lt = l;
int gt = r + 1;
int i = l + 1;
// arr[l+1...lt] 存储 <v 的元素
// arr[gt....r] 存储 >v 的元素
// arr[lt+1....i) 存储 ==v 的元素
while (i < gt) {
if (arr[i] == v) {
++i;
continue;
} else if (arr[i] < v) {
std::swap(arr[i], arr[lt + 1]);
++lt;
++i;
continue;
} else {
std::swap(arr[i], arr[gt - 1]);
--gt;
continue;;
}
}
std::swap(arr[l], arr[lt]);
return {lt - 1, gt};
}
void QuickSortAdaptor3ways(int arr[], int l, int r) {
if (l >= r) {
return;
}
auto p = Partition3ways(arr, l, r);
QuickSortAdaptor3ways(arr, l, p.first);
QuickSortAdaptor3ways(arr, p.second, r);
}
// 三路快排
void QuickSort3ways(int arr[], int n) {
if (n <= 1) {
return;
}
QuickSortAdaptor3ways(arr, 0, n - 1);
}
测试
void test() {
int arr1[]{9, 3, 7, 6, 5, 1, 8, 2, 4};
int arr1r[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
QuickSort(arr1, 9);
assert(SortCommon::ArrEqual(arr1, arr1r, 9) == true);
int arr2[]{1};
int arr2r[]{1};
QuickSort(arr2, 1);
assert(SortCommon::ArrEqual(arr2, arr2r, 1));
int arr3[]{2, 1};
int arr3r[]{1, 2};
QuickSort(arr3, 2);
assert(SortCommon::ArrEqual(arr3, arr3r, 2));
int arr4[]{5, 3, 3, 7, 5, 5, 5, 5, 1, 7, 2, 7, 7, 7, 7};
int arr4r[]{1, 2, 3, 3, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7};
QuickSort3ways(arr4, 15);
assert(SortCommon::ArrEqual(arr4, arr4r, 15));
int arr5[]{1, 3, 2};
int arr5r[]{1, 2, 3};
QuickSort(arr5, 3);
assert(SortCommon::ArrEqual(arr5, arr5r, 3));
return;
}