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; // 已经有序了，最好的情况是时间复杂度OO(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]); } }}
希尔排序
最好的情况是时间复杂度OO(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)
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）/ 两次比较，但随机打乱可以防止这种情况。
问:随机打乱数组似乎占据了排序时间的很大一部分，值得吗？
值得。这可以防止最多的情况，并预测运行时间。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); }
对于大量重复元素的数组，从线性对数级别降低到了线性级别。这种对重复元素的适应性使得三向切割的快速排序成为排序库函数的最佳算法选择——常用于包含大量重复元素的数组排序。
堆排序：
下沉排序(大值下沉，就是升序，小值下沉就是降序)
平均时间复杂度最好最差(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
降序代码：
(只用greater代替less)
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次比较。
阅读相关知识：基于堆的优先级队列
湘公网安备43019002002060