0

我是编程和java的新手，我试图理解一个实现“quickSort”算法对数组进行排序的代码。
现在..我了解了快速排序的基本思想，所以问题主要是关于代码本身。
在下面的代码（partition() 方法）中，我们有一个主循环（while(i<=j)）和两个循环，而不是另一个决策。我不明白的是，在主循环的每次迭代中没有执行循环下方交换的决定的原因是什么。简而言之，在最后一个while循环之后（while（arr [j]>pivot）j--;）为什么下面的条件没有被执行？他们做 j++ 并且代码应该在循环之外移动，不是吗？正如我从这个例子中了解到的......它没有！

这是我正在谈论的代码： 

public  class QuickSort {

    public static int list[] = {1,56,7,34,1,1,4,25,100,85,250};

    public static int partition(int arr[],int left,int right){

        int i = left;
        int j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while(i<=j){
             while(arr[i]<pivot){
                 i++;
             }
             while(arr[j]>pivot){
                 j--;
             }
             if(i<=j){
                 tmp = arr[i];
                 arr[i] = arr[j];
                 arr[j] = tmp;
                 i++;
                 j--;
             }
        }
        return i;
    }


    public static void quickSort(int arr[],int left,int right){
        int index = partition(arr,left,right);
        if(left<index-1){
            quickSort(arr,left,index-1);
        }
        if(index<right){
            quickSort(arr,index,right);
        }
    }
4

1 回答 1

0

如果我正确理解您的问题，那么您只是在谈论分区循环的最后一次迭代。

如果是这种情况，那么不执行交换块的原因仅仅是因为 if 条件不再成立，因为 i 已经停止了 j 右侧的一个位置。

于 2013-02-11T03:30:01.883 回答