1 冒泡排序
每次循环都比拟前后两个元素的大小，如果前者大于后者，则将两者进行替换。这样做会将每次循环中最大的元素替换到开端，逐步造成有序汇合。将每次循环中的最大元素逐步由队首转移到队尾的过程形似“冒泡”过程，故因而得名。
一个优化冒泡排序的办法就是如果在一次循环的过程中没有产生替换，则能够立刻退出以后循环，因为此时曾经排好序了（也就是工夫复杂度最好状况下是的由来）。
public int[] bubbleSort(int[] array) { if (array == null || array.length < 2) { return array; } for (int i = 0; i < array.length - 1; i++) { boolean flag = false; for (int j = 0; j < array.length - 1 - 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]; flag = true; } } if (!flag) { break; } } return array;}2 抉择排序
每次循环都会找出以后循环中最小的元素，而后和此次循环中的队首元素进行替换。
public int[] selectSort(int[] array) { if (array == null || array.length < 2) { return array; } for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[minIndex]) { minIndex = j; } } if (minIndex > i) { array[i] = array[i] ^ array[minIndex]; array[minIndex] = array[i] ^ array[minIndex]; array[i] = array[i] ^ array[minIndex]; } } return array;}3 插入排序
插入排序的精华在于每次都会在先前排好序的子集合中插入下一个待排序的元素，每次都会判断待排序元素的上一个元素是否大于待排序元素，如果大于，则将元素右移，而后判断再上一个元素与待排序元素...以此类推。直到小于等于比拟元素时就是找到了该元素的插入地位。这里的等于条件放在哪里很重要，因为它是决定插入排序稳固与否的要害。
public int[] insertSort(int[] array) { if (array == null || array.length < 2) { return array; } for (int i = 1; i < array.length; i++) { int temp = array[i]; int j = i - 1; while (j >= 0 && array[j] > temp) { array[j + 1] = array[j]; j--; } array[j + 1] = temp; } return array;}4 希尔排序
希尔排序能够认为是插入排序的改良版本。首先依照初始增量来将数组分成多个组，每个组外部应用插入排序。而后放大增量来从新分组，组内再次应用插入排序...反复以上步骤，直到增量变为1的时候，这个时候整个数组就是一个分组，进行最初一次残缺的插入排序即可完结。
在排序开始时的增量较大，分组也会较多，然而每个分组中的数据较少，所以插入排序会很快。随着每一轮排序的进行，增量和分组数会逐步变小，每个分组中的数据会逐步变多。但因为之前曾经通过了多轮的分组排序，而此时的数组会趋近于一个有序的状态，所以这个时候的排序也是很快的。而对于数据较多且趋向于无序的数据来说，如果只是应用插入排序的话效率就并不高。所以总体来说，希尔排序的执行效率是要比插入排序高的。
希尔排序执行示意图：
具体的实现代码如下：
public int[] shellSort(int[] array) { if (array == null || array.length < 2) { return array; } int gap = array.length >>> 1; while (gap > 0) { for (int i = gap; i < array.length; i++) { int temp = array[i]; int j = i - gap; while (j >= 0 && array[j] > temp) { array[j + gap] = array[j]; j = j - gap; } array[j + gap] = temp; } gap >>>= 1; } return array;}5 堆排序
堆排序的过程是首先构建一个大顶堆，大顶堆首先是一棵齐全二叉树，其次它保障堆中某个节点的值总是不大于其父节点的值。
因为大顶堆中的最大元素必定是根节点，所以每次取出根节点即为以后大顶堆中的最大元素，取出后剩下的节点再从新构建大顶堆，再取出根节点，再从新构建…反复这个过程，直到数据都被取出，最初取出的后果即为排好序的后果。
public class MaxHeap { /** * 排序数组 */ private int[] nodeArray; /** * 数组的实在大小 */ private int size; private int parent(int index) { return (index - 1) >>> 1; } private int leftChild(int index) { return (index << 1) + 1; } private int rightChild(int index) { return (index << 1) + 2; } private void swap(int i, int j) { nodeArray[i] = nodeArray[i] ^ nodeArray[j]; nodeArray[j] = nodeArray[i] ^ nodeArray[j]; nodeArray[i] = nodeArray[i] ^ nodeArray[j]; } private void siftUp(int index) { //如果index处节点的值大于其父节点的值，则替换两个节点值，同时将index指向其父节点，持续向上循环判断 while (index > 0 && nodeArray[index] > nodeArray[parent(index)]) { swap(index, parent(index)); index = parent(index); } } private void siftDown(int index) { //左孩子的索引比size小，意味着索引index处的节点有左孩子，证实此时index节点不是叶子节点 while (leftChild(index) < size) { //maxIndex记录的是index节点左右孩子中最大值的索引 int maxIndex = leftChild(index); //右孩子的索引小于size意味着index节点含有右孩子 if (rightChild(index) < size && nodeArray[rightChild(index)] > nodeArray[maxIndex]) { maxIndex = rightChild(index); } //如果index节点值比左右孩子值都大，则终止循环 if (nodeArray[index] >= nodeArray[maxIndex]) { break; } //否则进行替换，将index指向其替换的左孩子或右孩子，持续向下循环，直到叶子节点 swap(index, maxIndex); index = maxIndex; } } private void add(int value) { nodeArray[size] = value; size++; //构建大顶堆 siftUp(size - 1); } private void extractMax() { //将堆顶元素和最初一个元素进行替换 swap(0, size - 1); //此时并没有删除元素，而只是将size-1，剩下的元素从新构建成大顶堆 size--; //从新构建大顶堆 siftDown(0); } public int[] heapSort(int[] array) { if (array == null || array.length < 2) { return array; } nodeArray = new int[array.length]; for (int value : array) { add(value); } for (int i = 0; i < array.length; i++) { extractMax(); } return nodeArray; }}下面的经典实现中，如果须要变动节点时，都会来一次父子节点的互相交换操作（包含删除节点时首先做的要删除节点和最初一个节点之间的替换操作也是如此）。如果认真思考的话，就会发现这其实是多余的。在须要替换节点的时候，只须要siftUp操作时的父节点或siftDown时的孩子节点从新移到以后须要比拟的节点地位上，而比拟节点是不须要挪动到它们的地位上的。此时间接进入到下一次的判断中，反复siftUp或siftDown过程，直到最初找到了比拟节点的插入地位后，才会将其插入进去。这样做的益处是能够省去一半的节点赋值的操作，进步了执行的效率。同时这也就意味着，须要将要比拟的节点作为参数保存起来，而在ScheduledThreadPoolExecutor源码中也正是这么实现的（《较真儿学源码系列-ScheduledThreadPoolExecutor（逐行源码带你剖析作者思路）》）。
6 归并排序
归并排序应用的是分治的思维，首先将数组一直拆分，直到最初拆分成两个元素的子数组，将这两个元素进行排序合并，再向上递归。一直反复这个拆分和合并的递归过程，最初失去的就是排好序的后果。
合并的过程是将两个指针指向两个子数组的首位元素，两个元素进行比拟，较小的插入到一个temp数组中，同时将该数组的指针右移一位，持续比拟该数组的第二个元素和另一个元素…反复这个过程。这样temp数组保留的便是这两个子数组排好序的后果。最初将temp数组复制回原数组的地位处即可。
public int[] mergeSort(int[] array) { if (array == null || array.length < 2) { return array; } return mergeSort(array, 0, array.length - 1);}private int[] mergeSort(int[] array, int left, int right) { if (left < right) { //这里没有抉择“(left + right) / 2”的形式，是为了避免数据溢出 int mid = left + ((right - left) >>> 1); // 拆分子数组 mergeSort(array, left, mid); mergeSort(array, mid + 1, right); // 对子数组进行合并 merge(array, left, mid, right); } return array;}private void merge(int[] array, int left, int mid, int right) { int[] temp = new int[right - left + 1]; // p1和p2为须要比照的两个数组的指针，k为寄存temp数组的指针 int p1 = left, p2 = mid + 1, k = 0; while (p1 <= mid && p2 <= right) { if (array[p1] <= array[p2]) { temp[k++] = array[p1++]; } else { temp[k++] = array[p2++]; } } // 把残余的数组间接放到temp数组中 while (p1 <= mid) { temp[k++] = array[p1++]; } while (p2 <= right) { temp[k++] = array[p2++]; } // 复制回原数组 for (int i = 0; i < temp.length; i++) { array[i + left] = temp[i]; }}7 疾速排序
疾速排序的外围是要有一个基准数据temp，个别取数组的第一个地位元素。而后须要有两个指针left和right，别离指向数组的第一个和最初一个元素。
首先从right开始，比拟right地位元素和基准数据。如果大于等于，则将right指针左移，比拟下一位元素；如果小于，就将right指针处数据赋给left指针处（此时left指针处数据已保留进temp中），left指针+1，之后开始比拟left指针处数据。
拿left地位元素和基准数据进行比拟。如果小于等于，则将left指针右移，比拟下一位元素；而如果大于就将left指针处数据赋给right指针处，right指针-1，之后开始比拟right指针处数据…反复这个过程。
直到left和right指针相等时，阐明这一次比拟过程实现。此时将先前寄存进temp中的基准数据赋值给以后left和right指针独特指向的地位处，即可实现这一次排序操作。
之后递归排序根底数据的左半局部和右半局部，递归的过程和下面讲述的过程是一样的，只不过数组范畴不再是原来的全副数组了，而是当初的左半局部或右半局部。当全副的递归过程完结后，最终后果即为排好序的后果。
疾速排序执行示意图：
正如下面所说的，个别取第一个元素作为基准数据，但如果以后数据为从大到小排列好的数据，而当初要按从小到大的顺序排列，则数据摊派不平均，工夫复杂度会进化为，而不是失常状况下的。此时采取一个优化伎俩，即取最右边、最左边和最两头的三个元素的两头值作为基准数据，以此来防止工夫复杂度为的状况呈现，当然也能够抉择更多的锚点或者随机抉择的形式来进行选取。
还有一个优化的办法是：像疾速排序、归并排序这样的简单排序办法在数据量大的状况下是比抉择排序、冒泡排序和插入排序的效率要高的，然而在数据量小的状况下反而要更慢。所以咱们能够选定一个阈值，这里抉择为47（和源码中应用的一样）。当须要排序的数据量小于47时走插入排序，大于47则走疾速排序。
private static final int THRESHOLD = 47;public int[] quickSort(int[] array) { if (array == null || array.length < 2) { return array; } return quickSort(array, 0, array.length - 1);}private int[] quickSort(int[] array, int start, int end) { // 如果以后须要排序的数据量小于等于THRESHOLD则走插入排序的逻辑，否则持续走疾速排序 if (end - start <= THRESHOLD - 1) { return insertSort(array); } // left和right指针别离指向array的第一个和最初一个元素 int left = start, right = end; /* 取最右边、最左边和最两头的三个元素的两头值作为基准数据，以此来尽量避免每次都取第一个值作为基准数据、 工夫复杂度可能进化为O(n^2)的状况呈现 */ int middleOf3Indexs = middleOf3Indexs(array, start, end); if (middleOf3Indexs != start) { swap(array, middleOf3Indexs, start); } // temp寄存的是array中须要比拟的基准数据 int temp = array[start]; while (left < right) { // 首先从right指针开始比拟，如果right指针地位处数据大于temp，则将right指针左移 while (left < right && array[right] >= temp) { right--; } // 如果找到一个right指针地位处数据小于temp，则将right指针处数据赋给left指针处 if (left < right) { array[left] = array[right]; left++; } // 而后从left指针开始比拟，如果left指针地位处数据小于temp，则将left指针右移 while (left < right && array[left] <= temp) { left++; } // 如果找到一个left指针地位处数据大于temp，则将left指针处数据赋给right指针处 if (left < right) { array[right] = array[left]; right--; } } // 当left和right指针相等时，此时循环跳出，将之前寄存的基准数据赋给以后两个指针独特指向的数据处 array[left] = temp; // 一次替换后，递归替换基准数据右边的数据 if (start < left - 1) { array = quickSort(array, start, left - 1); } // 之后递归替换基准数据左边的数据 if (right + 1 < end) { array = quickSort(array, right + 1, end); } return array;}private int middleOf3Indexs(int[] array, int start, int end) { int mid = start + ((end - start) >>> 1); if (array[start] < array[mid]) { if (array[mid] < array[end]) { return mid; } else { return array[start] < array[end] ? end : start; } } else { if (array[mid] > array[end]) { return mid; } else { return array[start] < array[end] ? start : end; } }}private void swap(int[] array, int i, int j) { array[i] = array[i] ^ array[j]; array[j] = array[i] ^ array[j]; array[i] = array[i] ^ array[j];}8 计数排序
以上的七种排序算法都是比拟排序，也就是基于元素之间的比拟来进行排序的。而上面将要介绍的三种排序算法是非比拟排序，首先是计数排序。
计数排序会创立一个长期的数组，外面寄存每个数呈现的次数。比方一个待排序的数组是[3, 3, 5, 2, 7, 4, 2]，那么这个长期数组中记录的数据就是[2, 2, 1, 1, 0, 1]。示意2呈现了两次、3呈现了两次、4呈现了一次、5呈现了一次、6呈现了零次、7呈现了一次。那么最初只须要遍历这个长期数组中的计数值就能够了。
public int[] countingSort(int[] array) { if (array == null || array.length < 2) { return array; } //记录待排序数组中的最大值 int max = array[0]; //记录待排序数组中的最小值 int min = array[0]; for (int i : array) { if (i > max) { max = i; } if (i < min) { min = i; } } int[] temp = new int[max - min + 1]; //记录每个数呈现的次数 for (int i : array) { temp[i - min]++; } int index = 0; for (int i = 0; i < temp.length; i++) { //当输入一个数之后，以后地位的计数就减一，直到减到0为止 while (temp[i]-- > 0) { array[index++] = i + min; } } return array;}从下面的实现中能够看到，计数排序仅适宜数据跨度不大的场景。如果最大值和最小值之间的差距比拟大，生成的长期数组就会比拟长。比如说一个数组是[2, 1, 3, 1000]，最小值是1，最大值是1000。那么就会生成一个长度为1000的长期数组，然而其中绝大部分的空间都是没有用的，所以这就会导致空间复杂度变得很高。
计数排序是稳固的排序算法，但在下面的实现中并没有体现出这一点，下面的实现没有保护雷同元素之间的先后顺序。所以须要做些变换：将长期数组中从第二个元素开始，每个元素都加上前一个元素的值。还是拿之前的[3, 3, 5, 2, 7, 4, 2]数组来举例。计完数后的长期数组为[2, 2, 1, 1, 0, 1]，此时做下面的变换，每个数都累加后面的一个数，后果为[2, 4, 5, 6, 6, 7]。这个时候长期数组的含意就不再是每个数呈现的次数了，此时记录的是每个数在最初排好序的数组中应该要寄存的地位+1（如果有反复的就记录最初一个）。对于下面的待排序数组来说，最初排好序的数组应该为[2, 2, 3, 3, 4, 5, 7]。也就是说，此时各个数最初一次呈现的索引位为：1, 3, 4, 5, 6，别离都+1后就是2, 4, 5, 6, 7，这不就是下面做过变换之后的数组吗？（没有呈现过的数字不论它）所以，此时从后往前遍历原数组中的每一个值，将其减去最小值后，找到其在变换后的长期数组中的索引，也就是找到了最初排好序的数组中的地位了。当然，每次找到长期数组中的索引后，这个地位的数须要-1。这样如果后续有反复的该数字的话，就会插入到以后地位的前一个地位了。由此也阐明了遍历必须是从后往前遍历，以此来保护雷同数字之间的先后顺序。
public int[] stableCountingSort(int[] array) { if (array == null || array.length < 2) { return array; } //记录待排序数组中的最大值 int max = array[0]; //记录待排序数组中的最小值 int min = array[0]; for (int i : array) { if (i > max) { max = i; } if (i < min) { min = i; } } int[] temp = new int[max - min + 1]; //记录每个数呈现的次数 for (int i : array) { temp[i - min]++; } //将temp数组进行转换，记录每个数在最初排好序的数组中应该要寄存的地位+1（如果有反复的就记录最初一个） for (int j = 1; j < temp.length; j++) { temp[j] += temp[j - 1]; } int[] sortedArray = new int[array.length]; //这里必须是从后往前遍历，以此来保障稳定性 for (int i = array.length - 1; i >= 0; i--) { sortedArray[temp[array[i] - min] - 1] = array[i]; temp[array[i] - min]--; } return sortedArray;}9 桶排序
下面的计数排序在数组最大值和最小值之间的差值是多少，就会生成一个多大的长期数组，也就是生成了一个这么多的桶，而每个桶中就只插入一个数据。如果差值比拟大的话，会比拟节约空间。那么我能不能在一个桶中插入多个数据呢？当然能够，而这就是桶排序的思路。桶排序相似于哈希表，通过肯定的映射规定将数组中的元素映射到不同的桶中，每个桶内进行外部排序，最初将每个桶按程序输入就行了。桶排序执行的高效与否和是否是稳固的取决于哈希散列的算法以及外部排序的后果。须要留神的是，这个映射算法并不是惯例的映射算法，要求是每个桶中的所有数都要比前一个桶中的所有数都要大。这样最初输入的才是一个排好序的后果。比如说第一个桶中存1-30的数字，第二个桶中存31-60的数字，第三个桶中存61-90的数字...以此类推。上面给出一种实现：
public int[] bucketSort(int[] array) { if (array == null || array.length < 2) { return array; } //记录待排序数组中的最大值 int max = array[0]; //记录待排序数组中的最小值 int min = array[0]; for (int i : array) { if (i > max) { max = i; } if (i < min) { min = i; } } //计算桶的数量（能够自定义实现） int bucketNumber = (max - min) / array.length + 1; List<Integer>[] buckets = new ArrayList[bucketNumber]; //计算每个桶存数的范畴（能够自定义实现或者不必实现） int bucketRange = (max - min + 1) / bucketNumber; for (int value : array) { //计算应该放到哪个桶中（能够自定义实现） int bucketIndex = (value - min) / (bucketRange + 1); //提早初始化 if (buckets[bucketIndex] == null) { buckets[bucketIndex] = new ArrayList<>(); } //放入指定的桶 buckets[bucketIndex].add(value); } int index = 0; for (List<Integer> bucket : buckets) { //对每个桶进行外部排序，我这里应用的是疾速排序，也能够应用别的排序算法，当然也能够持续递归去做桶排序 quickSort(bucket); if (bucket == null) { continue; } //将不为null的桶中的数据按程序写回到array数组中 for (Integer integer : bucket) { array[index++] = integer; } } return array;}10 基数排序
基数排序不是依据一个数的整体来进行排序的，而是将数的每一位上的数字进行排序。比如说第一轮排序，我拿到待排序数组中所有数个位上的数字来进行排序；第二轮排序我拿到待排序数组中所有数十位上的数字来进行排序；第三轮排序我拿到待排序数组中所有数百位上的数字来进行排序...以此类推。每一轮的排序都会累加上一轮所有前几位上排序的后果，最终的后果就会是一个有序的数列。
基数排序个别是对所有非负整数进行排序的，然而也能够有别的伎俩来去掉这种限度（比方都加一个固定的数或者都乘一个固定的数，排完序后再复原等等）。基数排序和桶排序很像，桶排序是按数值的区间进行划分，而基数排序是按数的位数进行划分。同时这两个排序都是须要依附其余排序算法来实现的（如果不算递归调用桶排序自身的话）。基数排序每一轮的外部排序会应用到计数排序来实现，因为每一位上的数字无非就是0-9，是一个小范畴的数，所以应用计数排序很适合。
基数排序执行示意图：
具体的实现代码如下：
public int[] radixSort(int[] array) { if (array == null || array.length < 2) { return array; } //记录待排序数组中的最大值 int max = array[0]; for (int i : array) { if (i > max) { max = i; } } //获取最大值的位数 int maxDigits = 0; while (max != 0) { max /= 10; maxDigits++; } //用来计数排序的长期数组 int[] temp = new int[10]; //用来寄存每轮排序后的后果 int[] sortedArray = new int[array.length]; for (int d = 1; d <= maxDigits; d++) { //每次循环开始前都要清空temp数组中的值 replaceArray(temp, null); //记录每个数呈现的次数 for (int a : array) { temp[getNumberFromDigit(a, d)]++; } //将temp数组进行转换，记录每个数在最初排好序的数组中应该要寄存的地位+1（如果有反复的就记录最初一个） for (int j = 1; j < temp.length; j++) { temp[j] += temp[j - 1]; } //这里必须是从后往前遍历，以此来保障稳定性 for (int i = array.length - 1; i >= 0; i--) { int index = getNumberFromDigit(array[i], d); sortedArray[temp[index] - 1] = array[i]; temp[index]--; } //一轮计数排序过后，将这次排好序的后果赋值给原数组 replaceArray(array, sortedArray); } return array;}private final static int[] sizeTable = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};/** * 获取指定位数上的数字是多少 */private int getNumberFromDigit(int number, int digit) { if (digit < 0) { return -1; } return (number / sizeTable[digit - 1]) % 10;}private void replaceArray(int[] originalArray, int[] replaceArray) { if (replaceArray == null) { for (int i = 0; i < originalArray.length; i++) { originalArray[i] = 0; } } else { for (int i = 0; i < originalArray.length; i++) { originalArray[i] = replaceArray[i]; } }}11 复杂度及稳定性
| 排序算法 | 工夫复杂度 | 空间复杂度 | 稳定性 | ||
|---|---|---|---|---|---|
| 均匀状况 | 最好状况 | 最坏状况 | |||
| 冒泡排序 | 稳固 | ||||
| 抉择排序 | 不稳固 | ||||
| 插入排序 | 稳固 | ||||
| 希尔排序 | 取决于增量的抉择 | 不稳固 | |||
| 堆排序 | 不稳固 | ||||
| 归并排序 | 稳固 | ||||
| 疾速排序 | 不稳固 | ||||
| 计数排序 | 稳固 | ||||
| 桶排序 | 取决于桶散列的后果和外部排序算法的工夫复杂度 | 稳固 | |||
| 基数排序 | 稳固 |
（其中：
- k示意计数排序中最大值和最小值之间的差值；
- l示意桶排序中桶的个数；
- d示意基数排序中最大值的位数，r示意是多少进制；
- 希尔排序的工夫复杂度很大水平上取决于增量gap sequence的抉择，不同的增量会有不同的工夫复杂度。文中应用的“gap=length/2”和“gap=gap/2”是一种罕用的形式，也被称为希尔增量，但其并不是最优的。其实希尔排序增量的抉择与证实始终都是个数学难题，而下图列出的是迄今为止大部分的gap sequence抉择的计划）
12 小彩蛋：猴子排序
在几十年的计算机科学倒退中，诞生了很多优良的算法，大家都在为了能开发出更高效的算法而致力。然而在这其中也诞生了一些仅供娱乐的搞笑算法，猴子排序就是其中的一种。
猴子排序的实现很简略，随机找出两个元素进行替换，直到随机替换到最初能正确排好序的时候才会进行。
public int[] bogoSort(int[] array) { if (array == null || array.length < 2) { return array; } Random random = new Random(); while (!inOrder(array)) { for (int i = 0; i < array.length; i++) { int swapPosition = random.nextInt(i + 1); if (swapPosition == i) { continue; } array[i] = array[i] ^ array[swapPosition]; array[swapPosition] = array[i] ^ array[swapPosition]; array[i] = array[i] ^ array[swapPosition]; } } return array;}private boolean inOrder(int[] array) { for (int i = 0; i < array.length - 1; i++) { if (array[i] > array[i + 1]) { return false; } } return true;}原创不易，未得准许，请勿转载，翻版必究