下面是qSort()
使用的partition()
逻辑,
static void qSort(List *list, int low, int high, compareTo compare){
if(high <= low){
return; // no partition for sub array of size 1
}
int pivotIndex = partition(list, low, high, compare);
qSort(list, low, pivotIndex-1, compare);
qSort(list, pivotIndex+1, high, compare);
}
static int partition(List *list, int low, int high, compareTo compare){
int pivot = low;
int leftIndex = low + 1;
int rightIndex = high;
const void **array = list->array;
while(true){
while( leftIndex < high && (compare(array[leftIndex], array[pivot]) < 0) ){
leftIndex++;
}
while( rightIndex > pivot && (compare(array[rightIndex], array[pivot]) > 0) ){
rightIndex--;
}
if(leftIndex >= rightIndex){
break; // partition is done
}
if( compare(array[leftIndex], array[rightIndex]) == 0 ){
leftIndex++; rightIndex--;
continue; //Maintain stability
}
arraySwap(list, leftIndex, rightIndex);
}
if( compare(array[pivot], array[rightIndex]) != 0 ){
arraySwap(list, pivot, rightIndex); // Maintain stability
}
return rightIndex;
}
其中 arraySwap()
&& compare()
定义为,
void arraySwap(List *list, int i, int j){
const void **array = list->array;
const void *tempPointer = array[i];
array[i] = array[j];
array[j] = tempPointer;
}
int compare(const void *key, const void *item){
if( ((Person *)key)->age < ((Person *)item)->age ){
return -1;
}else if( ((Person *)key)->age > ((Person *)item)->age ){
return 1;
}else{
return 0;
}
}
partition()
必须通过在每个 arraySwap()
之前进行额外检查来保持稳定性。
但下面的输出显示,稳定性得到部分保持(键 10
与键 50
不同),
$ ./sort.exe
Before sorting
Age,LastName,FirstName
50 B A
30 A B
20 X D
10 F A
50 A B
90 V E
60 N M
10 A B
After sorting
Age,LastName,FirstName
10 F A
10 A B
20 X D
30 A B
50 A B
50 B A
60 N M
90 V E
在partition()
函数中,
下面的代码块只是为了保持稳定性,
while(true){
....
if( compare(array[leftIndex], array[rightIndex]) == 0 ){
leftIndex++; rightIndex--;
continue; //Maintain stability
}
....
}
...
if( compare(array[pivot], array[rightIndex]) != 0 ){
...
}
问题:
为什么用key 50
录制不稳定?
最佳答案
快速排序是不稳定的,因为分区步骤可能会交换彼此比较相等的元素,从而使它们的顺序与原始数组中的顺序不同。
使快速排序稳定需要一个比较函数,该函数将始终为不同的元素返回非零值。
关于c - 为什么快速排序代码会破坏稳定性?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41731964/