java - QuickSort 测试仪调试

Question

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

1. partition0 性能为 1877，
2. 分区 2 是 781，
3. 分区 3 674，
4. partition4 大约是 595。

数字可能因不同的机器和不同的时间而异。我现在不能说出每个分区的错误，我有几个问题:

1. 我注意到 partition0 和 partition1 之间的唯一区别是 while 循环的条件:一个有 <=，另一个有 <。但是当我将第一个 <= 更改为 < 时，性能并没有改变。 2. 什么是 do{ } while(some condition)。和通常使用的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. 我不是 100% 确定，但我相信这是因为 last 和 first 用于检查左右索引是否相交。如果是这样，则不会发生交换，并且如果 first 和 last 相等，则当它到达执行交换的 if 语句时不会发生。

2. do-while loop 它就像一个while循环，不同的是它总是执行1次，不管语句是真还是假。然后它会像普通 while 循环一样执行该 block ，具体取决于您为其设置的 boolean 条件。

有关 do-while 循环的更多信息:http://www.tutorialspoint.com/java/java_loop_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内部，然后if last > first，一直执行直到语句为false。