算法-排序（上）
原创
概述
排序（Sorting）是将一组对象按照规定的次序重新排列的过程，排序往往是为检索服务的。
排序算法的稳定性：相同键值的两个记录在排序前后相对位置的变化情况。稳定性是排序算法本身的特性，与数据无关。
排序的分类：
- 内部排序（Internal Sorting）：待排序记录全部放在计算机内存中进行的排序过程。
- 外部排序（External Sorting）：待排序的记录数量很大，内存不能存储全部记录，需要对外存进行访问的排序过程。
排序算法的分类：交换排序、插入排序、选择排序、归并排序。
交换排序
基本思想：比较两个记录键值的大小，如果这两个记录键值的大小出现逆序，则交换这两个记录。
冒泡排序（Bubble Sorting）
基本思想：把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。
代码实现：
private static void sort(int[] array) {
int len = array.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 1; j < len - i; j++) {
if (array[j - 1] > array[j]) {
array[j] = array[j - 1] ^ array[j];
array[j - 1] = array[j] ^ array[j - 1];
array[j] = array[j] ^ array[j - 1];
}
}
}
}冒泡排序总共遍历"元素数量-1"轮，每轮都要遍历所有元素，所以平均时间复杂度是O(n²)。
冒泡排序的优化1
如上种情况，数列在第一轮排序后已经有序，那么剩下的几轮排序就可以不执行了。
代码可进行如下优化：
private static void sort(int[] array) {
int len = array.length;
for (int i = 0; i < len - 1; i++) {
// 有序标记
boolean isSorted = true;
for (int j = 1; j < len - i; j++) {
if (array[j - 1] > array[j]) {
array[j] = array[j - 1] ^ array[j];
array[j - 1] = array[j] ^ array[j - 1];
array[j] = array[j] ^ array[j - 1];
isSorted = false;
}
}
if (isSorted) {
return;
}
}
}冒泡排序的优化2
如上图，数列右边元素是有序的，可是每一轮还是要进行比较操作。这正是需要优化的地方。问题关键在于对数列有序区的界定。解决办法是在每一轮排序后，记录最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区。
代码可进行如下优化：
private static void sort(int[] array) {
int len = array.length;
//最后一次交换的位置
int lastExIndex = 0;
// 边界，每次比较到此为止
int exBorder = array.length;
for (int i = 0; i < len - 1; i++) {
boolean isSorted = true;
for (int j = 1; j < exBorder; j++) {
if (array[j - 1] > array[j]) {
array[j] = array[j - 1] ^ array[j];
array[j - 1] = array[j] ^ array[j - 1];
array[j] = array[j] ^ array[j - 1];
isSorted = false;
//更新为最后一次交换元素的位置
lastExIndex = j;
}
}
exBorder = lastExIndex;
if (isSorted) {
return;
}
}
}鸡尾酒排序（Cocktail Sorting）
鸡尾酒排序又称双向冒泡排序，元素的比较和交换过程是双向的。排序的过程就像钟摆一样，第1轮从左到右，第2轮从右到左，第3轮再从左到右。。。。如下图所示：
代码实现如下：
private static void sort(int[] array) {
int len = array.length;
for (int i = 0; i < len / 2; i++) {
boolean isSorted = true;
//从左向右比较和交换
for (int j = i; j < len - i - 1; j++) {
if (array[j] > array[j + 1]) {
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
isSorted = false;
}
}
if (isSorted) {
return;
}
isSorted = true;
//从右向左比较和交换
for (int j = len - i - 2; j > i; j--) {
if (array[j] < array[j - 1]) {
array[j] = array[j] ^ array[j - 1];
array[j - 1] = array[j] ^ array[j - 1];
array[j] = array[j] ^ array[j - 1];
isSorted = false;
}
}
if (isSorted) {
return;
}
}
}鸡尾酒排序能够在特定条件下，减少排序的回合数，以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问两次（左右各一次 ）序列就可以完成排序，但如果使用冒泡排序则需要四次。
快速排序（Quick Sorting）
快速排序是从冒泡排序演变而来的，同冒泡排序一样，快速排序也属于交换排序。
冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序是在每一轮中挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移到数列的另一边，从而把数列拆解成两个总分。
大致流程如下：
这种思路叫分治法，原数列在每一轮都被拆分成两部分，每一部分在下一轮又被拆分成部分，直到不可两分为止。
基准元素，英文是pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。
代码实现的方式有两种：
- 双边循环法
- 单边循环法
双边循环法
基本思想：是从数组的两边交替遍历。过程下图所示：
代码实现：
public static void main(String[] args) {
int[] array = {4, 3, 6, 9, 8, 1, 2, 5};
sort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
/**
* 双指针法
*/
private static void sort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int divideIndex = quickPartition(array, left, right);
sort(array, left, divideIndex - 1);
sort(array, divideIndex + 1, right);
}
private static int quickPartition(int[] array, int left, int right) {
//基准值(选择左边第一个元素)
int pivot = array[left];
while (left < right) {
// 从右边第一个元素开始与基准值比较
while ((left < right) && (array[right] >= pivot)) {
right--;
}
array[left] = array[right];
while ((left < right) && (array[left] <= pivot)) {
left++;
}
array[right] = array[left];
}
array[left] = pivot;
return left;
}可以用一棵二叉树表示算法的执行过程，以数列{4,3,6,9,8,1,2,5}为例，如下图所示
递归调用的顺序是 -->sort(0,7)-->sort(0,2)-->sort(0,0)-->sort(2,2)-->sort(4,7)-->sort(4,5)-->sort(4,3)-->sort(5,5)-->sort(7,7)。可以看出该算法的执行过程实质是对应二叉树的先序遍历过程。
单边循环法
基本思想：从数组的一边进行遍历和交换，具体过程如下图所示：
代码实现如下：
/**
* 单指针
*/
private static void sort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int divideIndex = quickPartition(array, left, right);
sort(array, left, divideIndex - 1);
sort(array, divideIndex + 1, right);
}
private static int quickPartition(int[] array, int left, int right) {
//基准值(选择左边第一个元素)
int pivot = array[left];
int mark = left;
for (int i = left; i <= right; i++) {
if (array[i] < pivot && ++mark <i) {
array[i] = array[i]^array[mark];
array[mark] = array[i]^array[mark];
array[i] = array[i] ^ array[mark];
}
}
array[left] = array[mark];
array[mark] = pivot;
return mark;
}通过上面所讲的实现方法中，我们了解到了 快速排序的递归过程类似一棵二叉树的遍历过程，二叉树的遍历是可以通过非递归的方式实现的。二叉树的遍历分成DFS（深度优先遍历）和BFS（广度优先遍历），DFS的非递归遍历是通过栈实现的，BFS是借助队列实现。下面我们分别通过栈和队列实现快速排序。
栈非递归实现
private static void sortByStack(int[] array) {
Stack<Range> stack = new Stack<>();
stack.push(new Range(0, array.length - 1));
while (!stack.empty()) {
Range range = stack.pop();
int left = range.getLeft();
int right = range.getRight();
if (left < right) {
int divideIndex = quickPartition(array, left, right);
stack.push(new Range(divideIndex + 1, right));
stack.push(new Range(left, divideIndex - 1));
}
}
}
/**
* 单边循环
*/
private static int quickPartition(int[] array, int left, int right) {
//基准值(选择左边第一个元素)
int pivot = array[left];
int mark = left;
for (int i = left; i <= right; i++) {
if (array[i] < pivot && ++mark < i) {
array[i] = array[i] ^ array[mark];
array[mark] = array[i] ^ array[mark];
array[i] = array[i] ^ array[mark];
}
}
array[left] = array[mark];
array[mark] = pivot;
return mark;
}
public static class Range {
private final int left;
private final int right;
public Range(int left, int right) {
this.left = left;
this.right = right;
}
public int getLeft() {
return left;
}
public int getRight() {
return right;
}
}队列的非递归实现
private static void sortByQueue(int[] array) {
Queue<Range> queue = new LinkedList<>();
queue.offer(new Range(0, array.length - 1));
while (!queue.isEmpty()) {
Range range = queue.poll();
int left = range.getLeft();
int right = range.getRight();
if (left < right) {
int divideIndex = quickPartition(array, left, right);
queue.offer(new Range(divideIndex + 1, right));
queue.offer(new Range(left, divideIndex - 1));
}
}
}
/**
* 单边循环
*/
private static int quickPartition(int[] array, int left, int right) {
//基准值(选择左边第一个元素)
int pivot = array[left];
int mark = left;
for (int i = left; i <= right; i++) {
if (array[i] < pivot && ++mark < i) {
array[i] = array[i] ^ array[mark];
array[mark] = array[i] ^ array[mark];
array[i] = array[i] ^ array[mark];
}
}
array[left] = array[mark];
array[mark] = pivot;
return mark;
}
public static class Range {
private final int left;
private final int right;
public Range(int left, int right) {
this.left = left;
this.right = right;
}
public int getLeft() {
return left;
}
public int getRight() {
return right;
}
}基准元素的选择
上面快速排序实现中，我们都是选择数列中第1个元素为基准元素，这种情况在大多数情况是没有问题的。但是，
假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现如下情况：
如上，整个数列没有被分成两半，在这种情况下，待排序的数列中第1个元素要么是最小值，要么是最大值，根本无法发挥分治法的优势。快速排序的时间复杂度退化为O(n²)。
如何规避这种情况发生呢？
我们可以随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置。
复杂度分析
通过上面的分析，我们可知空间复杂度是O(logn)，平均时间复杂度是O(nlogn)，最坏时间复杂度是O(n²)。
双轴快速排序（DualPivot Quicksort）
双轴快速排序是俄罗斯程序员Vladimir Yaroslavskiy 在2009年开发出来的一种排序算法，与上面所讲的传统快排不同的是，它有两个基准值。
双轴快速排序的执行过程，我们引用原始论文 文中介绍：
P1、P2为选择的两个pivot轴，其指针位置用left和right变量表示。我们再定义三个指针L、K和G，其中位置见下图。三个指针区分出了四个分区。算法步骤如下：
- 选择两个轴元素P1、P2。例如图中选择第一个元素aleft =P1，最后一个元素aright=P2。
- 限定P1<P2（ 如果不是，则交换P1、P2）。这样我们就可以分出如下部分：Parit I left,L-1为<P1部分，Part II L,K-1为>=P1且<=P2部分，PartIII G+1,right-1为>P2部分，Part IVK,G为还没有确定的部分。
- 针对当前Part IV中的aK，与P1和P2比较，比较后放入Part I II III 中的一个。
- 调整L、K、G到适合的位置。
- 重复4、5步直到K>G。也就是说PartIV的元素全部分散到Part I II III中，最后是三个Part。
- 将P1放入Part I的最后一个位置，P2放入Part III的前一个位置（或者第一个位置）。这样就确定了P1和P2的位置。
- 对于PartI II III ，重复1-6步。
代码实现如下：
private static void sort(int[] arr, int start, int end) {
if (start > end) {
return;
}
if (arr[start] > arr[end]) {
swap(arr, start, end);
}
//储存最左侧和最右侧的值
int pivot1 = arr[start];
int pivot2 = arr[end];
//(start，left]:左侧小于等于pivot1 [right,end)大于pivot2
int left = start;
int right = end;
int m = left + 1;
while (m < right) {
if (arr[m] < pivot1) {
//和左侧交换
swap(arr, ++left, m++);
} else if (arr[m] <= pivot2) {
//在中间的情况
m++;
} else {
//如果全部大于pivot2直接跳出外层循环
while (arr[--right] > pivot2) {
if (right == m)
break;
}
if (m >= right) {
break;
}
swap(arr, m, right);
}
}
swap(arr, start, left);
swap(arr, end, right);
sort(arr, start, left - 1);
sort(arr, left + 1, right - 1);
sort(arr, right + 1, end);
}
private static void swap(int[] array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}下面我用图例来演示上面代码的执行过程：
从上可知双轴快速排序的时间复杂度与传统的快速排序是一样的。但实际执行的时候的双轴快速排序会更快，关于这个问题有一篇论文 Why Is Dual-Pivot Quicksort Fast? 作出了解释
论文中提到：
对比经典快速排序，双轴快速排序算法使用了更多的比较和指令，那么它在实践中怎么会更快？即理论和实际是有差异的！原因很可能与一种被称为“内存墙”或“冯.诺依曼瓶颈”的现象有关：长期以来，处理速度的增长速度远远以快于内存带宽。
关于“内存墙”，论文是这样描述的：
CPU速度在过去25年中以46%的平均年增长率增长，而内存带宽，即在给定时间内RAM和CPU之间可传输的数据量，每年增长37%。
如果CPU和内存传输速度之间的不平衡继续呈指数级增长，那么在将来的某个时候，CPU的任何进一步改进都将是徒劳的：处理器一直在等待数据；我们撞上了“内存墙”。
因此，论文作者提到我们在排序时不因仅考虑CPU的速度，还应考虑内存的速度，CPU和内存是否匹配等影响。
同时给出了另一种比较排序算法优劣的方法：扫描元素个数。
对于数组中一个元素的访问arrayi称为一次扫描。但是对于同一个下标，并且对应的值也不变的话，即使访问多次也只算一次，不管这个访问是读还是写。
为什么只算一次呢？由于有CPU高速缓存存在，再次访问数组同一下标的元素不需要访问内存，因此比访问一个新的下标元素时间少很多。
因此统计CPU与内存之间的数据流量大小也就把这个比较慢的内存因素考虑进去了。
扫描的元素与缓存未命中相关:
经典快速排序的一个分区步骤只扫描一次，结果是扫描了n个元素。在双轴快速排序的分区中，索引k和g一起扫描一次，但是索引ℓ 第二次扫描最左边的段。平均而言，后者包含所有元素的三分之一，产生4/3n扫描元素总数。Java 7快速排序（双轴快速排序）比Java 6版本（经典快速排序）节省了12%的元素扫描。
结论
关于交换排序的算法的内容就聊到这里，本文介绍了几种交换排序的实现原理及特点。
其中比较难理解的快速排序，在JAVA源代码中DualPivotQuicksort类有相关实现，这个类由Vladimir Yaroslavskiy, Jon Bentley, Josh Bloch编写，是一个高效的排序算法，里面不仅用到快排，还有插入排序、归并排序、计数排序。
参考资料
Why Is Dual-Pivot Quicksort Fast?
Dual-Pivot Quicksort algorithm
《算法(第4版)》作者: 美 Robert Sedgewick / 美 Kevin Wayne
《漫画算法》作者: 魏梦舒
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
