我正在用 C 撰寫一個演算法，用戶輸入他們想要排序的數字，然后程式生成一個亂數陣列，并對它們進行排序。它還顯示排序所花費的時間。
它僅適用于某些試驗，即使我使用相同的輸入。例如，如果我要求程式對一個包含 20 個數字的陣列進行排序，則會發生以下三種情況之一：
- 它將毫無問題地對陣列進行排序。
- 演算法將超時，終端將列印“Segmentation fault: 11”。
- 該演算法將以正確的順序對數字進行排序，但一個數字將被隨機負數替換。
這是我的磁區演算法（給我帶來麻煩的東西）。我選擇第一個/左邊的專案作為我的支點：
int partition(int arr[], int leftIndex, int rightIndex)
{
int i = leftIndex;
int j = rightIndex;
int pivotValue = arr[leftIndex];
while(i < j){
while(arr[i] <= pivotValue){
i ;
}
while(arr[j] > pivotValue && i < j){
j--;
}
if(i < j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i - 1];
arr[i - 1] = arr[leftIndex];
arr[leftIndex] = temp;
return i - 1;
}
這是我的快速排序演算法：
void quickSort(int arr[], int left, int right)
{
if (left < right)
{
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot 1, right);
}
return;
}
這是我在 main() 中呼叫所有內容的地方：
int main()
{
clock_t sTime, eTime;
int n;
cout << "Enter an array size: " << endl;
cin >> n;
cout << endl;
int originalArray[n];
cout << "Start generating random numbers..." << endl;
for(int index=0; index<n; index ){
originalArray[index] = (rand()%100) 1;
}
cout << "Original array values: ";
printArray(originalArray, n);
cout<<"\n\n";
//Makes a copy of the original array to preserve its original order
int quickArray[sizeof(originalArray)];
for(int i = 0; i < sizeof(originalArray); i ){
quickArray[i] = originalArray[i];
}
//Perform quicksort
sTime = clock();
quickSort(quickArray, 0, n-1);
eTime = clock();
printf("Sorted array by quickSort: ");
printArray(quickArray, n);
cout << "\nTotal CPU time used in quickSort: " << (double)(eTime-sTime) / CLOCKS_PER_SEC * 1000.0 << " ms" << endl;
cout << endl;
return 0;
}
uj5u.com熱心網友回復：
#include <bits/stdc .h>
using namespace std;
int partition(int arr[], int leftIndex, int rightIndex)
{
int pivotIndex = leftIndex;
int pivotValue = arr[pivotIndex];
int i = leftIndex;
int j = rightIndex;
while(i < j){
while(arr[i] <= pivotValue){
i ;
if(i >= rightIndex) break;
}
while(arr[j] >= pivotValue){
j--;
if(j <= leftIndex) break;
}
if(i < j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap
arr[pivotIndex] = arr[j];
arr[j] = pivotValue;
return j;
}
void quickSort(int arr[], int left, int right)
{
if (left < right)
{
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot 1, right);
}
return;
}
int main()
{
clock_t sTime, eTime;
int n;
cout << "Enter an array size: " << endl;
cin >> n;
cout << endl;
int originalArray[n];
cout << "Start generating random numbers..." << endl;
for(int index=0; index<n; index ){
originalArray[index] = (rand()%100) 1;
}
cout << "Original array values: ";
for(auto c: originalArray) {
cout << c << " ";
}
cout<<"\n\n";
//Makes a copy of the original array to preserve its original order
int quickArray[n];
for(int i = 0; i < n; i ){
quickArray[i] = originalArray[i];
}
//Perform quicksort
sTime = clock();
quickSort(quickArray, 0, n-1);
eTime = clock();
printf("Sorted array by quickSort: ");
for(auto c: quickArray) {
cout << c << " ";
}
cout << endl;
cout << "\nTotal CPU time used in quickSort: " << (double)(eTime-sTime) / CLOCKS_PER_SEC * 1000.0 << " ms" << endl;
cout << endl;
return 0;
}
我遇到了幾個錯誤。首先，我break在方法的 while 回圈中添加了陳述句，以便在超出陣列邊界時partititon()中斷遞增i或遞減。j這可能就是您有時會遇到分段錯誤的原因。
然后我更改了磁區末尾的交換部分并回傳了j. 可能這部分沒有錯誤，但我發現這個解決方案更具可讀性。
然后我將創建新陣列的部分更改為int quickArray[n]，您正在創建quickArraywith sizeof(originalArray)，這是錯誤的，因為它用于創建具有更多元素的陣列。sizeof()回傳(number of elements) * 4，因為每個int占用 4 個位元組的記憶體。
現在，它應該可以正常作業了。
此外，選擇第一個元素作為樞軸可以使您的程式在O(n^2)最壞的情況下以時間復雜度作業，請嘗試在將陣列發送到quicksort()函式之前對其進行混洗。通過這樣做，您可以消除最壞的情況。
uj5u.com熱心網友回復：
我不確定它是否對您看到的所有問題負責，但我將從這段代碼開始：
while(i < j){
while(arr[i] <= pivotValue){
i ;
}
如果樞軸是陣列中的最大值，這（尤其是內部回圈）會做什么？
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424322.html
上一篇：n-1比較的最佳運行時間？
下一篇：了解排序平方演算法