QuickSort测试仪调试

Question

对于quickSort的4种分区方法，我有以下代码。现在，如果我运行代码，各个分区的性能如下所示

1. partition0性能为1877，
2. partition2是781，
3. partition3 674，
4. partition4在595年左右。

不同的机器和不同的时间，数字可能会有所不同。我现在不能告诉每个分区的错误，我也没有什么问题：

1. 我注意到partition0和partition1之间唯一的区别是while循环的条件:一个有<=，另一个有<。但是，当我将第一个<=更改为<时，性能并没有改变。2.什么是做{}时(某些条件)。它是否与通常使用的while循环相同？
2. 我注意到partition0和partition1之间唯一的区别是while循环的条件:一个有<=，另一个有<。但是，当我将第一个<=改为<时，性能并没有改变。
3. 什么是do{ } while(some condition)。它是否与通常使用的while循环相同？

import java.util.Arrays;
import java.util.Random;

public class QuickSortTester {
static private Random rand = new Random(0);

public static void main(String[] args) {

    int arraySize = 1000;

    Integer[] list;

    long start, end;

    list = generateSortedIntegerArray(arraySize);
    // list = generateRandomIntegerArray(arraySize);
    System.out.printf("\n%15d", arraySize);

    start = System.nanoTime();
    sort(list, 0);
    end = System.nanoTime();
    System.out.printf("\t%15d", (end - start) / 1000);
    if (!isSorted(list))
        System.out.printf("Not sorted - problems!");

    System.out.println();

    list = generateSortedIntegerArray(arraySize);
    // list = generateRandomIntegerArray(arraySize);
    System.out.printf("\n%15d", arraySize);

    start = System.nanoTime();
    sort(list, 1);
    end = System.nanoTime();
    System.out.printf("\t%15d", (end - start) / 1000);
    if (!isSorted(list))
        System.out.printf("Not sorted - problems!");

    System.out.println();
    list = generateSortedIntegerArray(arraySize);
    // list = generateRandomIntegerArray(arraySize);
    System.out.printf("\n%15d", arraySize);

    start = System.nanoTime();
    sort(list, 2);
    end = System.nanoTime();
    System.out.printf("\t%15d", (end - start) / 1000);
    if (!isSorted(list))
        System.out.printf("Not sorted - problems!");

    System.out.println();
    list = generateSortedIntegerArray(arraySize);
    //list = generateRandomIntegerArray(arraySize);
    System.out.printf("\n%15d", arraySize);

    start = System.nanoTime();
    sort(list, 3);
    end = System.nanoTime();
    System.out.printf("\t%15d", (end - start) / 1000);
    if (!isSorted(list))
        System.out.printf("Not sorted - problems!");

}


public static <E extends Comparable<E>> boolean isSorted(E[] list) {
    for (int i = 1; i < list.length; i++) {
        if (list[i - 1].compareTo(list[i]) > 0) {
            return false;
        }
    }
    return true;
}


public static Integer[] generateRandomIntegerArray(int size) {
    Integer list[] = new Integer[size];

    for (int i = 0; i < list.length; i++)
        // list[i] = rand.nextInt(10); //range from zero to number - 1
        list[i] = rand.nextInt(); // unlimited range
    return list;
}

public static Integer[] generateSortedIntegerArray(int size) {
    Integer list[] = generateRandomIntegerArray(size);
    Arrays.sort(list);
    return list;
}

public static <E extends Comparable<E>> void sort(E[] list, int version) {
    quickSort(list, 0, list.length - 1, version);
}

private static <E extends Comparable<E>> void quickSort(E[] list, int first, int last, int version) {
    if (last > first) {
        int pivotIndex;
        if (version == 0)
            pivotIndex = partition0(list, first, last);
        else if (version == 1)
            pivotIndex = partition1(list, first, last);
        else if (version == 2)
            pivotIndex = partition2(list, first, last);
        else
            pivotIndex = partition3(list, first, last);
        quickSort(list, first, pivotIndex - 1, version);
        quickSort(list, pivotIndex + 1, last, version);
    }
}

private static <E extends Comparable<E>> int partition0(E[] list, int first, int last) {
    int pivotIndex = (first + last) / 2;
    E pivot = list[pivotIndex]; // Choose the first element as the pivot
    swap(list, last, pivotIndex);
    pivotIndex = last;
    last--;
    while (last >= first) {
        // Search forward from left
        while (first <= last && list[first].compareTo(pivot) < 0) //problem
            first++;
        // Search backward from right
        while (first <= last && list[last].compareTo(pivot) >= 0)
            last--;

        // Swap two elements in the list
        if (last > first) {
            swap(list, first, last);
            first++;
            last--;
        }
    }
    swap(list, pivotIndex, first);

    return first;
}

private static <E extends Comparable<E>> int partition1(E[] list, int first, int last) {
    int pivotIndex = (first + last) / 2;
    E pivot = list[pivotIndex]; // Choose the first element as the pivot
    swap(list, last, pivotIndex);
    pivotIndex = last;
    last--;
    while (last >= first) {
        // Search forward from left
        while (first <= last && list[first].compareTo(pivot) < 0)
            first++;
        // Search backward from right
        while (first <= last && list[last].compareTo(pivot) >= 0)
            last--;

        // Swap two elements in the list
        if (last > first) {
            swap(list, first, last);
            first++;
            last--;
        }
    }
    swap(list, pivotIndex, first);

    return first;
}

private static <E extends Comparable<E>> int partition2(E[] list, int first, int last) {

    int pivotIndex = (first + last) / 2;

    E pivot = list[pivotIndex]; // Choose the first element as the pivot
    swap(list, last, pivotIndex);
    pivotIndex = last;
    last--;

    while (last > first) {
        // Search forward from left
        while (first <= last && list[first].compareTo(pivot) < 0)
            first++;
        // Search backward from right
        while (first <= last && list[last].compareTo(pivot) > 0)
            last--;

        // Swap two elements in the list
        if (last > first) {
            swap(list, first, last);
            first++;
            last--;
        }
    }
    swap(list, pivotIndex, first);

    return first;
}

private static <E extends Comparable<E>> int partition3(E[] list, int first, int last) {
    int pivotIndex = (first + last) / 2;
    E pivot = list[pivotIndex]; // Choose the first element as the pivot
    swap(list, last, pivotIndex);
    pivotIndex = last;
    last--;
    do {
        // Search forward from left
        while (first < last && list[first].compareTo(pivot) <= 0)
            first++;
        // Search backward from right
        while (first <= last && list[last].compareTo(pivot) > 0)
            last--;

        // Swap two elements in the list
        if (last >= first) {
            swap(list, first, last);
            first++;
            last--;
        }
    } while (last > first);

    swap(list, pivotIndex, first);

    return first;
}

private static <E> void swap(E[] list, int index1, int index2) {
    E tmp = list[index1];
    list[index1] = list[index2];
    list[index2] = tmp;
}

}

Answer 1

1. 我不是百分之百肯定，但我相信这是因为最后和第一是用来检查指数是否符合从左和右。如果是的话，交换将不会发生，如果第一个和最后一个相等，当它到达执行交换的If语句时将不会发生。
2. do-while循环--就像while循环一样，不同的是，不管语句是真是假，它总是执行1次。然后，它将像普通的while循环一样执行这个块，这取决于您为它设置的布尔条件。

有关do-while循环的更多信息：control.htm

在您的代码中：

do {
        // Search forward from left
        while (first < last && list[first].compareTo(pivot) <= 0)
            first++;
        // Search backward from right
        while (first <= last && list[last].compareTo(pivot) > 0)
            last--;

        // Swap two elements in the list
        if (last >= first) {
            swap(list, first, last);
            first++;
            last--;
        }
    } while (last > first);

它将始终先执行do的内部，然后如果last > first，将继续执行直到语句为false。