如何避免我的索引在快速排序中越界

Question

我正在尝试实现一个快速排序的伪代码，它选择不同的元素作为枢轴，例如第一个元素作为枢轴、最后一个元素作为轴心、随机元素作为枢轴和中间元素作为枢轴。首先，我将第一个元素作为pivot处理，但如果pivot是数组中最大的数字，则索引将增长到大于数组的长度，导致索引超出长度的范围。快速排序实现适用于pivot是数组的第一个元素并且数组的第一元素最小的情况。当枢轴(在这种情况下(为8时，错误发生在第27行，它将停留在while([i] < pivot)，i加1。

我该如何避免这种情况？

这是我正在使用的伪代码：

Partition(A, p, r):
pivot ← A[p]`
i ← p + 1
j ← r
while i ≤ j
while A[i] < pivot
i ← i + 1
while A[j] > pivot
j ← j - 1
if i < j
swap A[i] with A[j]
swap A[p] with A[j]
return j

这是我的代码：

public class QuickSort {
//this global variable counts the comparisons
static long countComp = 0;

static void quickSort(int []array, int ft, int lt) {

if(ft < lt) {

int q = partitionFtE(array, ft, lt);
quickSort(array, ft, q - 1);
quickSort(array, q + 1, lt);    
}   
}   
//this method does quicksort with first element as pivot, ft = first element, lt = last element
static int partitionFtE(int []array, int ft, int lt) {          
int pivot = array[ft];      

int i = ft + 1;

int j = lt;

while(i <= j){
while(array[i] < pivot) {               
i = i + 1;
}           
while(array[j] > pivot) {
j = j - 1;              
}
//here we swap elements if i is lower than j
countComp++;
if(i < j) {
int temp = 0;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}       
}
//here we change the pivot where it suppose to be in the array
int temp2 = array[i];
temp2 = array[ft];
array[ft] = array[j];
array[j] = temp2;   

return j;   
}       
static void printArray(int []array) {

for(int i = 0; i < array.length; i++) {

System.out.print(array[i] + " ");           
}

System.out.println("n" + countComp);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//    int choice = menuData();
int[] intArray = {8, 7, 6, 5, 4, 3, 2, 1};
int n = intArray.length;    

quickSort(intArray, 0, n - 1);
System.out.println("Sorted array: ");
printArray(intArray);    
}
}

Answer 1

我使用了类中的另一个伪代码来修复此问题。这是伪代码：

//ft is first element, lt is last element
pivot := array[ft]
i := ft + 1;
for j:= ft + 1 to array length do
if array[j] < pivot
swap array[j] and array[i]
swap array[ft] and array[i - 1]
return i -1

这就是分区方法：

static int partition(int []array, int ft, int lt) {

int pivot = array[ft];
int i = ft + 1;

for(int j = ft + 1; j < array.length; j ++) {
if(array[j] < pivot) {
int temp = 0;
temp = array[j];
array[j] = array[i];
array[i] = temp;
i = i + 1;
}
}
int temp2 = array[ft];
array[ft] = array[i-1];
array[i-1] = temp2;

return i - 1;
}

Answer 2

后递减|递增Hoare分区方案示例：

void QuickSort(int *a, int lo, int hi)
{
int i, j;
int p, t;
if(lo >= hi)
return;
p = a[lo + (hi-lo)/2];
i = lo;
j = hi;
while (i <= j){
while (a[i] < p)i++;
while (a[j] > p)j--;
if (i > j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
i++;
j--;
}
QuickSort(a, lo, j);
QuickSort(a, i, hi);
}