排序算法的理论与实践

排序是对对象执行的活动或操作的基本类型之一。即使在童年时期，孩子们就被教导如何分类，发展他们的思维。计算机和程序也不例外。算法种类繁多。我建议您看看它们是什么以及它们如何工作。另外，如果有一天你在面试中被问到其中一个怎么办？

介绍

对元素进行排序是开发人员必须习惯的算法类别之一。如果说以前我读书的时候，计算机科学还没有那么被重视的话，那么现在在学校他们应该能够实现排序算法并理解它们。基本算法（最简单的算法）是使用循环实现的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 更改为数组中的最后一个元素。事实上，我们只是获取数组中的每个元素并打印其内容。数组中的元素越多，执行代码所需的时间就越长。也就是说，如果 n 是元素的数量，则 n=10 时程序的执行时间将是 n=5 时的 2 倍。当我们的程序有一个循环时，执行时间会线性增加：元素越多，执行时间就越长。事实证明，上述代码的算法在线性时间 (n) 内工作。在这种情况下，“算法复杂度”被称为 O(n)。这种表示法也称为“大O”或“渐近行为”。但你可以简单地记住“算法的复杂性”。

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

所以，我们有一个数组并且可以迭代它。伟大的。现在让我们尝试按升序对其进行排序。这对我们意味着什么？这意味着给定两个元素（例如，a=6，b=5），如果 a 大于 b（如果 a > b），我们必须交换 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 < 1 将不会返回 true，因此我们可以保护自己免受数组只有一个元素或根本没有元素的情况的影响，并且代码看起来会更好。但我们的最终数组无论如何都没有排序，因为...... 不可能一次性对所有人进行排序。我们必须添加另一个循环，在其中我们将逐个执行传递，直到获得排序的数组：

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));

这种排序是不稳定的，因为 相同的元素（从我们对元素进行排序的特征的角度来看）可以改变它们的位置。维基百科文章中给出了一个很好的例子：Sorting_by-selection。相关材料：

• “ JavaRush：排序算法。选择排序”
• 《CS50：选择排序》

插入排序

插入排序也具有二次复杂度，因为我们再次有一个循环中的循环。它与选择排序有什么不同？这种排序是“稳定的”。这意味着相同的元素不会改变它们的顺序。我们排序所依据的特征是相同的。

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	// Retrieve the value of the element
	int value = array[left];
	// Move through the elements that are before the pulled element
	int i = left - 1;
	for (; i >= 0; i--) {
		// If a smaller value is pulled out, move the larger element further
		if (value < array[i]) {
			array[i + 1] = array[i];
		} else {
			// If the pulled element is larger, stop
			break;
		}
	}
	// Insert the extracted value into the freed space
	array[i + 1] = value;
}
System.out.println(Arrays.toString(array));

相关材料：

• Java 插入排序解释
• CS50：插入排序
• JavaRush 上的 CS50：插入排序

穿梭排序

在简单排序中，还有一种就是穿梭排序。但我更喜欢穿梭巴士。在我看来，我们很少谈论航天飞机，航天飞机更多的是跑步。因此，更容易想象航天飞机是如何发射到太空的。这是与该算法的关联。算法的本质是什么？该算法的本质是我们从左到右迭代，在交换元素时，我们检查剩下的所有其他元素，看看是否需要重复交换。

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 介绍穿梭排序，作者：Jack Brown

希尔排序

另一种简单的排序是希尔排序。它的本质类似于冒泡排序，但是每次迭代我们所比较的元素之间都有不同的差距。每次迭代它都会减半。这是一个示例实现：

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 difference between the elements
while (gap >= 1) {
    for (int right = 0; right < array.length; right++) {
        // Shift the right pointer until we can find one that
        // there won't be enough space 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 决策 1 2.03a 希尔排序 - 8 个数字的示例

归并排序

除了所示的简单排序之外，还有更复杂的排序。例如，归并排序。首先，递归会对我们有所帮助。其次，我们的复杂性将不再像我们习惯的那样是二次的。该算法的复杂度是对数的。写为 O(n log n)。那么让我们这样做吧。首先，让我们编写一个对排序方法的递归调用：

public static void mergeSort(int[] source, int left, int right) {
        // Choose a separator, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Execute this function recursively for the two halves (if we can split(
        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) {
        // Choose a separator, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Execute this function recursively for the two halves (if we can split(
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
        // Create a temporary array with the desired size
        int[] buffer = new int[right - left + 1];
        // Starting from the specified left border, go through each element
        int cursor = left;
        for (int i = 0; i < buffer.length; i++) {
            // We use the delimeter to point to the element from the right side
            // If delimeter > right, then there are no unadded elements left on the right side
            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)。正如您所看到的，本质在于我们将一个数组作为输入，该数组指示要排序的部分的开头和结尾。当排序开始时，这是数组的开头和结尾。接下来我们计算 delimiter - 分隔符的位置。如果除法器可以分为两部分，那么我们对除法器将数组分成的部分进行递归排序。我们准备一个额外的缓冲区数组，在其中选择已排序的部分。接下来，我们将光标放在要排序的区域的开头，并开始遍历我们准备好的空数组中的每个元素，并用最小的元素填充它。如果光标指向的元素小于除数指向的元素，我们将该元素放入缓冲区数组中并移动光标。否则，我们将分隔符指向的元素放入缓冲区数组中并移动分隔符。一旦分隔符超出排序区域的边界或者填充整个数组，指定的范围就被认为是排序的。 相关材料：

• JavaRush：排序算法。归并排序
• CS50：归并排序

计数排序和基数排序

另一个有趣的排序算法是计数排序。这种情况下的算法复杂度将为 O(n+k)，其中 n 是元素的数量，k 是元素的最大值。该算法有一个问题：我们需要知道数组中的最小值和最大值。下面是计数排序的示例实现：

public static int[] countingSort(int[] theArray, int maxValue) {
        // Array with "counters" ranging from 0 to the maximum value
        int numCounts[] = new int[maxValue + 1];
        // In the corresponding cell (index = value) we increase the counter
        for (int num : theArray) {
            numCounts[num]++;
        }
        // Prepare array for sorted result
        int[] sortedArray = new int[theArray.length];
        int currentSortedIndex = 0;
        // go through the array with "counters"
        for (int n = 0; n < numCounts.length; n++) {
            int count = numCounts[n];
            // go by the number of values
            for (int k = 0; k < count; k++) {
                sortedArray[currentSortedIndex] = n;
                currentSortedIndex++;
            }
        }
        return sortedArray;
    }

据我们了解，当我们必须提前知道最小值和最大值时，这是非常不方便的。还有另一种算法——基数排序。我在这里仅以视觉方式展示该算法。实现方式见材料： 材料：

• 有关计数排序的视频

Java快速排序

好吧，甜点 - 最著名的算法之一：快速排序。它具有算法复杂性，即我们有 O(n log n)。这种排序也称为霍尔排序。有趣的是，该算法是霍尔在苏联期间发明的，他在莫斯科大学学习计算机翻译，并正在开发一本俄英短语手册。该算法还用于 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 while element is less than pivot
            while (source[leftMarker] < pivot) {
                leftMarker++;
            }
            // Move the right marker until element is greater than pivot
            while (source[rightMarker] > pivot) {
                rightMarker--;
            }
            // Check if you don't need to swap elements pointed to by markers
            if (leftMarker <= rightMarker) {
                // The left marker will only be less than the right marker if we have to swap
                if (leftMarker < rightMarker) {
                    int tmp = source[leftMarker];
                    source[leftMarker] = source[rightMarker];
                    source[rightMarker] = tmp;
                }
                // Move markers to get new borders
                leftMarker++;
                rightMarker--;
            }
        } while (leftMarker <= rightMarker);

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

这里的一切都很可怕，所以我们会弄清楚的。对于输入数组int[]源，我们设置两个标记，左 (L) 和右 (R)。第一次调用时，它们匹配数组的开头和结尾。接下来，确定支撑元素，即pivot。之后，我们的任务是将小于 的值pivot向左移动pivot，将大于的值向右移动。为此，首先移动指针，L直到找到大于 的值pivot。如果没有找到更小的值，则 L совпадёт с pivot. Потом двигаем указатель R пока не найдём меньшее, чем pivot meaning. Если меньшее meaning не нашли, то R совпадёт с pivot. Далее, если указатель L находится до указателя R or совпадает с ним, то пытаемся выполнить обмен элементов, если элемент L меньше, чем R. Далее L сдвигаем вправо на 1 позицию, R сдвигаем влево на одну позицию. Когда левый маркер L окажется за правым маркером R это будет означать, что обмен закончен, слева от pivot меньшие значения, справа от pivot — большие значения. После этого рекурсивно вызываем такую же сортировку для участков массива от начала сортируемого участка до правого маркера и от левого маркера до конца сортируемого участка. Почему от начала до правого? Потому что в конце итерации так и получится, что правый маркер сдвинется настолько, что станет границей части слева. Этот алгоритм более сложный, чем простая sorting, поэтому его лучше зарисовать. Возьмём белый лист бумаги, запишем: 4 2 6 7 3 , а Pivot по центру, т.е. число 6. Обведём его в круг. Под 4 напишем L, под 3 напишем R. 4 меньше чем 6, 2 меньше чем 6. Total, L переместился на положение pivot, т.к. по условию L не может уйти дальше, чем pivot. Напишем снова 4 2 6 7 3 , обведём 6 вкруг ( pivot) и поставим под ним L. Теперь двигаем указатель R. 3 меньше чем 6, поэтому ставим маркер R на цифру 3. Так How 3 меньше, чем pivot 6 выполняем swap, т.е. обмен. Запишем результат: 4 2 3 7 6 , обводим 6 вкруг, т.к. он по прежнему pivot. Указатель L на цифре 3, указатель R на цифре 6. Мы помним, что двигаем указатели до тех пор, пока L не зайдём за R. L двигаем на следующую цифру. Тут хочется разобрать два варианта: если бы предпоследняя цифра была 7 и если бы она была не 7, а 1. Предпоследня цифра 1: Сдвинули указатель L на цифру 1, т.к. мы можем двигать L до тех пор, пока указатель L указывает на цифру, меньшую чем pivot. А вот R мы не можем сдвинуть с 6, т.к. R не мы можем двигать только если указатель R указывает на цифру, которая больше чем pivot. swap не делаем, т.к. 1 меньше 6. Записываем положение: 4 2 3 1 6, обводим pivot 6. L сдвигается на pivot и больше не двигается. R тоже не двигается. Обмен не производим. Сдвигаем L и R на одну позицию и подписываем цифру 1 маркером R, а L получается вне числа. Т.к. L вне числа — ничего не делаем, а вот часть 4 2 3 1 выписываем снова, т.к. это наша левая часть, меньшая, чем pivot 6. Выделяем новый pivot и начинаем всё снова ) Предпоследняя цифра 7: Сдвинули указать L на цифру 7, правый указатель не можем двигать, т.к. он уже указывает на pivot. т.к. 7 больше, чем pivot, то делаем swap. Запишем результат: 4 2 3 6 7, обводим 6 кружком, т.к. он pivot. Указатель L теперь сдвигается на цифру 7, а указатель R сдвигается на цифру 3. Часть от L до конца нет смысла сортировать, т.к. там всего 1 элемент, а вот часть от 4 до указателя R отправляем на сортировку. Выбираем pivot и начинаем всё снова ) Может на первый взгляд показаться, что если расставить много одинаковых с pivot значений, это сломает алгоритм, но это не так. Можно напридумывать каверзных вариантов и на бумажке убедиться, что всё правильно и подивиться, How такие простые действия предоставляют такой надёжный механизм. Единственный минус — такая sorting не является стабильной. Т.к. при выполнении обмена одинаковые элементы могут поменять свой порядок, если один из них встретился до pivot до того, How другой элемент попал в часть до pivot при помощи обмена. Материал:

• Фоксфорд: Алгоритмы поиска и сортировки: Быстрая sorting Хоара

Итог

Выше мы рассмотрели "джентельменский" набор алгоритмов сортировки, реализованных на Java. Алгоритмы вообще штука полезная, How с прикладной точки зрения, так и с точки зрения развития мышления. Некоторые из них попроще, некоторые посложнее. По Howим-то умные люди защищали различные работы на степени, а по другим писали толстые-толстые книги. Надеюсь, приложенный к статье материал позволит вам узнать ещё больше, так How это обзорная статья, которая и так получилась увесистой. И цель её — дать небольшое вступление. Про введение в алгоритмы можно так же прочитать ознакомиться с книгой " Грокаем Алгоримы". Также мне нравится плэйлист от Jack Brown — AQA Decision 1 1.01 Tracing an Algorithm. Ради интереса можно посмотреть на визуализацию алгоритмов на sorting.at и visualgo.net. Ну и весь Youtube к вашим услугам.