我需要實作一個使用隨機樞軸的快速排序演算法；我正在使用大矩陣，所以我無法承受最壞的情況。
現在，我發現這個實作可以正常作業，但它使用第一個元素作為樞軸。
我已經修改它以適應我的場景（我正在使用稀疏矩陣，我需要按“行索引，列索引”對元素進行排序），這就是我所擁有的：
void quicksortSparseMatrix(struct sparsematrix *matrix,int first,int last){
int i, j, pivot, temp_I, temp_J;
double temp_val;
if(first<last){
pivot=first; //(rand() % (last - first 1)) first;
i=first;
j=last;
while(i<j){
while(lessEqual(matrix,i, pivot)&&i<last)
i ;
while(greater(matrix,j, pivot))
j--;
if(i<j){
temp_I = matrix->I[i];
temp_J = matrix->J[i];
temp_val = matrix->val[i];
matrix->I[i] = matrix->I[j];
matrix->J[i] = matrix->J[j];
matrix->val[i] = matrix->val[j];
matrix->I[j]=temp_I;
matrix->J[j]=temp_J;
matrix->val[j]=temp_val;
}
}
temp_I = matrix->I[pivot];
temp_J = matrix->J[pivot];
temp_val = matrix->val[pivot];
matrix->I[pivot] = matrix->I[j];
matrix->J[pivot] = matrix->J[j];
matrix->val[pivot] = matrix->val[j];
matrix->I[j]=temp_I;
matrix->J[j]=temp_J;
matrix->val[j]=temp_val;
quicksortSparseMatrix(matrix,first,j-1);
quicksortSparseMatrix(matrix,j 1,last);
}
}
現在，問題是我正在使用的一些矩陣幾乎是排序的，并且演算法運行得非常慢。我想修改我的演算法以使其使用隨機樞軸，但是如果我應用您在上面的代碼中看到的更改pivot=(rand() % (last - first 1)) first;，該演算法不會正確地對資料進行排序。
誰能幫我弄清楚如何更改演算法以使用隨機樞軸并對資料進行正確排序？
編輯：這是 struct sparsematrix 定義，我認為你不需要它，但為了完整性......
struct sparsematrix {
int M, N, nz;
int *I, *J;
double *val;
};
uj5u.com熱心網友回復：
Pivot 應該是一個值，而不是一個索引。第一個比較應該小于（而不是小于等于），這也將消除檢查的需要i < last。交換后，應該有i and j--。對于 Hoare 磁區方案的這種變體，最后兩行應該是quicksortSparseMatrix(matrix,first,j);和。quicksortSparseMatrix(matrix,i,last);陣列示例代碼：
void QuickSort(int *a, int lo, int hi)
{
int i, j;
int p, t;
if(lo >= hi)
return;
p = a[lo 1 (rand() % (hi - lo))];
i = lo;
j = hi;
while (i <= j){
while (a[i] < p)i ;
while (a[j] > p)j--;
if (i > j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
i ;
j--;
}
QuickSort(a, lo, j);
QuickSort(a, i, hi);
}
對矩陣行的索引陣列進行合并排序可能更快：索引的移動更多，但矩陣行的比較更少。合并排序需要第二個臨時索引陣列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505876.html
上一篇：在Map<String,Integer>中查找與MaxInteger值關聯的String鍵
下一篇：長度為5的回文數