常用排序算法比较
在比较排序算法时，得先找一个标准比较，一般都使用时间复杂度和空间复杂度来衡量。
排序算法
根据排序过程中使用的存储器不同，排序算法分为 内部排序 和 外部排序 两大类。
内部排序指的是待排序记录存放在计算机随机存储器中进行的排序过程
外部排序指的在排序过程中尚需对外村进行访问的排序过程
/**
* 交换数组元素
*
* @param array
* @param i
* @param j
*/
public static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
/**
* 交换数组元素
* 用了一个巧妙的方法，不需要临时变量
* 不足之处，就是当数组中的arr[a]+arr[b]的值大于int的最大值时，计算结果会溢出。导致arr[a]和arr[b]的值错误。
* @param arr
* @param a
* @param b
*/
public static void swap(int[] arr, int a, int b){
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
/**
* 交换数组元素
*
* @param arr
* @param a
* @param b
*/
public void swap(int[] arr, int a, int b) {
arr[a] ^= arr[b];
arr[b] ^= arr[a];
arr[a] ^= arr[b];
}
一、 冒泡排序(Bubble Sort)
冒泡排序( Bubble Sort )是一种交换排序，基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
在最好的情况下，也就是数列本身是排好序的，需要进行 n - 1 次比较；在最坏的情况下，也就是数列本身是逆序的，需要进行 n(n-1)/2 次比较。因此冒泡排序总的时间复杂度是 O(n^2)。
最坏时间复杂度 O(n^{2}) 最优时间复杂度 O(n) 平均时间复杂度 O(n^{2})
空间复杂度 总共O(n)，需要辅助空间O(1)
/**
* 冒泡排序<br>
* 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到 数列 的顶端，故名。<br>
* <p>
* 冒泡排序最好的时间复杂度为O(n)，最坏时间复杂度为O(n^2)<br>
* 综上，因此冒泡排序总的平均时间复杂度为 O(n^2)
*
* References
* https://www.cnblogs.com/melon-h/archive/2012/09/20/2694941.html
*
* @author: weikeqin.cn@gmail.com
*/
public class BubbleSort {
/**
* 冒泡排序
*
* <pre>
*
* 在数列里把小的往上浮就相当于把小的往(数组)前放
*
* 基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整， 让较大的数往上浮，较小的往下。
* 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
*
* 在这个方法里(未改进)，冒泡排序最好的时间复杂度为O(n^2) 冒泡排序的最坏时间复杂度为O(n^2)
*
* 原理：假如有一个长度为n的数组，要循环n-1次 每次循环把最大值换到第一个位置
*
* 例子： 28276130 长度n=9;要循环8次
* 第一次循环完 变成 2 7 2 7 6 1 3 0 8
* 第二次循环完 变成 2 2 7 6 1 3 0 7 8
* 第三次循环完 变成 2 2 6 1 3 0 7 7 8
* 第四次循环完 变成 2 2 1 3 0 6 7 7 8
* 第五次循环完 变成 2 1 2 0 3 6 7 7 8
* 第六次循环完 变成 1 2 0 2 3 6 7 7 8
* 第七次循环完 变成 1 0 2 2 3 6 7 7 8
* 第八次循环完 变成 0 1 2 2 3 6 7 7 8
* </pre>
*
* @param array
*/
public static void bubbleSort(int[] array) {
int temp = 0;
//int count = 0;
int arrayLength = array.length;
// 比多少趟
int x = arrayLength - 1;
for (int i = 0; i < x; i++) {
// 一趟比多少次
int y = arrayLength - i - 1;
for (int j = 0; j < y; j++) {
// 相邻元素比较，小的往前放，大的往后放
if (array[j] > array[j + 1]) {
swap(array, j, j+1);
}
} // end for
print(array);
} // end for
} // end method
/**
* 交换数组元素
*
* @param array
* @param big
* @param small
*/
public static void swap(int[] array, int big, int small) {
int tmp = 0;
tmp = array[big];
array[big] = array[small];
array[small] = tmp;
}
/**
* 改进版的冒泡排序<br>
*
* 改进版的冒泡排序最好的时间复杂度为O(n) 冒泡排序的最坏时间复杂度为O(n^2)
*
* @param array
*/
public static void bubbleSortImprove(int[] array) {
int temp = 0;
int arrayLength = array.length;
// 比多少趟
int x = arrayLength - 1;
boolean didSwap = false;
for (int i = 0; i < x; i++) {
// 一趟比多少次
int y = arrayLength - i - 1;
for (int j = 0; j < y; j++) {
// 相邻元素比较，小的往前放，大的往后放
if (array[j] > array[j + 1]) {
swap(array, j, j+1);
didSwap = true;
}
} // end for
//print(array);
if(didSwap == false){
return;
}
} // end for
} // end method
/**
*
* @param array
*/
private static void print(int[] array) {
StringBuilder sb = new StringBuilder();
int length = array.length;
for (int i = 0; i < length; i++) {
sb.append(array[i]);
sb.append(" ");
}
System.out.println(sb.toString());
}
/**
*
* @param args
* @author weikeqin.cn@gmail.com
* @date 2018/6/2 15:35
*/
public static void main(String[] args) {
int[] a = null;
a = new int[]{2, 7, 8, 2, 7, 6, 1, 3, 0};
a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
a = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
// int count = 100000;
// a = new int[count];
// for(int i = 0; i < count; i++){
// // 倒序
// //a[i] = count - i;
// // 正序
// a[i] = i;
// }
System.out.println("---------------排序前--------------------");
print(a);
System.out.println("--------------开始排序--------------------");
long start = System.currentTimeMillis();
// 冒泡排序
bubbleSortImprove(a);
long end = System.currentTimeMillis();
System.out.println("共花费" + 1.0 * (end - start) / 1000 + "s");
System.out.println("---------------排序后---------------------");
print(a);
}
}
二、直接插入排序 (Straight Insertion Sort)
直接插入排序(Straight Insertion Sort)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
插入排序的时间复杂度为 O(n^2)，比冒泡法和选择排序的性能要更好一些，是稳定的排序方法，适用于数量较少的排序。
最坏时间复杂度 O(n^{2}) 最优时间复杂度 O(n) 平均时间复杂度 O(n^{2})
空间复杂度 总共 O(n)，需要辅助空间 O(1)
/**
* 直接插入排序 <br>
*
* References
* https://www.cnblogs.com/chengxiao/p/6103002.html
* https://www.cnblogs.com/skywang12345/p/3596881.html
*
* @author: weikeqin.cn@gmail.com
*/
public class StraightInsertionSort {
/**
* 直接插入排序<br>
*
* <pre>
* 基本思想： 把n个待排序的元素看成为一个有序表和一个无序表。
* 开始时有序表中只包含1个元素，无序表中包含有n-1个元素，
* 排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，
* 使之成为新的有序表，重复n-1次可完成排序过程。
*
* 数据 2 7 8 2 7 6 1 3 0
* 假设有序表里有一个元素，是数组的第一个元素，其他的元素在无序表里，逐个插入
* 插入时如果相等，要插入的元素放到当前元素的后面
*
* 第一次插入 2 7
* 第二次插入 2 7 8
* 第三次插入 2 2 7 8
* 第四次插入 2 2 7 7 8
* 第五次插入 2 2 6 7 7 8
* 第六次插入 1 2 2 6 7 7 8
* 第七次插入 1 2 2 3 6 7 7 8
* 第八次插入 0 1 2 2 3 6 7 7 8
*
* 最好情况要比较n-1次，最差情况要比较 n(n-1)/2
* 时间复杂度是 O(n^2)
*
* </pre>
*
* @param array
* @author weikeqin.cn@gmail.com
*/
public static int[] starightInsertionSort(int[] array) {
int length = array.length;
for (int i = 1; i < length; i++) {
int j = i;
// 把 选择数组下标 和 插入数据时元素后移 合二为一
while (j > 0 && array[j] < array[j - 1]) {
swap(array, j, j - 1);
j--;
}
}
return array;
}
/**
* 直接插入排序<br>
* 第一次自己实现的
*
* @param array
* @author weikeqin.cn@gmail.com
*/
public static int[] starightInsertionSortMy(int[] array) {
int length = array.length;
// 要插入的位置
int index = 0;
int tmp = 0;
// 以数组第一个元素作为有序表，其他元素作为无序表
// 最小的放前面，大的放后面，如果等于，等于的全部放到后面
for (int i = 1; i < length; i++) {
if (array[i] < array[i - 1]) {
System.out.println("第" + i + "个元素" + array[i] + "小于第" + (i - 1) + "个元素" + array[i - 1] + " 准备插入。");
// 寻找插入位置，从小到大找
if (array[i] < array[0]) {
index = 0;
} else {
for (int j = 0; j < i; j++) {
if (array[i] >= array[j] && array[i] < array[j + 1]) {
// 要插入到j+1个位置
index = j + 1;
}
}
}
System.out.println("第" + i + "个元素" + array[i] + "准备插入到第" + index + "个位置。");
System.out.println("第" + index + "个元素到第" + (i - 1) + "个元素全部往右移。");
tmp = array[i];
// 插入有序表对应位置，index位置及以后的全部后移
for (int k = i - 1; k >= index; k--) {
System.out.println("第" + k + "个元素" + array[k] + "移动到到第" + (k + 1) + "个位置。");
array[k + 1] = array[k];
}
array[index] = tmp;
} else {
// 如果 array[i] >= array[i-1]，array[i]插入到array[i-1]后面，也就是位置不变
System.out.println("第" + i + "个元素" + array[i] + "大于第" + (i - 1) + "个元素" + array[i - 1] + " 不用插入。");
}
// 打印当前数组
print(array);
}
return array;
}
/**
* 交换数组元素
*
* @param array
* @param a
* @param b
*/
public static void swapUseCpu(int[] array, int a, int b) {
array[a] = array[a] + array[b];
array[b] = array[a] - array[b];
array[a] = array[a] - array[b];
}
/**
* 交换数组元素
*
* @param array
* @param a
* @param b
*/
public static void swap(int[] array, int a, int b) {
int tmp = 0;
tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
/**
* @param array
*/
private static void print(int[] array) {
StringBuilder sb = new StringBuilder();
int length = array.length;
for (int i = 0; i < length; i++) {
sb.append(array[i]);
sb.append(" ");
}
System.out.println(sb.toString());
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a = null;
a = new int[]{2, 7, 8, 2, 7, 6, 1, 3, 0};
//a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
//a = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
System.out.println("---------------排序前--------------------");
print(a);
System.out.println("--------------开始排序--------------------");
a = starightInsertionSort(a);
System.out.println("---------------排序后---------------------");
print(a);
}
}
三、简单选择排序(Selection sort)
选择排序的基本思想是：每一趟在n-i+1 (i=1,2,3…,n-1)个记录中选择关键字最小的记录 作为有序序列中第i个记录。
简单选择排序：通过n-i次关键字之间的比较，从n-i+1 个记录中选择关键字最小的记录，并和第i(1<=i<=n)个记录交换之。
尽管时间复杂度与冒泡排序同为O(n^2),但简单选择排序的性能要略优于冒泡排序。
/**
* 简单选择排序
*
* https://www.cnblogs.com/chengxiao/p/6103002.html
*
* @author: weikeqin.cn@gmail.com
*/
public class SelectionSort {
/**
* 简单选择排序<br>
*
* <pre>
* 基本思想: 为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，
* 直到所有元素排完为止。
*
* 原始数据 2 7 8 2 7 6 1 3 0
* 第一次交换 0 7 8 2 7 6 1 3 2
* 第二次交换 0 1 8 2 7 6 7 3 2
* 第三次交换 0 1 2 8 7 6 7 3 2
* 第四次交换 0 1 2 2 7 6 7 3 8
* 第五次交换 0 1 2 2 3 6 7 7 8
* 第六次交换 0 1 2 2 3 6 7 7 8
* 第七次交换 0 1 2 2 3 6 7 7 8
* 第八次交换 0 1 2 2 3 6 7 7 8
* 第九次交换 0 1 2 2 3 6 7 7 8
*
* 无论数据如何排列，所需比较次数都为 n(n-1)/2
* 时间复杂度是O(n^2)
* 简单选择排序是不稳定排序。
*
* </pre>
*
* @author weikeqin.cn@gmail.com
*/
public static int[] selectionSort(int[] array){
int length = array.length;
int tmp = 0;
for(int i = 0; i < length; i++){
//
int index = selectMinKey(array, i, length);
System.out.println("数组下标："+index + " 对应元素："+array[index]);
// 交换值
if(i != index){
tmp = array[i];
array[i] = array[index];
array[index] = tmp;
}
print(array);
}
return array;
}
/**
* 选出数组给定范围最小值对应的数组下标
*
* @param array
* @param begin
* @param length
*/
public static int selectMinKey(int[] array, int begin, int length) {
int minKey = 0;
int index = 0;
boolean first = true;
for(int j = begin; j < length; j++){
if(first){
minKey = array[j];
index = j;
first = false;
}
if(array[j] < minKey){
minKey = array[j];
index = j;
}
}
return index;
}
/**
* @param array
*/
private static void print(int[] array) {
StringBuilder sb = new StringBuilder();
int length = array.length;
for (int i = 0; i < length; i++) {
sb.append(array[i]);
sb.append(" ");
}
System.out.println(sb.toString());
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a = null;
a = new int[]{2, 7, 8, 2, 7, 6, 1, 3, 0};
//a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
//a = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
System.out.println("---------------排序前--------------------");
print(a);
System.out.println("--------------开始排序--------------------");
a = selectionSort(a);
System.out.println("---------------排序后---------------------");
print(a);
}
}
四、希尔排序(Shell Sort)
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2)的第一批算法之一。
基本思想：先将整个待排元素序列分割成若干子序列(由相隔某个”增量”的元素组成的)分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序(增量为1)。
简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
当增量序列为 dlta[k] = (2^(t-k+1)) - 1 时，其时间复杂度为O(n^(3/2))，其中t为排序趟数， 1 <= k <= t < log2^(n+1)
当n在特定范围内，希尔排序所需的比较和移动次数约为n^1.3，当n -> 无穷， 可减少到n(log2^n)^(2^[2]) 。
最优时间复杂度: O(n) 最坏时间复杂度: 根据步长序列的不同而不同。 平均时间复杂度: 根据步长序列的不同而不同。
空间复杂度: O(n)
增量(步长)序列 最坏情况下复杂度
n/2^i O(n^2)
2^k - 1 O(n^(3/2))
2^i * 3^j O(nlog2^n)
/**
* 希尔排序
* <p>
* References
* https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
* http://www.cnblogs.com/chengxiao/p/6104371.html
* http://bubkoo.com/2014/01/15/sort-algorithm/shell-sort/
* https://blog.csdn.net/morewindows/article/details/6668714
*
* @author: weikeqin.cn@gmail.com
*/
public class ShellSort {
/**
* 希尔排序 针对有序序列在插入时采用交换法
* <pre>
*
* 基本思想：先将整个待排元素序列分割成若干子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序，
* 然后依次缩减增量再进行排序，待整个序列中的元素基本有序(增量足够小)时，
* 再对全体元素进行一次直接插入排序(增量为1)。
*
* 原始数据 2 7 8 2 7 6 1 3 0
* 第一趟排序结果 0 6 1 2 2 7 8 3 7
* 第二趟排序结果 0 1 2 2 3 6 7 7 8
*
* 在希尔排序时，先对数据进行分组，然后对每组的数据做插入排序，然后合并多组的数据
* 在代码实现时，对每组做插入排序要稍微转一下弯
*
* 希尔排序时增量(步长)选择是一个难题
* 当增量序列为 dlta[k] = (2^(t-k+1)) - 1 时，其时间复杂度为O(n^(3/2))，其中t为排序趟数， 1 <= k <= t < log2^(n+1)
* 当n在特定范围内，希尔排序所需的比较和移动次数约为n^1.3，当n -> 无穷， 可减少到n(log2^n)^(2^[2]) 。
*
* </pre>
*
* @param arr
* @author weikeqin.cn@gmail.com
*/
public static int[] shellSort(int[] arr) {
int gap = 1, i, j, len = arr.length;
int temp;
while (gap < len / 3) {
// <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
gap = gap * 3 + 1;
}
// 循环趟
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;
} // end for
print(arr);
} // end for
return arr;
}
/**
* @author weikeqin.cn@gmail.com
*/
public static int[] shellSort2(int[] arr) {
int i, j, gap, len = arr.length;
for (gap = len / 2; gap > 0; gap /= 2) {
for (i = gap; i < len; i++) {
for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) {
swap(arr, arr[j], arr[j + gap]);
}
}
}
return arr;
}
/**
* @author weikeqin.cn@gmail.com
*/
public static int[] shellSort3(int[] arr) {
int length = arr.length;
for (int gap = length / 2; gap > 0; gap /= 2) {
System.out.println("gap:" + gap);
// 每一趟相当于插入排序，把每组的小的往前放
// 这个i从gap开始的目的是为了避免后面数组越界异常
// i从0开始也可以，但是试了就会发现，从0 ~ (gap-1) 全部数组越界，还要跳过，相当于i从gap开始
for (int i = gap; i < length; i++) {
System.out.println("i:" + i);
int j = i;
// 可以把上面的for循环改成从0开始，发现 0 ~ (gap-1) 全部跳过
if (j - gap < 0) {
System.out.println("比较 第" + j + "个元素 与 第" + (j - gap) + "个元素 数组越界， 跳过");
continue;
}
System.out.println("比较 第" + j + "个元素 与 第" + (j - gap) + "个元素。");
while (j - gap >= 0 && arr[j] < arr[j - gap]) {
System.out.println("交换 第" + j + "个元素:" + arr[j] + " 与 第" + (j - gap) + "个元素:" + arr[j - gap]);
swap(arr, j, j - gap);
// 同一组迭代比较，目的是把最小的放到该组最前面
j -= gap;
print(arr);
}
}
System.out.println("----一趟排序完，打印数组----");
print(arr);
}
return arr;
}
/**
* 希尔排序 针对有序序列在插入时采用移动法。
*
* @param arr
*/
public static int[] shellSort4(int[] arr) {
int length = arr.length;
//增量gap，并逐步缩小增量
for (int gap = length / 2; gap > 0; gap /= 2) {
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for (int i = gap; i < length; i++) {
int j = i;
// 同一组的整体处理
int temp = arr[j];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
//移动法
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
} // end for
} // end for
return arr;
}
/**
* 交换数组元素
*
* @param arr
* @param a
* @param b
*/
public static void swap(int[] arr, int a, int b) {
int tmp = 0;
tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
/**
* 交换数组元素
*
* @param arr
* @param a
* @param b
*/
public static void swapUseCpu(int[] arr, int a, int b) {
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
/**
* @param arr
*/
private static void print(int[] arr) {
StringBuilder sb = new StringBuilder();
int length = arr.length;
for (int i = 0; i < length; i++) {
sb.append(arr[i]);
sb.append(" ");
}
System.out.println(sb.toString());
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a = null;
a = new int[]{2, 7, 8, 2, 7, 6, 1, 3, 0};
//a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
//a = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
//a = new int[]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
//a = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
//a = new int[]{49, 38, 65, 97, 26, 13, 27, 49, 55, 4};
System.out.println("---------------排序前--------------------");
print(a);
System.out.println("--------------开始排序--------------------");
a = shellSort(a);
System.out.println("---------------排序后---------------------");
print(a);
}
}
五、归并排序(Merge sort)
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 O(nlogn)（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
归并排序(Merge sort) 是一种分治算法，是建立在归并操作上的一种有效的排序算法。常用的 2 路归并排序假设初始序列有 n 个记录，可以看成是 n 个长度为 1 的子序列，进行两两归并，可以得到 n / 2 个长度为 2 或 1 的子序列；再两两归并，******，直到得到一个长度为 n 的有序序列为止。
归并排序的时间复杂度是 O(nlogn)，是一种效率高且稳定的算法。
（1）稳定性
归并排序是一种稳定的排序。
（2）存储结构要求
可用顺序存储结构。也易于在链表上实现。
（3）时间复杂度
对长度为n的文件，需进行 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
（4）空间复杂度
需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)
import org.junit.Test;
import java.util.Arrays;
/**
* @author: weikeqin.cn@gmail.com
* @date: 2018-06-03 19:52
*/
public class MergeSort {
/**
* 归并排序 迭代法
*
* @author weikeqin.cn@gmail.com
*/
public static int[] mergeSortBottomUp(int[] arr) {
int len = arr.length;
int[] result = new int[len];
int block, start;
// 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
for (block = 1; block < len; 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;
return result;
}
/**
*
* @param arr 要排序的数组
* @param result 保存排序结果的数组
* @param start 开始位置
* @param end 结束位置
*
* @author weikeqin.cn@gmail.com
* @date 2018-06-03 21:00
*/
static void merge_sort_recursive(int[] arr, 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;
merge_sort_recursive(arr, result, start1, end1);
merge_sort_recursive(arr, result, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) {
result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 <= end1) {
result[k++] = arr[start1++];
}
while (start2 <= end2) {
result[k++] = arr[start2++];
}
for (k = start; k <= end; k++) {
arr[k] = result[k];
}
}
/**
* 归并排序 递归版
*
* @param arr
* @author weikeqin.cn@gmail.com
* @date 2018-06-03 20:41
*/
public static void merge_sort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
merge_sort_recursive(arr, result, 0, len - 1);
}
}
堆排序 (Heap sort)
堆是具有下列性质的完全二叉树：
- 每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；
- 每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。
堆排序(Heap sort)是指利用堆这种数据结构所设计的一种排序算法。基本思想是把待排序的序列构造成一个大顶堆，此时序列的最大值就是队顶元素，把该元素放在最后，然后对剩下的 n - 1 个元素继续构造大顶堆，直到排序完成。
堆排序的时间复杂度为 O(nlogn)，由于要构造堆，因此不适用于序列个数较少的情况。
堆排序的实现需要解决的两个关键问题：
(1) 将一个无序序列构成一个堆。
(2) 输出堆顶元素后，调整剩余元素成为一个新堆。
复杂度分析
堆排序的运行时间主要耗费在初始构建堆和在重建堆时反复筛选上。在构建对的过程中，因为我们是完全二叉树从最下层最右边的非终端节点开始构建，将它与其孩子进行比较和若有必要的互换，对每个非终端节点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个节点到根节点的距离为(log2(n))+1 ），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。
所以总体来说，堆排序的时间复杂度为O(nlogn)，由于堆排序对原始记录的状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的时间复杂度了。
空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。不过由于记录的比较与交换是跳跃式进行的，因此堆排序也是一种不稳定的排序方法。
另外，由于出事构建堆所需要的比较次数比较多，因此，他并不适合待排序序列个数较少的情况。
初始化堆：将数列a[1…n]构造成最大堆。
交换数据：将a[1]和a[n]交换，使a[n]是a[1…n]中的最大值；然后将a[1…n-1]重新调整为最大堆。 接着，将a[1]和a[n-1]交换，使a[n-1]是a[1…n-1]中的最大值；然后将a[1…n-2]重新调整为最大值。 依次类推，直到整个数列都是有序的。
快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分的记录都比另一部分小，然后再分别对这两个部分进行快速排序，最终实现整个序列的排序。
快速排序的时间复杂度为 O(nlogn)，是一种不稳定的排序算法；
import java.util.Arrays;
/**
* 快速排序<br>
* 快速排序是对冒泡排序的一种改进
*
* <pre>
* 基本思想：选择一个基准元素，通常选择第一个元素或者最后一个元素，
* 通过一趟扫描， 将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素,
* 此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。
* </pre>
*
* @author weikeqin.cn@gmail.com
*/
public class QuickSort {
/**
* <pre>
*
* 基本思想：选择一个基准元素，通常选择第一个元素或者最后一个元素，
* 通过一趟扫描， 将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素,
* 此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。
*
* </pre>
*
* @param arr
* @param start
* @param end
*/
public static void quickSort(int[] arr, int start, int end) {
if(end <= start){
return ;
}
int i = start;
int j = end;
// 数组的第一个作为中轴/基准元素
int pivot = arr[i];
while (i < j) {
// 比中轴大的在高端(右边)
// 从右向左找小于x的数来填arr[i]
while (i < j && arr[j] >= pivot) {
j--;
}
if(i < j){
// 比中轴/基准元素小的，移到低端/左边
//将arr[j]填到arr[i]中，arr[j]就形成了一个新的坑
arr[i] = arr[j];
}
// 比中轴元素小的在低端(左边)
// 从左向右找大于或等于x的数来填arr[j]
while (i < j && arr[i] < pivot) {
i++;
}
if(i < j){
// 比中轴大的，跳出while循环，移到高端/右边
//将arr[i]填到arr[j]中，arr[i]就形成了一个新的坑
arr[j] = arr[i];
}
}
// 中轴记录到尾
// 一次快速排序完，将pivot填到i这个坑中。
arr[i] = pivot;
quickSort(arr, start, i - 1);
quickSort(arr, i+1, end);
}
/**
*
* @param arr
* @param head
* @param tail
*/
public static void qSort(int[] arr, int head, int tail) {
if (head >= tail || arr == null || arr.length <= 1) {
return;
}
int i = head, j = tail, pivot = arr[(head + tail) / 2];
while (i <= j) {
while (arr[i] < pivot) {
++i;
}
while (arr[j] > pivot) {
--j;
}
if (i < j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
++i;
--j;
} else if (i == j) {
++i;
}
}
qSort(arr, head, j);
qSort(arr, i, tail);
}
/**
* @param arr
*/
private static void print(int[] arr) {
System.out.println(Arrays.toString(arr));
}
/**
*
* @param args
*/
public static void main(String[] args) {
int[] arr1 = {2, 7, 8, 2, 7, 6, 1, 3, 0};
int[] arr = {49, 38, 65, 97, 76, 13, 27, 49};
int[] a3 = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62,
99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
arr = new int[]{1, 4, 8, 2, 55, 3, 4, 8, 6, 4, 0, 11, 34, 90, 23, 54, 77, 9, 2, 9, 4, 10};
System.out.print("--------------排序前---------------------");
print(arr);
// 快速排序
quickSort(arr, 0, arr.length - 1);
//quickSortMy(arr, 0, arr.length - 1);
System.out.print("--------------排序后---------------------");
print(arr);
}
}
八：计数排序
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。
算法的步骤如下：
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的位置为1的元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
九、桶排序
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
桶排序以下列程序进行：
设置一个定量的数组当作空桶子。
寻访串行，并且把项目一个一个放到对应的桶子去。（hash）
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的串行中。
十、基数排序
基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
鸡尾酒排序
鸡尾酒排序是冒泡排序的一种变形。先找到最小的数字，放在第一位，再找到最大的数字放在最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。
鸡尾酒排序的时间复杂度为 O(n^2)。
梳排序
梳排序和希尔排序很类似。希尔排序是在直接插入排序的基础上做的优化，而梳排序是在冒泡排序的基础上做的优化，也就是将相距某个增量 d 的记录组成一个子序列，通过冒泡排序使得这个子序列基本有序，然后减少增量继续排序。
梳排序的时间复杂度是 O(nlogn)。
比较标准
时间复杂度
简单的说，就是运行一个程序需要多长时间。
时间频度
一个算法执行所耗费的时间。
一个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。时间复杂度
在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。为此，我们引入时间复杂度概念。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1);另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…， k次方阶O(nk),指数阶O(2n)。
空间复杂度
简单地说，就是运行一个程序需要多少空间(可能是内存，可能是外存)，是10MB，100MB，还是1G。
一个程序的空间复杂度是指运行完一个程序所需内存的大小。
利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。
一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间：
1 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
2 可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)) 其中n为问题的规模，S(n)表示空间复杂度。
References
[1] 《数据结构》(C语言版) 严蔚敏 吴伟民
[2] 算法的时间复杂度和空间复杂度-总结
[3] 算法的时间复杂度和空间复杂度
[4] 时间复杂度和空间复杂度详解
[5] 十种排序算法总结（冒泡、插入、选择、希尔、归并、堆、快速，计数，桶，基数）
[6] Data Structure Visualizations
[7] 九种排序算法的可视化及比较
[8] 冒泡排序
[9] 冒泡排序最佳情况的时间复杂度，为什么是O(n)
[10] 直接插入排序
[11] 插入排序
[12] 图解排序算法(一)之3种简单排序(选择，冒泡，直接插入)
[13] 希尔排序
[14] 图解排序算法(二)之希尔排序
[15] 白话经典算法系列之三 希尔排序的实现
[16] 归并排序
[17] 白话经典算法系列之五 归并排序的实现
[18] “深入理解”—归并排序算法
[19] 白话经典算法系列之六 快速排序 快速搞定
[20] 快速排序
[21] 常见排序算法 - 堆排序 (Heap Sort)
[22] 排序算法 堆排序原理及Java实现
[23] 堆排序介绍
[24] Java排序算法(五)：堆排序