理论和实践中的排序算法

排序是我们对对象执行的基本操作之一。即使在孩提时代，孩子们在培养思维能力的过程中也被教导要进行分类。计算机和软件也不例外。Java 中有各种各样的排序算法。我建议您检查一下它们是什么以及它们是如何工作的。如果有一天你在面试中被问及其中一个怎么办？

介绍

对元素进行排序是开发人员必须了解的算法类别之一。如果说我在学校的时候计算机科学曾经不被重视，那么今天的学生必须能够实现和理解排序算法。最简单的基本算法是使用for循环实现的。自然地，要对元素集合（例如数组）进行排序，您需要以某种方式遍历集合。例如：

int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
	System.out.println(array[i]);
}

关于这段代码可以说些什么？我们有一个循环，其中我们将索引 ( int i) 从 0 更改为数组中的最后一个元素。事实上，我们只是获取数组中的每个元素并打印其内容。数组中的元素越多，代码完成所需的时间就越长。也就是说，ifn是元素的数量，whenn = 10程序的运行时间是 when 的两倍n = 5。如果我们的程序只有一个循环，执行时间会线性增长：元素越多，执行时间越长。事实证明，上述算法在线性时间内工作（n 的线性函数）。在这种情况下，我们称算法的复杂度为“O(n)”。这种表示法也称为“大 O”或“渐近行为”。但你只能记住“

最简单的排序算法（冒泡排序）

假设我们有一个数组，我们可以遍历它。伟大的。现在让我们尝试按升序对其进行排序。这是什么意思？这意味着给定两个元素（例如，a = 6, b = 5），我们必须重新排列aifb大于a（bif a > b）。当我们使用索引来处理集合时，这意味着什么（数组就是这种情况）？这意味着如果索引为 a 的元素大于索引为b( array[a] > array[b]) 的元素，则必须交换元素。有不同的方法来改变位置。但我们将使用一种简单、易懂且易于记忆的技术：

private void swap(int[] array, int ind1, int ind2) {
    int tmp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = tmp;
}

现在我们可以写如下：

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {
		swap(array, i, i-1);
	}
}
System.out.println(Arrays.toString(array));

如您所见，元素确实被交换了。我们从索引 1 开始，因为如果数组只有一个元素，则表达式array[i] < array[i-1]对索引无效0。这样做还可以保护我们免受数组没有元素或只有一个元素的情况的影响，并且它使代码看起来更好。但是生成的数组仍然没有排序，因为一次传递不足以进行排序。我们将不得不添加另一个循环，在这个循环中我们将一次又一次地执行遍历，直到我们得到一个排序的数组：

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
	needIteration = false;
	for (int i = 1; i < array.length; i++) {
		if (array[i] < array[i - 1]) {
			swap(array, i, i-1);
			needIteration = true;
		}
	}
}
System.out.println(Arrays.toString(array));

这样我们就完成了我们的第一个排序算法。我们重复外层循环 ( while) 直到我们决定不需要更多的迭代。默认情况下，在每次新迭代之前，我们假设我们的数组已排序并且我们不再需要循环。因此，我们按顺序移动元素并检查此假设。但是如果元素没有按顺序排列，那么我们交换元素并理解我们现在不能保证元素的顺序正确。这意味着我们需要执行另一次迭代。例如，假设我们有[3, 5, 2]。5不止3——一切都好。但是2小于5。但是，[3, 2, 5]需要另一次通过，因为3 > 2他们需要交换。因为我们在循环中使用循环，所以算法的复杂性增加了。给定n元素，它变为n * n，即O(n^2)。这称为二次复杂度。一般来说，我们无法确切知道需要多少次迭代。算法复杂度的表达式显示了在最坏情况下复杂度如何增加。即表示随着元素个数的n变化，执行时间会增加多少。冒泡排序是最简单且效率最低的排序算法之一。它有时也被称为“愚蠢的排序”。关于这个主题的材料：

• “HackerRank：算法 - 冒泡排序”

选择排序

另一种排序算法是选择排序。它还具有二次复杂性，但稍后会详细介绍。所以这个想法很简单。在每次传递中，我们选择最小的元素并将其移动到开头。此外，每次通过都开始向右迈出一步。换句话说，第一遍从第零个元素开始，第二遍从第一个元素开始，依此类推。它看起来像这样：

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	int minInd = left;
	for (int i = left; i < array.length; i++) {
		if (array[i] < array[minInd]) {
			minInd = i;
		}
	}
	swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));

这种排序是不稳定的，因为相同的元素（根据我们用来对元素排序的任何特征）可以改变它们的相对位置。维基百科关于选择排序的文章中有一个很好的例子。关于这个主题的材料：

• “CS50：选择排序”

插入排序

插入排序也有二次复杂度，因为我们又在一个循环中有一个循环。是什么让插入排序不同？这种排序算法是“稳定的”。这意味着相同的元素不会改变它们的相对顺序。同样，我们的意思是根据我们排序所依据的特征来表示相同。

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	// Get an element
	int value = array[left];
	// Iterate through the elements that are in front of this element
	int i = left - 1;
	for (; i >= 0; i--) {
		// If the current element is smaller, then move the larger element to the right.
		if (value < array[i]) {
			array[i + 1] = array[i];
		} else {
			// If the current element is larger, we stop
			break;
		}
	}
	// Insert the current value in the empty space
	array[i + 1] = value;
}
System.out.println(Arrays.toString(array));

穿梭排序

还有另一种简单的排序算法：穿梭排序。这也称为双向冒泡排序或调酒器排序。这些替代名称告诉我们，航天飞机类型与航天飞机无关。这是关于来回移动的东西。现在，当您想到这个算法时，您可以想到这一点。算法的本质是什么？该算法的本质是我们从左到右迭代，交换元素并检查是否需要交换另一个方向上剩余的任何元素。

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {
		swap(array, i, i - 1);
		for (int z = i - 1; (z - 1) >= 0; z--) {
			if (array[z] < array[z - 1]) {
				swap(array, z, z - 1);
			} else {
				break;
			}
		}
	}
}
System.out.println(Arrays.toString(array));

关于这个主题的材料：

• AQA 决定 1 2.02a 引入穿梭分类 by Jack Brown

壳排序

另一种简单的排序算法是 shell 排序。它的要点类似于冒泡排序，但在每次迭代中，我们在比较元素之间有不同的差距。每次迭代都会将其减半。这是一个实现：

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
    for (int right = 0; right < array.length; right++) {
        // Shift the right index until we find one for which
        // there is the necessary gap between it and the element before it
       for (int c = right - gap; c >= 0; c -= gap) {
           if (array[c] > array[c + gap]) {
               swap(array, c, c + gap);
           }
        }
    }
    // Recalculate the gap
    gap = gap / 2;
}
System.out.println(Arrays.toString(array));

关于这个主题的材料：

• AQA Decision 1 2.03a Shell Sort - 一个有 8 个数字的例子

合并排序

除了这些简单的排序算法，还有更复杂的排序算法。例如归并排序。有两点需要注意。首先，递归在这里拯救了我们。其次，算法的复杂度不再像我们习惯的那样是二次的。该算法的复杂度是对数的。这写成O(n log n). 因此，让我们实施它。首先，我们将编写对排序方法的递归调用：

public static void mergeSort(int[] source, int left, int right) {
        // Select the delimiter, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Recursively execute this function on the two halves (if we can split the input array)
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
}

现在，让我们将主要操作添加到我们的实现中。这是我们的超级方法：

public static void mergeSort(int[] source, int left, int right) {
        // Select the delimiter, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Recursively execute this function on the two halves (if we can split the input array)
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
        // Create a temporary array with the required size
        int[] buffer = new int[right - left + 1];
        // Starting from the specified left index, go through each element.
        int cursor = left;
        for (int i = 0; i < buffer.length; i++) {
            // We use delimeter to point to the element on the right half
            // If delimeter> right, then the right half has no elements that haven't been added
            if (delimiter > right || source[cursor] > source[delimiter]) {
                buffer[i] = source[cursor];
                cursor++;
            } else {
                buffer[i] = source[delimiter];
                delimiter++;
            }
        }
        System.arraycopy(buffer, 0, source, left, buffer.length);
}

我们可以通过调用来运行我们的示例mergeSort(array, 0, array.length-1). 如您所见，该过程归结为接受输入数组以及需要排序的部分的开头和结尾的指示。当排序开始时，这些是数组的开头和结尾。然后我们计算定界符，这是我们将拆分数组的索引。如果数组可以分为两部分，那么我们对数组的两半递归调用sort方法。我们准备了一个辅助缓冲区，我们将在其中插入已排序的部分。接下来，在要排序的部分的开头设置索引，并开始遍历空缓冲区的每个元素，用最小的元素填充它。如果索引指向的元素小于定界符指向的元素，我们将元素放入缓冲区并移动索引。否则，我们将分隔符指向的元素放入缓冲区并移动分隔符。一旦分隔符超出了正在排序的部分的边界，或者我们填充了整个数组，指定的范围就被认为是已排序的。关于这个主题的材料：

• CS50：归并排序
• 思路说明——归并排序

计数排序和基数排序

另一个有趣的排序算法是计数排序。这里的算法复杂度为O(n+k)，其中n是元素个数，k是元素的最大值。该算法确实有一个缺点：我们需要知道数组中的最小值和最大值。下面是计数排序的例子：

public static int[] countingSort(int[] theArray, int maxValue) {
        // An array of "counters", ranging from 0 to the maximum value
        int numCounts[] = new int[maxValue + 1];
        // We increase the counter in the corresponding cell (index = value)
        for (int num : theArray) {
            numCounts[num]++;
        }
        // Create an array to hold the sorted result
        int[] sortedArray = new int[theArray.length];
        int currentSortedIndex = 0;
        // Run through the array of "counters"
        for (int n = 0; n < numCounts.length; n++) {
            int count = numCounts[n];
            // Run through the number of values
            for (int k = 0; k < count; k++) {
                sortedArray[currentSortedIndex] = n;
                currentSortedIndex++;
            }
        }
        return sortedArray;
    }

你可以理解，当我们需要提前知道最小值和最大值时，这是非常不方便的。我们这里有另一种算法：基数排序。我只会在这里直观地展示算法。实现见补充材料：材料：

• 关于计数排序的视频
• 计数排序算法

快速排序

好了，甜点时间到了——快速排序，最著名的排序算法之一。它具有对数复杂度：O(n log n)。这种排序算法是由 Tony Hoare 开发的。有趣的是，他在苏联生活期间发明了它，在那里他在莫斯科大学学习机器翻译并开发了一本俄英短语手册。更重要的是，Java 在Arrays.sort. 怎么样Collections.sort？为什么不看看事物是如何“在引擎盖下”分类的呢？这是代码：

public static void quickSort(int[] source, int leftBorder, int rightBorder) {
        int leftMarker = leftBorder;
        int rightMarker = rightBorder;
        int pivot = source[(leftMarker + rightMarker) / 2];
        do {
            // Move the left marker from left to right as long as the element is less than pivot
            while (source[leftMarker] < pivot) {
                leftMarker++;
            }
            // Move the right marker as long as the element is greater than pivot
            while (source[rightMarker] > pivot) {
                rightMarker--;
            }
            // Check whether we need to swap the elements pointed to by the markers
            if (leftMarker <= rightMarker) {
                // The left marker will be less than the right one only if we need to do a swap
                if (leftMarker < rightMarker) {
                    int tmp = source[leftMarker];
                    source[leftMarker] = source[rightMarker];
                    source[rightMarker] = tmp;
                }
                // Shift the markers to get new borders
                leftMarker++;
                rightMarker--;
            }
        } while (leftMarker <= rightMarker);

        // Execute recursively on the parts
        if (leftMarker < rightBorder) {
            quickSort(source, leftMarker, rightBorder);
        }
        if (leftBorder < rightMarker) {
            quickSort(source, leftBorder, rightMarker);
        }
}

这些都是非常可怕的东西，所以让我们深入研究一下。对于输入数组 ( int[]source)，我们创建两个标记：左 ( L) 和右 ( R)。在第一次方法调用期间，它们对应于数组的开头和结尾。然后我们确定枢轴元素，它被恰当地命名为pivot。此后，我们的任务是将小于 的值移到pivot的左侧pivot，将大于 的值移到右侧。为此，我们首先移动L标记，直到找到大于 的值pivot。如果没有找到更小的值，则 L 变得等于 pivot。然后我们移动 R标记，直到找到一个小于 的值 pivot。如果没有找到更大的值，则 R变为等于 pivot。接下来，如果 L标记在标记之前 R或与其重合，那么如果 L元素小于 R元素，我们将尝试交换元素。然后我们 L向右移动 1，我们 R向左移动 1。当 L标记超出 R标记时，表示交换完成：较小的值在 的左侧 pivot，较大的值在 的右侧 pivot. 在此之后，我们对子数组递归调用相同的排序方法——从要排序的部分的开头到右标记，从左标记到要排序的部分的末尾。为什么从开始到右边的标记？因为在迭代结束时，事实证明右侧标记移动到足以成为左侧部分的边界。这个算法比简单的排序要复杂，所以最好画个草图。拿一张白纸，写上：4 2 6 7 3。然后写 pivot在中间，也就是数字6下面。把它圈起来。在 4 下，写 L，在 3 下，写 R。4 小于 6，2 小于 6。我们最终移动 L到该 pivot位置，因为 L不能移动过去 pivot, 根据条件。再写 4 2 6 7 3。圈出 6 ( pivot) 并放在 L它下面。现在移动 R标记。3 小于 6，所以将 R标记放在 3 上。由于 3 小于 6 ( pivot)，我们执行 swap. 写出结果：4 2 3 7 6。圈出6，因为还是那个 pivot。标记 L在 3 上。 R标记在 6 上。请记住，我们移动标记直到 L超出 R。移动 L到下一个数字。在这里我想探讨两种可能性：1）倒数第二个数字为 7 的情况和 2）倒数第二个数字为 1 而不是 7 的情况。如果 倒数第二个数字为 1：将标记移动 L到 1，因为我们可以移动 L只要 Lmarker 指向一个小于 pivot. 但是我们不能离开 R6，因为只有当标记指向大于 的数字时，我们才能移动 RR。 pivot我们不执行 a swap，因为 1 小于 6。写出当前情况：4 2 3 1 6。圈出 6 ( pivot)。 L移动 pivot并停止移动。 R不动。我们不执行交换。移动一个位置 L。 R将标记写 R在 1 下。 L标记超出范围。因为 L是越界的，我们什么都不做。但是，我们再次写 4 2 3 1，因为这是我们的左侧，小于 pivot(6)。选择新的 pivot并重新开始一切:) 如果倒数第二个数字是 7：将标记移动 L到 7。我们无法移动右侧标记，因为它已经指向轴心。7 大于 pivot，所以我们执行 a swap。写出结果：4 2 3 6 7。圈出6，因为它是 pivot。标记 L现在移到 7， R标记移到 3。从头到尾对部分进行排序没有意义 L，因为只有 1 个元素。但是，我们将 4 中的部分发送到 R标记器进行排序。我们选择 a pivot并重新开始 :) 乍一看，如果你添加很多等于 pivot，那么你就会破坏算法。但事实并非如此。您可以想出巧妙的组合，并在纸上说服自己一切都是正确的，并惊叹于如此简单的操作实现了如此可靠的排序机制。唯一的缺点是这种排序算法不稳定。 pivot因为如果在另一个元素交换到之前的部分之前遇到其中一个元素，交换可能会改变相同元素的相对顺序 pivot。

底线

上面，我们查看了一组用 Java 实现的“绅士”排序算法。无论是从应用的角度还是从学习如何思考的角度来看，算法通常都是有用的。有些更简单，有些更复杂。聪明人为他们的论文辩护。对于其他人，他们写了超厚的书。我希望补充材料能帮助你学到更多，因为这篇文章只是一个概述，已经证明是有分量的。它的目的是提供一个小的介绍。 如果您阅读“Grokking Algorithms ” ，您还可以找到对算法的介绍。我也喜欢 Jack Brown 的播放列表： AQA Decision 1 1.01 Tracing an Algorithm。为了好玩，您可以在 排序时看到算法可视化。 visualgo.net。