冒泡排序、选择排序、插入排序和快速排序中的交换次数和比较次数

Question

我已经用Java实现了所有四种排序算法。只是出于好奇，我决定看看每个算法中的交换次数和比较次数。对于一个大小为20的随机数组，这是我的结果:

冒泡排序: 87次交换，87次比较

插入排序: 87次交换，87次比较

选择排序: 19次交换，29次比较

快速排序: 11940次交换，我甚至不知道从哪里数比较次数

为什么冒泡排序和选择排序是相同的呢？我是说看着代码我几乎能看出来。循环基本上是一样的，我只想让有人指出来。

我可以看出为什么选择排序拥有最少的交换次数。

快速排序对我来说是个谜（该死的递归）。我想这就是为什么交换次数如此之多的原因。为什么我的实现如此缓慢？其他三个算法完成得比它早得多。

***** 代码 - 如果有遗漏请告诉我 *****

对于所有三种实现，交换都是相同的。

private void swap(int firstIndex, int secondIndex) {
    int temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
}

泡沫

public void sort() {
    for(int out = nElements-1; out > 1; out--) {// outer backwards loop
        for(int in = 0; in < out; in++) { // inner forward loop 
            if(array[in] > array[in+1]) {
                swap(in, in + 1);
                totalSwaps++;
                totalComparisons++;
            }
        }
    }
}

选择

public void sort() {
    for (int i = 0; i < nElements-1; i++) {
        int currentMinIndex = i;
        for (int j = i + 1; j < nElements; j++)
            if (array[j] < array[currentMinIndex]) {
                currentMinIndex = j;
                totalComparisons++;
            }
        swap(i, currentMinIndex);
        totalSwaps++;
    }
}

插入

public void sort() {
    for(int i = 1; i < nElements; i++) {
        for(int j = i; j > 0; j--) {
            if(array[j] < array[j-1]) {
                swap(j, j - 1);
                totalSwaps++;
                totalComparisons++;
            }
        }
    }
}

快速排序

public void sort() {
    sort(this.array, 0, array.length - 1);
}
private void sort(int[] array, int left, int right) {
    if(left >= right)
        return;

    int randomIndex = new Random().nextInt(array.length);
    int pivot = array[randomIndex];

    // returns the dividing point between the left side and the right side
    int index = partition(array, left, right, pivot);

    sort(array, left, index - 1);
    sort(array, index, right);
}

private int partition(int[] array, int left, int right, int pivot) {
    while(left <= right) {
        while(array[left] < pivot)  // will break when there's an element to the left of the pivot that's greater
            left++;

        while(array[right] > pivot)  // breaks when there's an element to the right of the pivot that's less
            right--;

        if(left <= right) {
            swap(left, right);
            left++;
            right--;
            totalSwaps++;

        }

    }

    return left;  // left will be at the partition point
}

主要

import java.util.Random;


public class Sorting {

private static final int maxSize = 50;
private static int[] randomArray() {
    int[] array = new int[maxSize];
    Random random = new Random();
    random.setSeed(0);
    for(int i = 0; i < maxSize; i++)
        array[i] = random.nextInt(50);
    return array;
}

public static void main(String[] args) {

    int[] randomArr = randomArray();

    BubbleSort bubbleSort = new BubbleSort(randomArr);
    bubbleSort.display();
    bubbleSort.sort();
    bubbleSort.display();

    randomArr = randomArray();

    SelectionSort selectionSort = new SelectionSort(randomArr);
    selectionSort.sort();
    selectionSort.display();

    randomArr = randomArray();

    InsertionSort insertionSort = new InsertionSort(randomArr);
    insertionSort.sort();
    insertionSort.display();

    System.out.println("Bubble Sort: Swaps = " + bubbleSort.totalSwaps + " Comparisons = " + bubbleSort.totalComparisons);
    System.out.println("Selection Sort: Swaps = " + selectionSort.totalSwaps + " Comparisons = " + selectionSort.totalComparisons);
    System.out.println("Insertion Sort: Swaps = " + insertionSort.totalSwaps + " Comparisons = " + insertionSort.totalComparisons);


    randomArr = randomArray();

    QuickSort quickSort = new QuickSort(randomArr);
    quickSort.sort();
    quickSort.display();

    System.out.println("Quick Sort: Swaps = " + quickSort.totalSwaps);
}

输出

10 48 29 47 15 3 41 11 19 4 27 27 23 12 45 44 34 25 41 20  // original
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48  // bubble
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48  // selection
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48  // insertion
Bubble Sort: Swaps = 87 Comparisons = 87
Selection Sort: Swaps = 19 Comparisons = 29
Insertion Sort: Swaps = 87 Comparisons = 87
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48  // quick
Quick Sort: Swaps = 25283

- MAA

---

你的比较计数完全错误。你应该计算执行的比较次数，而不是计算结果为“true”的次数。 - John Bollinger

此外，您的插入排序实现有点错误——尽管它可以正确排序，但它执行的比标准插入排序更多的比较（并且不计算任何额外的比较）。 - John Bollinger

Answer 1

关于如何计算操作，您可以考虑添加一层间接性。例如，使用这样一个类来执行和计数操作：

class Instrumentation {
    int compares = 0;
    int swaps = 0;

    boolean compareLess(int left, int right) {
        compares++;
        return left < right;
    }

    boolean compareGreater(int left, int right) {
        compares++;
        return left > right;
    }

    void swap(int[] array, int index1, int index2) {
        int temp = array[index1];

        array[index1] = array[index2];
        array[index2] = temp;

        swaps++;
    }

    void printResult(String label) {
        System.out.print(label);
        System.out.print(": Swaps = ");
        System.out.print(swaps);
        System.out.print(" Comparisons = ");
        System.out.println(compares);
    }
}

我已经修改了您的代码，使其足以使用该仪器类来计算操作次数，我得到了以下结果:

Original data:
10 48 29 47 15 3 41 11 19 4 27 27 23 12 45 44 34 25 41 20 

BubbleSort: Swaps = 87 Comparisons = 189
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 

SelectionSort: Swaps = 19 Comparisons = 190
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 

InsertionSort: Swaps = 87 Comparisons = 190
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 

QuickSort: Swaps = 3221 Comparisons = 110575
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 

现在观察比较排序的主要特征是，在最坏情况下，它们涉及将每个元素与每个其他元素进行比较。对于20个元素，这是20 * 19 / 2 = 190次比较，这基本上是您的比较排序实现在每种情况下产生的内容（冒泡排序减去1）。

事实上，这是您对冒泡排序和选择排序的预期结果，但不是您对平均情况下插入排序的预期结果。这是因为您的插入排序实现存在缺陷：该排序的前提是依赖其中间结果（将数组的第一部分排序）来减少所需的比较次数。当内部循环中的比较失败时（因此不需要交换），您应该从（内部）循环中退出，因为您知道在外部循环的下一次迭代之前不需要进行进一步的交换。实施这一点可将比较次数减少到您特定数据的105次。

比较排序中的交换次数也很有意义：冒泡排序和插入排序都通过与相邻元素进行一系列交换将每个元素从初始位置移动到最终位置。实际上，您的实现几乎是彼此的镜像。然而，我没有准备超越这个概括来进行实际证明。

至于选择排序，是的，对于排序n个元素，它总是执行（n *（n-1））/ 2次比较，并且最多进行n-1次交换（如果您执行并计算自我交换，则恰好为n-1）。

然后是您的快速排序。显然它不是很快——有些问题非常严重。稍微多一点的仪器告诉我，它下降到了远远超过递归深度（平均约400，而即使在最坏情况下也不应超过n）。问题出在您的随机枢轴选择上。您选择从整个数组中选择枢轴，而不是从正在排序的子数组中选择枢轴。要解决此问题，请替换。

int randomIndex = new Random().nextInt(array.length);

使用

int randomIndex = left + new Random().nextInt(right + 1 - left);

这样做应该会给你更多有利的比较和交换计数，但是直到你开始排序更大的数组，你才会真正意识到快速排序相对于其他算法提供了多少优势。

你还可以做更多的工作来改进你的快速排序实现，但我没有看到任何其他真正的错误。

- John Bollinger

---

非常感谢你，约翰。这非常有帮助。 - MAA