以下是由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()之前进行额外的检查，以确保稳定性。
但是下面的输出显示，稳定性部分得到了维护（与关键字50不同，关键字10是稳定的）。
$ ./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 ){
...
}
问题：
为什么使用关键字 50 记录不稳定？