jimmy19980625@gmail.com
(張軒愷)
學校
:
不指定學校
編號 : 261552
來源 : [123.194.35.10]
最後登入時間 ：
2024-02-03 06:45:39
找到中位數即可
關鍵程式碼
void DualPivotPartition(short *array, int *partitionIndices, int left, int right) {
.........
}
void DualPivotSelect(short *array, int left, int right, int median) {
if(left < right) {
int partitionIndices[2];
DualPivotPartition(array, partitionIndices, left, right);
if(median == partitionIndices[0] || median == partitionIndices[1])
return;
if(median < partitionIndices[0])
DualPivotSelect(array, left, partitionIndices[0] - 1, median);
else if(median > partitionIndices[1])
DualPivotSelect(array, partitionIndices[1] + 1, right, median);
else
DualPivotSelect(array, partitionIndices[0] + 1, partitionIndices[1] - 1, median);
}
}
由雙樞軸快排改寫
得到的兩個分割索引如果等於median 即可停止排序
C 0.3s
jimmy19980625@gmail.com
(張軒愷)
學校
:
不指定學校
編號 : 261552
來源 : [123.194.35.10]
最後登入時間 ：
2024-02-03 06:45:39
找到中位數即可
關鍵程式碼
void DualPivotPartition(short *array, int *partitionIndices, int left, int right) {
.........
}
void DualPivotSelect(short *array, int left, int right, int median) {
if(left < right) {
int partitionIndices[2];
DualPivotPartition(array, partitionIndices, left, right);
if(median == partitionIndices[0] || median == partitionIndices[1])
return;
if(median < partitionIndices[0])
DualPivotSelect(array, left, partitionIndices[0] - 1, median);
else if(median > partitionIndices[1])
DualPivotSelect(array, partitionIndices[1] + 1, right, median);
else
DualPivotSelect(array, partitionIndices[0] + 1, partitionIndices[1] - 1, median);
}
}
由雙樞軸快排改寫得到的兩個分割索引如果等於median 即可停止排序
jimmy19980625@gmail.com
(張軒愷)
學校
:
不指定學校
編號 : 261552
來源 : [123.194.35.10]
最後登入時間 ：
2024-02-03 06:45:39
找到中位數即可
關鍵程式碼
void DualPivotPartition(short *array, int *partitionIndices, int left, int right) {
.........
}
void DualPivotSelect(short *array, int left, int right, int median) {
if(left < right) {
int partitionIndices[2];
DualPivotPartition(array, partitionIndices, left, right);
if(median == partitionIndices[0] || median == partitionIndices[1])
return;
if(median < partitionIndices[0])
DualPivotSelect(array, left, partitionIndices[0] - 1, median);
else if(median > partitionIndices[1])
DualPivotSelect(array, partitionIndices[1] + 1, right, median);
else
DualPivotSelect(array, partitionIndices[0] + 1, partitionIndices[1] - 1, median);
}
}
由雙樞軸快排改寫得到的兩個分割索引如果等於median 即可停止排序