基本排序算法总结 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆排序：
以下排序算法模版都会用Comparable接口数据类型，只要实现了Comarable接口的数据类型比如Integer、Double、String和其他许多高级数据类型（如File和URL），这些数据类型的数组可以作为参数调用排序方法。
这里的输入不是Scanner cin = new Scanner(System.in)，因为读取花费的时间太大，主要时间都在读取上面了，不如直接读入然后在进行转换操作来得快，所以采用BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
但是也有弊端，比如存在文件中的数据有几万条或者更多，那么必定是有很多行数据，但是这么读取只能读取一行，就需要如下改进：
while ((line = cin.readLine()) != null) {
......
}
直接看关键排序代码即可， 写的是通用类型的排序，整型浮点型字符串都可以，只需修改输入定义的数组引用类型即可。
以下算法参考《算法(第四版)》
目录
冒泡排序
选择排序
插入排序
希尔排序
归并排序
快速排序
堆排序：
最好情况(加了标记辅助的)时间复杂度O(n)
平均情况O(n*n)
最坏情况O(n*n)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Bubble_Sort {
public static boolean isLess(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
public static void bubbleSort(Comparable[] a) {
if (a == null || a.length < 2) {
return;
}
for (int end = a.length - 1; end > 0; --end) {
boolean flag = true; // 如果不要标记符，那么冒泡的最好情况也只能是O(n*n)了
for (int i = 0; i < end; ++i) {
if (isLess(a[i + 1], a[i])) { // 升序
swap(a, i + 1, i);
flag = false;
}
}
if (flag)
break; // 已经有序了，最好情况时间复杂度O(n)
}
}
public static void swap(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine().trim();
br.close();
String[] s = line.split(" +"); // 输入全部转成字符串， 分割成数组元素
int len = s.length;
/**
* 为什么不直接Scanner按照类型读取? 因为读取花费的时间太大，主要时间都在读取上面了，不如直接读入然后在进行转换操作来得快
* 如果直接字符串排序就不需要接下来的转换操作了。
*/
Integer[] a = new Integer[len];
// 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
for (int i = 0; i < len; ++i) {
a[i] = Integer.valueOf(s[i]);
}
bubbleSort(a);
if (len != 0) {
System.out.print(a[0]);
}
for (int i = 1; i < len; ++i) {
System.out.print(" " + a[i]);
}
}
}选择排序
时间复杂度的最好最坏和平均情况都是O(n*n)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Selection_Sort {
public static boolean isLess(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
public static void selectionSort(Comparable[] a) {
if (a == null || a.length < 2) {
return;
}
for (int i = 0; i < a.length - 1; ++i) {
int min = i;
for (int j = i + 1; j < a.length; ++j) {
min = isLess(a[j], a[min]) ? j : min; // 升序
}
if (min != i) {
swap(a, i, min);
}
}
}
public static void swap(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine().trim();
br.close();
String[] s = line.split(" +"); // 输入全部转成字符串， 分割成数组元素
int len = s.length;
/**
* 为什么不直接Scanner按照类型读取? 因为读取花费的时间太大，主要时间都在读取上面了，不如直接读入然后在进行转换操作来得快
* 如果直接字符串排序就不需要接下来的转换操作了。
*/
Integer[] a = new Integer[len];
// 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
for (int i = 0; i < len; ++i) {
a[i] = Integer.valueOf(s[i]);
}
selectionSort(a);
if (len != 0) {
System.out.print(a[0]);
}
for (int i = 1; i < len; ++i) {
System.out.print(" " + a[i]);
}
}
}冒泡排序和选择排序实际一般用不到了，只是一个教学版本，但至少得掌握吧
插入排序
时间复杂度最好情况是O(n)
最坏和平均情况是O(n*n)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Insertion_Sort {
public static boolean isLess(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
public static void InsertionSort(Comparable[] a) {
if (a == null || a.length < 2) {
return;
}
for (int i = 1; i < a.length; ++i) { // 从前往后排序
for (int j = i; j > 0 && isLess(a[j], a[j - 1]); --j) { // 前面数据一定已经排好序，刚刚开始比较发现a[j]>a[j+1]，
// 不满足就进行下一轮循环
swap(a, j, j - 1); // 因此最好情况是O(n)，本身是有序数组，外层O(n),内层O(1)忽略
}
}
}
public static void swap(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine().trim();
br.close();
String[] s = line.split(" +"); // 输入全部转成字符串， 分割成数组元素
int len = s.length;
/**
* 为什么不直接Scanner按照类型读取? 因为读取花费的时间太大，主要时间都在读取上面了，不如直接读入然后在进行转换操作来得快
* 如果直接字符串排序就不需要接下来的转换操作了。
*/
Integer[] a = new Integer[len];
// 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
for (int i = 0; i < len; ++i) {
a[i] = Integer.valueOf(s[i]);
}
InsertionSort(a);
if (len != 0) {
System.out.print(a[0]);
}
for (int i = 1; i < len; ++i) {
System.out.print(" " + a[i]);
}
}
}希尔排序
最好情况时间复杂度O(n^1.25)
最坏情况是O(n^5/3)而不是O(n^2)，要优于插入排序
平均情况O(nlogn)~O(n^5/3)
透彻理解希尔排序的性能至今仍然是一项挑战，实际上希尔排序是至今唯一无法准确描述其对于乱序的数组的性能的排序方法
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Shell_Sort {
public static boolean isLess(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
public static void shellSort(Comparable[] a) {
int n = a.length;
int h = 1;
while (h < n / 3)
h = 3 * h + 1; // 递增序列1，4，13，40，121，364，1093......
while (h >= 1) {
for (int i = h; i < n; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
swap(a, j, j - h);
}
// 可以打印交换过程，方便理解
/*
* for (int k = 0; k < n; ++k) { System.out.print(a[k] + " "); }
* System.out.println();
*/
}
h /= 3;
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void swap(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine().trim();
br.close();
String[] s = line.split(" +"); // 输入全部转成字符串， 分割成数组元素
int len = s.length;
/**
* 为什么不直接Scanner按照类型读取? 因为读取花费的时间太大，主要时间都在读取上面了，不如直接读入然后在进行转换操作来得快
* 如果直接字符串排序就不需要接下来的转换操作了。
*/
Integer[] a = new Integer[len];
// 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
for (int i = 0; i < len; ++i) {
a[i] = Integer.valueOf(s[i]);
}
shellSort(a);
if (len != 0) {
System.out.print(a[0]);
}
for (int i = 1; i < len; ++i) {
System.out.print(" " + a[i]);
}
}
}希尔排序为了加快速度简单的改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。希尔排序的思想是使数组中任意间隔为h的元素都是有序的，这样的数组被称为h有序数组。实现希尔排序的一中方法是对于每个h，用插入排序将h个子数组独立的排序。但因为子数组是相互独立的，一个更简单的方法是h子数组中将每个元素交换到比它还大的元素之前去(将比它大的元素向右移动了一格)。只需要在插入排序的代码中将移动元素的距离由1改为h即可。这样，希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。
如何选择递增序列h呢？算法的性能不进取决于h，还取决于h之间的数学性质，比如它们的公因子等。有很多论文研究了各种不同的递增序列，但都无法证明某个递增序列是“最好的”。
归并排序
最好最坏平均的时间复杂度都是O(nlogn)
关于递归行为的复杂度分析可以见我的另一篇博客https://blog.csdn.net/qq_34115899/article/details/79841329
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class MergeSort {
// 不把help[]声明为merge()方法的局部变量，是为了避免每次归并时，即使是归并很小的数组，都创建一个新的数组。
// 如果这么做，那么创建新数组将成为归并排序运行时间的主要部分。更好的解决方案是把help[]变为sort方法的局部变量，
// 并将它作为参数传递给merge()方法
public static Comparable[] help;
public static void mergeSort(Comparable[] a) {
if (a == null || a.length < 2) {
return;
}
help = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
public static void sort(Comparable[] a, int lo, int hi) {
if (lo >= hi) {
return;
} // 为什么不直接(lo+hi)>>1呢，因为lo+hi可能溢出，而hi-lo不溢出，lo+((hi-lo)>>1)是小于hi的，也不溢出，更安全
int mid = lo + ((hi - lo) >> 1); // 对于java最好(lo + hi) >>> 1
sort(a, lo, mid);
sort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
public static boolean isLess(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
public static void merge(Comparable[] a, int lo, int mid, int hi) {
int j = lo, k = mid + 1;
for (int i = lo; i <= hi; ++i) {
help[i] = a[i];
}
for (int i = lo; i <= hi; ++i) {
if (j > mid) {
a[i] = help[k++];
} else if (k > hi) {
a[i] = help[j++];
} else if (isLess(help[k], help[j])) {
a[i] = help[k++];
} else {
a[i] = help[j++];
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine().trim();
br.close();
String[] s = line.split(" +"); // 输入全部转成字符串， 分割成数组元素
int len = s.length;
/**
* 为什么不直接Scanner按照类型读取? 因为读取花费的时间太大，主要时间都在读取上面了，不如直接读入然后在进行转换操作来得快
* 如果直接字符串排序就不需要接下来的转换操作了。
*/
Integer[] a = new Integer[len];
// 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
for (int i = 0; i < len; ++i) {
a[i] = Integer.valueOf(s[i]);
}
mergeSort(a);
if (len != 0) {
System.out.print(a[0]);
}
for (int i = 1; i < len; ++i) {
System.out.print(" " + a[i]);
}
}
}归并排序比希尔排序快吗？？在实际的应用中，它们的运行时间之间的差距在常数级别之内(希尔排序使用的是经过验证的递增序列)，因此相对性能取决于具体的实现。
理论上来说，还没有人能够证明希尔排序对于随机数据的运行时间是线性对数级别的，因此存在平均情况下希尔排序的性能的渐进增长率更高的可能性，在最坏的情况下，这种差距的存在已经被证实了，但这对实际应用没有影响。
快速排序
原地排序：空间复杂度为O(1)，相对于归并排序来说，占用非常小的内存便可以实现很高效的排序的效果
平均状态下的时间复杂度为O(nlogn)， 最好O（nlogn），最坏O（n*n）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;
public class QuickSort {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine().trim();
br.close();
String[] s = line.split(" +"); // 输入全部转成字符串， 分割成数组元素
int len = s.length;
/**
* 为什么不直接Scanner按照类型读取? 因为读取花费的时间太大，主要时间都在读取上面了，不如直接读入然后在进行转换操作来得快
* 如果直接字符串排序就不需要接下来的转换操作了。
*/
Integer[] a = new Integer[len];
// 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
for (int i = 0; i < len; ++i) {
a[i] = Integer.valueOf(s[i]);
}
quickSort(a);
if (len != 0) {
System.out.print(a[0]);
}
for (int i = 1; i < len; ++i) {
System.out.print(" " + a[i]);
}
}
private static Random random = new Random(System.currentTimeMillis());
private static void quickSort(Comparable[] a) {
shuffle(a); // 随机任意打乱顺序，消除对输入的依赖，之后会讲为什么
quickSort(a, 0, a.length - 1);
}
private static void quickSort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int j = partition(a, lo, hi);
quickSort(a, lo, j - 1);
quickSort(a, j + 1, hi);
}
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1;
Comparable v = a[i];
while (true) {
while (less(a[++i], v))
if (i >= hi)
break;
while (less(v, a[--j]))
if (j <= lo)
break;
if (i >= j)
break;
swap(a, i, j); // 将第一个大于v的数--a[i]和第一个小于v的数--a[j]交换
}
swap(a, lo, j);
return j;
}
private static void swap(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static boolean less(Comparable com, Comparable v) {
return com.compareTo(v) < 0;
}
private static void shuffle(Object[] a) {
validateNotNull(a); // 判断数组是否为空
int n = a.length;
for (int i = 0; i < n; i++) {
int r = i + uniform(n - i);
Object temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
public static int uniform(int n) {
if (n <= 0)
throw new IllegalArgumentException("argument must be positive: " + n);
return random.nextInt(n);
}
private static void validateNotNull(Object x) {
if (x == null) {
throw new IllegalArgumentException("argument is null");
}
}
}有一个能被证明的命题就是：快速排序最多需要约（N*N）/ 2次比较，但随机打乱能够预防这种情况。
问：随机将数组打乱似乎占用了排序用时的一大部分时间，这么做值得吗？
值得。这能够防止出现最怀情况并使运行时间可以预计。Hoare在1960年提出这个算法的时候就推荐了这种方法——它是一种(也是第一批)偏爱随机性的算法。
下面给出三向切分的快速排序作为参考：
对于大量重复元素， 时间复杂度可降到O(N)
private static void quickSort3Way(Comparable[] a, int lo, int hi) {
if (hi >= lo)
return;
int lt = lo, i = lo + 1, gt = hi;
Comparable v = a[lo];
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0)
swap(a, lt++, i++);
else if (cmp > 0)
swap(a, i, gt--);
else
++i;
} // 现在a[lo...lt-1] < v = a[lt..gt] < a[gt + 1...hi]成立
quickSort3Way(a, lo, lt - 1);
quickSort3Way(a, gt + 1, hi);
}对于大量重复元素的数组，它将排序时间从 线性对数级别 降低到了线性级别。这种对于重复元素的适应性使得三向切分的快速排序成为排序库函数的最佳算法选择——需要将包含大量重复元素的数组排序的用例很常见。
堆排序：
下沉排序（数值大的下沉，这样就是升序，如果数值小的下沉，那么就是降序）
最好最坏平均时间复杂度都为O(nlogn)，空间复杂度为O(1)
升序代码：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class HeapSort {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine().trim();
br.close();
String[] s = line.split(" +"); // 输入全部转成字符串， 分割成数组元素
int len = s.length;
/**
* 为什么不直接Scanner按照类型读取? 因为读取花费的时间太大，主要时间都在读取上面了，不如直接读入然后在进行转换操作来得快
* 如果直接字符串排序就不需要接下来的转换操作了。
*/
Integer[] a = new Integer[len];
// 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
for (int i = 0; i < len; ++i) {
a[i] = Integer.valueOf(s[i]);
}
heapSort(a);
if (len != 0) {
System.out.print(a[0]);
}
for (int i = 1; i < len; ++i) {
System.out.print(" " + a[i]);
}
}
private static void heapSort(Comparable[] a) {
int N = a.length;
for (int k = N >> 1; k >= 1; --k) { // 堆的构造，从树底端开始往上恢复堆有序
sink(a, k, N);
}
while (N > 1) { // 从上往下沉，让数组变成升序(下沉排序)
swap(a, 1, N--); // 第一个一定是最大的，换到数组最后
sink(a, 1, N); // 剩下的元素继续恢复堆有序
}
}
private static void sink(Comparable[] a, int k, int n) {
while ((k << 1) <= n) { // (k << 1) <= N说明一定有左孩子
int j = k << 1; // 左孩子下标
if (j < n && less(a, j, j + 1)) // j < N说明一定有右孩子,如果左孩子小于右孩子的值
++j; // 下标转移到右孩子
if (less(a, j, k)) // 如果k结点的孩子中的最大值还是比k结点的值小，不用下沉了，已经堆有序
break;
swap(a, k, j); // 和孩子中的最大值交换
k = j; // 现在这个元素已经在刚刚的j位置上，继续记录这个元素的位置，继续判断看能否继续下沉
}
}
private static void swap(Object[] a, int k, int j) { // 第k和第j个元素交换，因为是下标所以-1
Object temp = a[k - 1];
a[k - 1] = a[j - 1];
a[j - 1] = temp;
}
private static boolean less(Comparable[] a, int j, int i) {
return a[j - 1].compareTo(a[i - 1]) < 0;
}
}
测试结果：
-2 5 34 768 12 678 32 675 0 345 -1 12
-2 -1 0 5 12 12 32 34 345 675 678 768
降序代码：
(仅仅将less换成了greater)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class HeapSort {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine().trim();
br.close();
String[] s = line.split(" +"); // 输入全部转成字符串， 分割成数组元素
int len = s.length;
/**
* 为什么不直接Scanner按照类型读取? 因为读取花费的时间太大，主要时间都在读取上面了，不如直接读入然后在进行转换操作来得快
* 如果直接字符串排序就不需要接下来的转换操作了。
*/
Integer[] a = new Integer[len];
// 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
for (int i = 0; i < len; ++i) {
a[i] = Integer.valueOf(s[i]);
}
heapSort(a);
if (len != 0) {
System.out.print(a[0]);
}
for (int i = 1; i < len; ++i) {
System.out.print(" " + a[i]);
}
}
private static void heapSort(Comparable[] a) {
int N = a.length;
for (int k = N >> 1; k >= 1; --k) { // 堆的构造，从树底端开始往上恢复堆有序
sink(a, k, N);
}
while (N > 1) { // 从上往下沉，让数组变成降序(下沉排序)
swap(a, 1, N--); // 第一个一定是最小的，换到数组最后
sink(a, 1, N); // 剩下的元素继续恢复堆有序
}
}
private static void sink(Comparable[] a, int k, int n) {
while ((k << 1) <= n) { // (k << 1) <= N说明一定有左孩子
int j = k << 1; // 左孩子下标
if (j < n && greater(a, j, j + 1)) // j < N说明一定有右孩子,如果左孩子大于右孩子的值
++j; // 下标转移到右孩子
if (greater(a, j, k)) // 如果k结点的孩子中的最小值还是比k结点的值大，不用下沉了，已经堆有序
break;
swap(a, k, j); // 和孩子中的最小值交换
k = j; // 现在这个元素已经在刚刚的j位置上，继续记录这个元素的位置，继续判断看能否继续下沉
}
}
private static void swap(Object[] a, int k, int j) { // 第k和第j个元素交换，因为是下标所以-1
Object temp = a[k - 1];
a[k - 1] = a[j - 1];
a[j - 1] = temp;
}
private static boolean greater(Comparable[] a, int j, int i) {
return a[j - 1].compareTo(a[i - 1]) > 0;
}
}测试结果：
-2 5 34 768 12 678 32 675 0 345 -1 12
768 678 675 345 34 32 12 12 5 0 -1 -2
命题1：用下沉操作由N个元素构造堆只需要少于2N次比较以及少于N次交换
命题2：将N个元素排序，堆排序只需要少于(2NlgN+2N)次比较(以及一半次数的交换)，其中2N项来自堆的构造，2NlgN项来自于每次下沉操作最大可能需要2NlgN次比较。
相关知识阅读：基于堆的优先级队列
============================Talk is cheap, show me the code============================