void partition(int *a, int size) { int pivot = a[0]; int left = 0, right = 0; for(left = 1, right = size-1; left <= right; left++, right--) { if(a[left] >= pivot && a[right] <= pivot){ swap(left, right, a); } } swap(0, right, a); }
为了进行快速排序,我编写了此方法来对数组进行分区,这是准备进行快速排序的第一步,并在此示例数据上对其进行了测试:
8 2 5 13 4 19 12 6 3 11 10 7 9
正确的输出应为:
6 2 5 7 4 3 8 12 19 11 10 13 9
但实际输出为:
6 2 5 13 4 3 8 12 19 11 10 7 9
该算法必须交换13,7但由于&&上述循环中的条件而失败。我想增加left只有a[left] >= pivot和递减right仅当a[right]<= pivot。
13
7
&&
left
a[left] >= pivot
right
a[right]<= pivot
您或多或少地回答了自己的问题。您可能想要执行以下操作:
void partition(int *a, int size) { int pivot = a[0]; int left, right; for(left = 1, right = size-1; left < right; ) { if(a[left] > pivot && a[right] <= pivot) { swap(left, right, a); } if(a[left] <= pivot) left++; if(a[right] > pivot) right--; } }