我正在做一个比较冒泡排序和快速排序算法的项目。一切正常,直到我想对已经使用 Quicksort 方法排序的数据进行排序。它在大型阵列(50k、100k)上崩溃。
在我的例子中,我首先按降序对数据进行排序,然后尝试按升序排序,然后它崩溃了。
read(); // just creates an array with random integers
quickSortDSC(0, length - 1); //Here is the problem! (works if commented)
t1 = clock();
quickSortASC(0, length - 1);
t2 = clock();
cout << "Quick Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";
完整代码:
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
long length = 1000;
const long max_length = 100000;
int list[max_length];
void read()
{
ifstream fin("random.dat", ios::binary);
for (long i = 0; i < length; i++)
{
fin.read((char*)&list[i], sizeof(int));
}
fin.close();
}
void bubbleSort()
{
int temp;
for(long i = 0; i < length; i++)
{
for(long j = 0; j < length-i-1; j++)
{
if (list[j] > list[j+1])
{
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
long partitionASC(long left, long right)
{
int pivot_element = list[left];
int lb = left, ub = right;
int temp;
while (left < right)
{
while(list[left] <= pivot_element)
left++;
while(list[right] > pivot_element)
right--;
if (left < right)
{
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
list[lb] = list[right];
list[right] = pivot_element;
return right;
}
long partitionDSC(long left, long right)
{
int pivot_element = list[left];
int lb = left, ub = right;
int temp;
while (left < right)
{
while(list[left] >= pivot_element)
left++;
while(list[right] < pivot_element)
right--;
if (left < right)
{
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
list[lb] = list[right];
list[right] = pivot_element;
return right;
}
//ascending order
void quickSortASC(long left, long right)
{
long pivot;
if (left < right)
{
pivot = partitionASC(left, right);
quickSortASC(left, pivot-1);
quickSortASC(pivot+1, right);
}
}
//descending order
void quickSortDSC(long left, long right)
{
long pivot;
if (left < right)
{
pivot = partitionDSC(left, right);
quickSortDSC(left, pivot-1);
quickSortDSC(pivot+1, right);
}
}
int main()
{
double t1, t2;
for (length = 1000; length <= max_length; )
{
cout << "\nLength\t: " << length << '\n';
read();
t1 = clock();
bubbleSort();
t2 = clock();
cout << "Bubble Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";
read();
quickSortDSC(0, length - 1); //Here is the problem!
t1 = clock();
quickSortASC(0, length - 1);
t2 = clock();
cout << "Quick Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";
if(length == max_length)
break;
switch (length)
{
case 1000 :
length = 10000;
break;
case 10000 :
length = 50000;
break;
case 50000 :
length = 100000;
break;
}
}
return 0;
}
最佳答案
通过选择数组的第一个元素作为基准,您可以在数组已经排序时遇到快速排序的最坏情况行为。所以你会得到 O(n2) 的行为(更糟糕的是,O(n) 堆栈空间,这可能会让你发生堆栈溢出)。
为避免这种情况,请选择不同的枢轴。通常会选择中间元素作为枢轴:
int pivot_element = list[(left+right)/2];
或随机元素:
int pivot_element = list[left + random()%(right+1-left)];
关于c++ - 快速排序不适用于排序数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50090491/