当前位置:  开发笔记 > 编程语言 > 正文

为什么快速排序代码打破稳定性?

如何解决《为什么快速排序代码打破稳定性?》经验,为你挑选了1个好方法。

以下是使用的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不稳定?



1> chqrlie..:

快速排序是不稳定的,因为分区步骤可以交换相互比较相等的元素,因此将它们放在与原始数组不同的顺序中.

使快速排序稳定需要比较函数,该函数对于不同的元素总是返回非零.


@overexchange:没有.让我们举一个简单的例子:数组包含`A1 D1 C D2 A2`,pivot是`C`,分区步骤将交换`D1`和'A2`,有效地颠倒了`D1`和`D2`条目的顺序.
推荐阅读
mobiledu2402851377
这个屌丝很懒,什么也没留下!
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有