排序算法（Sorting Algorithms）
- 1. 冒泡排序（Bubble Sort）
- 2. 插入排序（Insertion Sort）
- 3. 选择排序（Selection Sort）
- 4. 归并排序（Merge Sort）
- 5. 快速排序（Quick Sort）
- 6. 堆排序（Heap Sort）
1. 冒泡排序（Bubble Sort）
冒泡排序几乎是所有算法教程里的第一个排序例子。冒泡排序简单，易于实现，且占用存储空间不多。唯一的问题是时间复杂度偏大（ ）。冒泡排序得名于它的性质。在冒泡排序中，最小的元素会像气泡一样渐渐地被交换到该组数据的开始位置。
冒泡排序的算法：
- 从头开始依次比较每对相邻的元素。如果前一个元素比后一个大，就交换他们两个的位置。（一轮过后，最大元素将会被交换到最后。）
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
下面给出了一个冒泡排序的例子。红色元素表示当前进行比较的元素位置。绿色元素是从首元素到该元素最大的元素，不参加下面的比较。
第一步，从首元素56的位置开始顺序依次比较，56>32，交换位置；56>15，交换位置；56>29，交换位置，56>24，交换位置。56标记为绿色。
第二步，同理，将32与其他元素比较，一直比较到56之前。
第三步，因为15<29，则不交换。下面继续比较29>24，交换位置。标记29为绿色。
第四步，15<24，不交换。标记24为绿色。
第五步，仅有15，标记为绿色，排序完成，算法结束。
下面是冒泡排序的Java代码bubbleSort方法。该方法将一个整型（int）数组的元素用冒泡排序算法从小到大进行排序。
查看和下载源代码public void bubbleSort(int array[]) {
// 获取当前数组长度，在第一遍比较交换的过程中，一直比较到数组的最后一个元素。
int len = array.length;
boolean swapped;
do {
// 如果有一遍比较没有导致一次交换操作的发生，那么该数组已经完成排序，程序停止。
swapped = false;
for(int i = 1; i < len; i++) {
// 从索引值1到len-1，顺序比较每对相邻元素，如果前一个元素（较小索引值）大于后一个元素值，则交换位置。
if(array[i-1] > array[i]) {
int tmp = array[i];
array[i] = array[i-1];
array[i-1] = tmp;
swapped = true;
}
// 在for循环结尾处，array[len-1]是array[0]到array[len-1]里最大的元素，下一轮不必再参与比较。
}
// 将len减1。
// 在进入下一轮循环时，算法排除掉当前的array[len-1]。
len--;
} while(swapped);
}
下面我们用冒泡排序算法排序一个数组。
[9, 3, 5, 8, 2, 4, 6, 7, 10, 1]
那么每一步的交换操作如下面的动图所示。注意该动图标记出的是交换操作，当比较一对相邻元素而前一元素小于后一元素时是没有交换操作的。
因为每个元素冒泡时，需要与所有剩下的元素依次进行比较。所以当有 个元素时，冒泡排序的时间消耗最差为
所以插入排序的时间复杂度为 。
下面是冒泡排序的动画小程序。小程序可接受随机生成的一组不重复的数据，或者用户输入的自定义数据。
2. 插入排序（Insertion Sort）
如果你会打扑克牌，那么你就一定应用过插入排序算法。这是一个很直观的例子，当我们从牌桌上摸牌时，有手中和桌上两组扑克牌。桌上的牌是乱序的而手中的牌是排好序的。我们每次从桌上（乱序）摸一张牌插入手中牌（已排序）的合适位置，使得手中牌仍然为排序状态。重复此操作直到桌上所有的牌都插入手中，排序完成。
如果我们直接套用此方法，就会需要有两个数组（手中牌和桌上牌），从而导致额外的内存消耗。因此我们可以将算法稍加改进，从而不用额外的内存便能达到同样的效果。
改进方法为我们将待排序数组逻辑上分为两部分：已排序部分和未排序部分。初始状态是只有首元素已排好序（因为只有一个元素，天然处于排序状态。）。从数组中取第一个未排序元素，插入已排序元素中。此时已排序元素增加一个而未排序元素减少一个。重复此步骤直到所有元素都为已排序元素。
插入排序算法描述：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出第一个未排序元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一个位置。
- 重复步骤3，直到找到已排序的元素小于或者等于新元素。
- 将新元素插入到当前位置。
- 重复步骤2~5直到所有元素都插入已排序部分。
下面的例子是一组插入排序示意图。红色的数字表示该元素为已排序元素，黑色数字为未排序元素。
第一步，第一个元素为已排序部分。
第二，取未排序部分第一个元素（32），从后向前依次比较已排序元素中的值，当前元素大于32时，向后挪一个位置。因为56>32，所以56向后挪一个位置，32插在56之前。此时已排序部分有32,56两个元素。
重复以上步骤。取15，依次与56和32比较。（因为比较顺序是从后向前），然后将15插入合适位置。
取29，再重复以上步骤。
取24，再重复以上步骤。当24插入到合适位置后，所有元素都已排序，算法结束。
以下是插入排序的Java代码。
查看和下载源代码public void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1; // 因为i是从1开始，所以i-1没有越界。
// 从已排序元素部分的最后一个向前依次与要插入的元素进行比较，每个比要插入元素大的元素都要后移。
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
下面我们用插入排序算法排序下面的数组。注意比较和其他排序算法的区别。
[9, 3, 5, 8, 2, 4, 6, 7, 10, 1]
在下面的动图里，红色代表刚刚被移动位置的元素。
因为每个元素插入时，最坏情况是都要和所有之前已插入的元素进行比较。所以当有 个元素时，插入排序的时间消耗最差为
所以插入排序的时间复杂度为 。
下面是插入排序的动画小程序。小程序可接受随机生成的一组不重复的数据，或者用户输入的自定义数据。
3. 选择排序（Selection Sort）
选择排序每次在未排序的数据中选取最小的一个并将它移动到未排序数据的最前面使其变为已排序数据。然后再在剩下的未排序数据中重复此操作直到所有数据都排序。因此，每个元素最多只需移动一次便可到达其最终的排序位置。如果一个元素已经在其排序后的位置，则不必移动。所以在基于交换操作的排序算法中，选择排序算法是需要移动次数较少的。
下图给出了用选择排序算法将数组[56, 32, 15, 29, 24]排序的例子。当前未排序元素中的最小元素标记为红色，已排序元素标记为绿色，未排序元素标记为黑色。
- 所有元素均未排序。找出其中最小的元素（即15）。
- 将其交换至未排序元素的最左边（即与56交换位置）。交换后该元素（15）处于其最终的排序位置，未排序元素为剩下的所有元素。
- 重复1，2两步直到所有元素变为已排序元素。
选择排序算法的Java代码实现如下。
查看和下载源代码public void selectionSort(int[] array) {
// min用来寻找当前未排序数据中的最小元素的索引（index）。
// tmp用于进行交换操作的临时存储。
int min, tmp;
for (int i = 0; i < array.length; i++) {
min = i;
// 里层的for循环用于查找当前未排序数据的最小值索引。
// 注意查找起始位置的变化是基于i的。比如第一组比较是索引j和min的元素，两个索引值都由i决定。
// 也就是说随着排序的进行，剩下的未排序元素逐渐减少。
for (int j = i+1; j < array.length; j++) {
if (array[j] < array[min]) {
min = j;
}
}
// 如果最小元素已在未排序元素的开始位置，则不必交换位置；否则最小元素与起始位置元素交换位置。
if (min != i) {
tmp = array[min];
array[min] = array[i];
array[i] = tmp;
}
}
}
下面我们用选择排序算法排序下面的数组。注意比较和其他排序算法的区别。
[9, 3, 5, 8, 2, 4, 6, 7, 10, 1]
在下面的动图里，红色代表刚刚被移动位置的元素。
在时间复杂度方面，选择排序的交换次数较少，介于 到 之间。但是比较次数仍为 ，即 。所以选择排序的时间复杂度仍然是 。
下面是选择排序的动画小程序。小程序可接受随机生成的一组不重复的数据，或者用户输入的自定义数据。
4. 归并排序（Merge Sort）
不同于像冒泡排序这样基于交换操作的排序算法，归并排序是基于归并操作的。归并操作是将两个已排序的序列合并成一个已排序序列的操作。当使用归并排序算法排序一个乱序序列时，将该序列分（divide）为尽量等长的两个子序列，再将子序列进一步划分为两个等长的子序列。重复划分操作直至子序列只有一个元素从而使得该序列天然排序。然后再从只有一个元素的子序列开始合并（Merge）操作，直到所有序列合并完成。
归并排序是一个使用了分治法（Divide and Conquer）的算法。归并排序可以使用递归结构来实现。
- 递归归并排序算法（Merge Sort）
- 如果一个序列的长度为0或者1，则其已经排序。
- 否则将该乱序序列划分为两个基本等长的子序列（如果原序列有偶数个元素，则两个子序列等长；如果原序列元素个数为奇数，则一个子序列元素会比另一个子序列多一个）。
- 对每个子序列再进行合并排序。
- 使用合并操作来合并子序列直到仅剩一个序列。
从以上给出的算法可知，合并操作是归并排序中的关键操作。下面我们给出一个合并操作的例子。假如有两个已排序的数组[20,32,33,62]和[5,48,50,72]，合并操作的步骤如下图所示。
该动图表示的算法如下（注意此处是合并操作而不是完整的归并排序）。
- 合并操作算法（Merge）
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
- 设定两个引用，初始位置分别为两个子序列的起始位置。
- 比较两个引用所指向的元素，选择相对小的元素放入到合并空间，并移动引用到下一个位置。
- 重复步骤3直到某一引用到达序列尾部。
- 将另一序列剩下的所有元素直接复制到合并序列尾部。
归并排序的代码如下。我们使用了两个函数mergeSort和mergeSortRecursive。用户调用算法时只需要使用mergeSort。
查看和下载源代码void mergeSortRecursive(int[] array, int[] result, int start, int end) {
// 如果当前序列为空或者只有一个元素则返回。因为此时序列时天然排好序的。
if (start >= end) {
return;
}
// 将当前序列划分成基本相等的两部分，通过当前数组的起始位置和结束位置来计算划分点的位置。
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
// 对划分开的两个序列递归调用mergeSortRecursive方法。
mergeSortRecursive(array, result, start1, end1);
mergeSortRecursive(array, result, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) {
// 将比较位置中较小的元素写入合并序列的下一个位置
result[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
}
// 如果一个子序列的所有元素都已写入合并序列，则将另一个子序列中剩下的所有元素按顺序写入合并序列。
while (start1 <= end1)
result[k++] = array[start1++];
while (start2 <= end2)
result[k++] = array[start2++];
// 将合并序列中的元素按顺序写入原始序列，此时原始序列排序完成。
for (k = start; k <= end; k++)
array[k] = result[k];
}
public void mergeSort(int[] array) {
int len = array.length;
int[] result = new int[len];
mergeSortRecursive(array, result, 0, len - 1);
}
下面的动图给出了使用归并排序算法来排序[32,62,33,20,72,5,48,50]的完整步骤。
归并排序的时间复杂度为 。所以归并排序在时间复杂度上小于冒泡排序，插入排序和选择排序。但是归并排序需要占用一份额外的完整序列长度的空间，所以归并排序牺牲了内存空间来获得性能的提升。
5. 快速排序（Quick Sort）
快速排序也是一种基于分治法的排序算法。快速排序使用从序列中挑选出的基准元素（pivot）来划分数列。将所有小于pivot的元素移到pivot之前，所有大于pivot的元素移到pivot之后。该操作完成后pivot已经挪到了它的最终位置。然后在针对pivot之前和之后的两个子序列分别再选出各自的pivot并递归地进行此操作。每次操作都有一个pivot移动到最终的排序位置上。最终，所有的元素都完成排序。
- 快速排序算法
- 从序列中挑出一个元素，称为“基准”（pivot）。
- 将所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面。在这个分割结束之后，对基准值的排序就已经完成了，即基准值pivot已经在其应该在的排序位置上了。
- 递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
下面的动图给出了对下面的数组进行快速排序的第一个步骤，即选取基准元素步骤，并将大于基准的元素移到基准右边，小于基准的元素移到左边。在这个例子中，选取了第一个元素（即40）作为基准元素。
[40, 20, 10, 80, 60, 50, 7, 30, 100, 90, 70]
下面的代码是递归版本的快速排序算法，可以对比上面的动图进行理解。
查看和下载源代码void quickSortRecursive(int[] array, int head, int tail) {
// 当数列为空，或者仅有一个元素时直接返回。
if (head >= tail || array == null || array.length <= 1) {
return;
}
// 基准pivot有许多种选择方法，为了简明，我们静态地选择当前数列的第一个元素作为基准。
int i = head+1, j = tail, pivot = array[head];
while (i <= j) {
// 索引i从左向右查找。
while (i <=j && array[i] < pivot) {
++i;
}
// 索引j从右向左查找。
while (i <=j && array[j] > pivot) {
--j;
}
if (i < j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
++i;
--j;
} else if (i == j) {
++i;
} else if (i > j) {
int tmp = array[head];
array[head] = array[j];
array[j] = tmp;;
}
}
quickSortRecursive(array, head, j);
quickSortRecursive(array, i, tail);
}
下面我们用快速排序算法排序这个数组。
[9, 3, 5, 8, 2, 4, 6, 7, 10, 1]
下面的动图显示了完整的步骤。第一轮选择当前数列的第一个元素9为基准元素，所以，经过移动我们可以看到，9的右边只有10，9的左边则是一组所有元素值都小于9的乱序数列。此时9已经处于其最终的排序位置上了。然后再对9左右两边的子序列重复进行相同的步骤，直到所有元素都到达最终位置，排序完成。
快速排序的时间复杂度为 。所以快速排序在时间复杂度上也小于冒泡排序，插入排序和选择排序。快速排序是一种广泛应用的排序算法，其性能还可以进一步优化。比如可以优化基准的选择算法，使得每次选择的基准值都能尽量的平分当前序列。
下面是快速排序的动画小程序。小程序可接受随机生成的一组不重复的数据，或者用户输入的自定义数据。
6. 堆排序（Heap Sort）
前面学习了最小堆和最大堆的概念。堆结构应用非常广泛。在排序算法中，堆排序也是一种高效的排序算法。
因为我们学习过堆，所以介绍堆排序的算法就变得非常简单。如果使用堆排序对一个数组进行排序，堆排序的算法如下。
- 堆排序算法
- 将该序列调整为最大堆。
- 取出堆顶元素（即最大元素，也就是位于数组最前面的元素）。
- 将数组最后一个元素移至堆顶。
- 重复1-3步直到堆为空。
从堆顶取出元素的顺序即为降序顺序。
下面的代码给出了堆排序的算法。
查看和下载源代码public void heapSort(int array[]) {
int n = array.length;
// i<= n/2-1.原因在于这些位置都是没有子节点的叶节点。
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// 将堆顶元素（即最大元素，位于数组最前面）与数组最后一个元素交换位置，该位置即该元素排序后应在的位置，
// 然后将堆的大小减1。下一轮的heapify调整堆时不会将最后一个元素包括在内。
for (int i=n-1; i>=0; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
heapify(array, i, 0);
}
}
在上面堆排序的算法中，我们也提到了最大堆的调整算法（heapify）。该方法访问一个节点并将其所在的子树调整为最大堆。
void heapify(int array[], int n, int i) {
int largest = i; // 最大节点初始化为根节点。
int l = 2*i + 1; // 计算左子节点的数组索引值2*i + 1。
int r = 2*i + 2; // 计算右子节点的数组索引值2*i + 2。
// 如果左子节点大于根节点。
if (l < n && array[l] > array[largest])
largest = l;
// 如果右子节点大于根节点。
if (r < n && array[r] > array[largest])
largest = r;
// 如果最大值不是根节点。
if (largest != i) {
int swap = array[i];
array[i] = array[largest];
array[largest] = swap;
// 在子树中递归的调用heapify方法。
heapify(array, n, largest);
}
}
下面我们用堆排序算法排序这个数组。
[9, 3, 5, 8, 2, 4, 6, 7, 10, 1]
在动图中，我们可以看到该数组首先被调整成为一个最大堆。
[10, 9, 6, 8, 2, 4, 5, 7, 3, 1]
然后将堆顶元素（即最大元素）10与堆中最后一个元素1互换位置得到[1, 9, 6, 8, 2, 4, 5, 7, 3, 10]。 此时我们将10放到了它排序后应在的位置上，在剩下的排序过程中不需要挪动它的位置了。所以当下次调整最大堆的时候，我们只需要将剩下的部分[1, 9, 6, 8, 2, 4, 5, 7, 3]再调整为最大堆。
重复此操作，最大堆的部分会越来越少，已排序元素会越来越多，直到排序完成。
堆排序的平均时间复杂度为 。但是与归并排序不同的是，堆排序的所有操作都在原始数组之内完成，所以，堆排序没有增加额外的内存消耗。
下面是堆排序的动画小程序。小程序可接受随机生成的一组不重复的数据，或者用户输入的自定义数据。
上一章
下一章
注册用户登陆后可留言