2

我必须在java中实现一个迭代快速排序来完成作业。我已经搜索了很多关于它的信息，但我找不到一个清楚解释如何实现迭代快速排序的网站。

我在java中找到了这段代码，它的排序很好，但我不知道它是如何工作的，但我知道递归快速排序是如何工作的。

我已经用我的问题评论了代码

public static void iterativeQsort(int[] arr) { 
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);
    stack.push(arr.length);
    while (!stack.isEmpty()) {
        int end = stack.pop();
        int start = stack.pop();
        if (end - start < 2) continue;
        int p = start + ((end-start)/2);
        p = partition(arr,p,start,end); 

        stack.push(p+1);
        stack.push(end);

        stack.push(start);
        stack.push(p);

    }
}

private static int partition(int[] arr, int p, int start, int end) {
    int l = start;
    int h = end - 2; //what is h and l variables for and why h has to be end -2?
    int piv = arr[p];
    swap(arr,p,end-1);

    while (l < h) {
        if (arr[l] < piv) {
            l++;
        } else if (arr[h] >= piv) { 
            h--;
        } else { 
            swap(arr,l,h);
        }
    }
    int idx = h;  // what is idx exactly?
    if (arr[h] < piv) idx++;
    swap(arr,end-1,idx);
    return idx;  //why return idx.
}
private static void swap(int[] arr, int i, int j) { 
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

我对分区方法很困惑，我不知道它做了什么。

如果有人可以向我解释进行迭代快速排序的主要步骤，我会很高兴。

谢谢你的帮助。

4

0 回答 0