以下是使用的partition()
逻辑qSort()
,
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 ){ ... }
题:
为什么用键记录50
不稳定?
快速排序是不稳定的,因为分区步骤可以交换相互比较相等的元素,因此将它们放在与原始数组不同的顺序中.
使快速排序稳定需要比较函数,该函数对于不同的元素总是返回非零.