由于几乎所有的排序都会用到两个元素的交换，所以将交换方法放在这里，每个排序算法中直接使用：
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
冒泡排序
基本思想：
每一次排序要做的就是通过两两比较，小的放在前面，结果是最小的数放在本次排序的无序数的最前面。
如第一次排序：从最后一个元素开始，让最后一个元素和倒数第二个元素比较，小的放前面；再让倒数第二个元素和倒数第三个元素比较，小的放前面；.....直到第二个与第一个元素比较，小的放前面。这样就把最小的放在第一个位置了。
Java代码实现：
public static void bubbleSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i=0; i<arr.length-1; i++) {
for(int j=arr.length-1; j>i; j--) {
if(arr[j] < arr[j-1])
swap(arr, j-1, j);
}
}
}
改进：
改进基于上述算法中出现的这样一种情况：在某次排序中，没有发生数据交换。这种情况说明数据已经完全排序，无需再继续判断。
public static void bubbleSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
boolean flag = true;//flag表示是否发生数据交换
for(int i=0; i<arr.length-1 && flag ; i++) {
flag = false;//每次排序时设置为false
for(int j=arr.length-1; j>i; j--) {
if(arr[j] < arr[j-1]) {
swap(arr, j-1, j);
flag = true; //如果发生了数据交换，再设置为true
}
}
}
}
简单选择排序
基本思想：每一次排序都选出最小的那个，放在已经排好序的序列的后面。
如第一次排序，在所有的数中选出最小的，放在第一个位置；第二次排序，选出第2个数开始的所有数的最小的，放在第二个位置...
public static void selectSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int minIndex;//用来记录每次排序中最小的那个数的下标
for(int i=0; i<arr.length-1; i++) { //只需要比较n-1次
minIndex = i;
for(int j=i+1; j<arr.length; j++) { //从i+1开始比较
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) { //如果minIndex不为i，说明找到了更小的值。
swap(arr, i, minIndex);
}
}
}
直接插入排序
直接插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。与打牌时抓牌的时候类似：拿到一张牌，找到一个合适的位置插入。
实现思路：假设第一个已经排好（只有一个数，肯定是排好的）；在第i次排序中，只关心如何将第i+1个数（待插入的数，记为target）插入到这个数之前的已经排好序的序列中，这个数之后的元素不考虑。如何插入：让target依次向前比较，如果被比较的元素比target大，就让这个被比较的元素右移一个位置，直到被比较的元素比target小，比较结束，将target插在空出的这个位置上。
public static void insertSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
//假设第一个数位置是正确的，所以从i=1开始
for(int i=1; i<arr.length; i++) {
int target = arr[i]; //待插入的数
int j = i;//这个j就是最终找到的要插入的位置
//后移
while(j > 0 && target < arr[j-1]) {
arr[j] = arr[j-1];
j --;
}
//插入
arr[j] = target;
}
}
快速排序
在实际应用当中快速排序确实也是表现最好的排序算法。快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。
实现思路（冒泡+二分+递归分治）：
选择第一个数p为基准数，小于p的数放在左边，大于p的数放在右边。
递归的将p左边和右边的数都按照第一步进行，直到不能递归。
public static void sort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
quickSort(arr, 0, arr.length-1);
}
//分治+递归
private static void quickSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int baseIndex = partition(arr, left, right);
quickSort(arr, left, baseIndex-1);
quickSort(arr, baseIndex+1, right);
}
//一次排序中完成的工作：从右边找出比基准数小的，从左边找到比基准数大的，交换
private static int partition(int[] arr, int left, int right) {
int base = arr[left];
int baseIndex = left;
//右指针从右边寻找比基准数小的数，左指针从左边寻找比基准数大的数，找到后，交换；下次循环的时候，从上次指针到达的位置开始；
while(left < right) {//这里会直到left=right的时候停止
//先从右边开始，找出右边比基准数小的
while(left < right && arr[right] >= base)
right --;
//找到左边比基准数大的
while(left < right && arr[left] <= base)
left ++;
swap(arr, left, right); //把大的交换到右边，把小的交换到左边。
}
swap(arr, baseIndex, left); //最后把baseIndex交换到中间
return left;
}
希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
每次排序，将相距某个增量（步长）的数组成一个子序列，各个子序列进行直接插入排序。假如步长为3，则分为三个序列，第1个序列中的数应该是下标为（0，3，6...）的数，第2个序列中的数应该是下标为（1，4，7...）的数，第三个序列中的数应该是下标为（2，5，8...）的数，这三个序列用直接插入法排好序之后，再按照第1个序列、第2个序列、第3个序列的顺序将三个序列重新组成数组；完成一次排序后，让步长=原步长/3 + 1，循环上个步骤，直到步长=1。初始值为数组长度除3加1。[步长为什么这么变？...据说这样比较好]
public static void shellSort(int[] array) {
if (array == null || array.length == 0)
return;
int length = array.length;
int gap = length;
//最外层的循环是每次取不同步长时的循环，直到循环完最后一次：步长=1
//循环体内实现的是根据步长进行分组，并对每组进行直接插入排序，最后组成新数组
do {
//计算本次循环时步长应该是多少
gap = gap / 3 + 1;
//对于每个序列中的元素，下标为k的元素的前一个和后一个元素的下标为k-gap,k+gap
//步长为gap，则子序列个数为gap,每个子序列中的元素个数为：最少n/gap，最多为n/gap+1
/*、
*
*
* 这里的思路是对每个分组分别进行简单插入排序
*for(int i = 0; i < gap; i++){//对每个子序列进行简单插入排序
* for(int m = i + gap; m < length; m += gap){
* int target = array[m];
* int n = m;
* while(n > i && target < array[n-gap]){
* array[n] = array[n-gap];
* n -= gap;
* }
* array[n] = target;
* }
*}
*
*/
//这里的思路是将各个子序列的排序穿插进行
for (int i = gap; i < length; i++) {
int target = array[i];//待插入的数
int j = i;//记录最终插入的位置，开始设为原位置
while (j > i - gap && target < array[j - gap]) {//循环向左寻找插入位置，并将比target大的右移。
array[j] = array[j - gap];//左移，与简单插入排序不同的是，这里移动的距离是gap
j -= gap;
}
array[j] = target;//插入
}
}
while (gap > 1);
}
/**
* 维基上给出的算法
*
* @param arr
*/
public static void shell_sort(int[] arr) {
int gap = 1, i, j, len = arr.length;
int temp;
while (gap < len / 3)
gap = gap * 3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
for (; gap > 0; gap /= 3)
for (i = gap; i < len; i++) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}
堆排序
常见排序算法 - 堆排序 (Heap Sort)以及堆排序原理及算法实现（最大堆）讲的非常清楚，推荐阅读。
首先要明白堆的含义：
堆是具有下列性质的完全二叉树：每个节点的值都大于等于其左右子节点的值，称为大顶推；或者每个节点的值都小于等于其左右子节点的值，称为小顶堆。
如果按照层序遍历的方式对堆中节点进行编号，则对于编号为i的节点来说：
左子节点的编号为2i+1
右子节点的编号为2i+1
父节点的编号为floor((i-1)/2)
堆排序是指利用堆这种数据结构所设计的一种排序算法：将待排序的序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根节点。取走这个堆的根节点（其实是将其与堆数组的末尾元素交换），将剩余的n-1个序列重新构造成一个大顶堆，再次将堆顶元素取出，直到堆只有一个根节点。
代码来自维基百科，略有改动。
public class HeapSort {
public static void heapSort(int[] array) {
/*
* 第一步：将数组堆化---建堆
*
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点（只含有一个节点的大顶堆）
*
* beginIndex = 第一个非叶子节点的位置。
* index大于beginIndex的都是叶子节点。
* 一直循环到array[0]
*/
int length = array.length;
int beginIndex = (length - 2) >> 1;
for (int i = beginIndex; i >= 0; i--) {
maxHeapify(array, i, length - 1);
}
/*
* 第二步：对堆化数据排序
*
* 当对初始数组进行建堆之后，
* 此时，数组中最大元素是array[0]，最尾部节点就是当前数组的最后一个元素。
* 交换这两个元素后，数组中最大元素已经排好成为数组的最后一个元素；
* 然后，断开堆的最尾部节点（初始数组中的最大元素），
* 这里的断开，在操作中的实现是：调整堆的时候，忽略该节点；
*
* 对剩下的元素重新建堆，此时仅仅需要调整堆顶节点即可，
* 因为其他节点在建堆的时候都满足了堆的特性。
*
* 直至未排序的堆长度为 0。
*/
for (int i = length - 1; i > 0; i--) {
Util.swap(array, 0, i);
//再次建堆：仅仅调整此时的堆顶节点即可
maxHeapify(array, 0, i - 1);
}
}
/**
* 调整索引为i处的数据，使其符合堆的特性。
* 调整思路为：
* 先找到array[i]的两个子节点中的较大的节点，比较array[i]与子节点中的较大者，
* 如果子节点中的较大者大于array[i]，则交换，否则结束；
* 如果发生了交换（假设是左子节点array[left]与array[i]交换），
* 则递归调整array[left]
* 从堆的结构来看，这个递归过程是自上而下的调整过程
*
* @param i 需要堆化处理的数据的索引
* @param array 未排序的堆（数组）的长度
*/
private static void maxHeapify(int[] array, int i, int unHeaplength) {
int left = (i << 1) + 1; // 左子节点位置
int right = (i << 1) + 2;// 右子节点位置
int maxChild = left; // array[i]的所有子节点中位置最大的，默认左子节点。
if (left > unHeaplength) return; // 左子节点索引超出计算范围，直接返回。
if (right <= unHeaplength && array[right] > array[left]) // 先判断左右子节点，哪个较大。
maxChild = right;
if (array[maxChild] > array[i]) {
Util.swap(array, maxChild, i);
//如果节点交换，则要继续堆化该节点
maxHeapify(array, maxChild, unHeaplength);
}
}
@Test
public void validate() {
for (int i = 0; i < 10000; i++) {
int[] array = Util.randomArray(1000, 0, 10000);
heapSort(array);
if (!Util.assertOrder(array)) {
System.out.print("排序出现错误");
}
}
System.out.print("排序没出现问题");
}
}
通过阅读代码，更能体会出为什么说堆排序是简单选择排序的优化：简单选择排序在一次排序后仅仅选出最大的元素，但对过程中元素的比较结果没有保存下来；而堆排序在一次排序后，不仅选出了最大元素，也保留了元素的大小关系，使得之后的排序中不必重复比较已知大小关系的两个元素。
归并排序
归并排序
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法效率为。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法的一个非常典型的应用，且各层分治递归可以同时进行。
分治法的思想：分治算法是一个解决复杂问题的好工具，它可以把问题分解成若干个子问题，把子问题逐个解决，再组合到一起形成大问题的答案。
迭代法
①申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
②设定两个指针，最初位置分别为两个已经排序序列的起始位置
③比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
④重复步骤3直到某一指针到达序列尾
⑤将另一序列剩下的所有元素直接复制到合并序列尾递归法（假设序列共有n个元素）：
①将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
②将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
③重复步骤2，直到所有元素排序完毕
代码来自维基百科，略有改动。
public class MergeSort {
static 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(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 static void mergeSort(int[] array) {
int length = array.length;
int[] result = new int[length];//申请空间，保存结果
mergeSortRecursive(array, result, 0, length - 1);
}
/**
* 有助于理解的一个小算法：
* 合并两个有序序列：假设均为从小到大的顺序
*
* @param a
* @param b
* @return
*/
public static int[] mergeArrays(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int m = 0, n = 0, i = 0;
while (m < a.length && n < b.length) {
result[i++] = a[m] <= b[n] ? a[m++] : b[n++];
}
while (m < a.length) {
result[i++] = a[m++];
}
while (n < b.length) {
result[i++] = b[n++];
}
return result;
}
@Test
public void validate() {
for (int i = 0; i < 10000; i++) {
int[] array = Util.randomArray(10, 0, 10000);
mergeSort(array);
if (!Util.assertOrder(array)) {
System.out.print("排序出现错误");
}
}
System.out.print("排序没出现问题");
}
//归并排序的迭代法实现
public static void merge_sort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
int block, start;
// 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
for(block = 1; block < len*2; block *= 2) {
for(start = 0; start <len; start += 2 * block) {
int low = start;
int mid = (start + block) < len ? (start + block) : len;
int high = (start + 2 * block) < len ? (start + 2 * block) : len;
//两个块的起始下标及结束下标
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
//开始对两个block进行归并排序
while (start1 < end1 && start2 < end2) {
result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while(start1 < end1) {
result[low++] = arr[start1++];
}
while(start2 < end2) {
result[low++] = arr[start2++];
}
}
int[] temp = arr;
arr = result;
result = temp;
}
result = arr;
}
}
基数排序
实现思路：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
对比及适用场景：
常用排序算法的性能分析及应用场景
