前言：算法第四版2.1节 初级排序算法 学习总结，这里排序的结果都是从大到小。
冒泡排序：
1.从第一个元素开始，比较相邻元素大小，如果后面的元素比前面的元素小则互换位置，一轮结束后，最后一个元素是最大的
2.除去最后一个元素（已经有序了），进行1，倒数第二个位置是剩下的元素中最大的
3.以此类推
速度：正序时是最好情况O（n）,逆序时是最坏情况O（n^2）
/** * 冒泡排序 * @author CANAAN * */ public class BubbleSort { public static void sort(Comparable[] a){ for (int i = 0; i < a.length - 1; i++){ for (int j = 0; j < a.length-1-i; j++){ if (less(a[j+1], a[j])){ exch(a,j,j+1); } } } } private static boolean less(Comparable v, Comparable w){ //比较v是否小于w return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { //交换 Comparable t = a[i]; a[i] = a[j]; a[j] = t; } public static void show(Comparable[] a){ //单行打印数组 for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } public static boolean isSorted(Comparable[] a){ //判断是否有序 for (int i = 1; i < a.length; i++) { if(less(a[i], a[i-1])) return false; } return true; } /*public static void main(String[] args) { String[] a = StdIn.readAllStrings(); sort(a); show(a); }*/ }选择排序：
1.找到数组中最小的元素与数组中第一个元素交换位置
2.在剩下的元素中找到最小的元素和数组中第二个元素交换位置
3.以此类推
速度：对于大小为N的数组，需要N^2/2次比较和N次交换。（数据移动是最少的）
/** * 选择排序 * @author Chuanjie * */ public class SelectionSort { public static void sort(Comparable[] a){ int N = a.length; for (int i = 0; i < N; i++) { int min = i; for (int j = i+1; j < N; j++) { if(less(a[j],a[min])) min = j; exch(a, i, min); } } } private static boolean less(Comparable v, Comparable w){ //比较v是否小于w return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { //交换 Comparable t = a[i]; a[i] = a[j]; a[j] = t; } public static void show(Comparable[] a){ //单行打印数组 for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } public static boolean isSorted(Comparable[] a){ //判断是否有序 for (int i = 1; i < a.length; i++) { if(less(a[i], a[i-1])) return false; } return true; } }
插入排序：
1.从第二个元素开始，与左边的元素倒序逐个比较，比它大就交换位置，直到位于合适位置使左边序列有序
速度：平均需要~N^2/4次比较和~N^2/4次交换；最坏情况需要~N^2/2次比较和~N^2/2次交换；最好情况需要N-1次比较和0次交换。
通常，插入排序要比冒泡和选择快。
使用场景：对接近有序或部分有序的序列排序
/** * 插入排序 * @author Chuanjie * */ public class InsertionSort { public static void sort(Comparable[] a){ int N = a.length; for (int i = 1; i < N; i++) { for (int j = i; j > 0 && less(a[j],a[j-1]); j--) { exch(a,j,j-1); } } } private static boolean less(Comparable v, Comparable w){ //比较v是否小于w return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { //交换 Comparable t = a[i]; a[i] = a[j]; a[j] = t; } public static void show(Comparable[] a){ //单行打印数组 for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } public static boolean isSorted(Comparable[] a){ //判断是否有序 for (int i = 1; i < a.length; i++) { if(less(a[i], a[i-1])) return false; } return true; } }
希尔排序：
思路：使间隔h的元素组成的数组有序，发挥插入排序的优势（h=1时就是插入排序）
1.选择一个增量序列，一般有3*h+1、2^n-1
2.从最大的h开始往下，对h个子序列进行插入排序，直到h=1
速度：性能与选取的h序列有关，最坏时与N^(3/2)成正比（突破了平方级）；使用3*h+1序列的希尔排序所需的比较次数不会超出N的若干倍乘以递增序列的长度
使用场景：无更高效的排序算法时（明显提升了插入排序的性能）；嵌入式系统里（代码量小，不需要额外的内存空间）
/** * 希尔排序：h-sort * 以h为步长划分为若干子数组进行插入排序 * 这里选择的递增序列是 3*h+1 * @author Chuanjie * */ public class ShellSort { public static void sort(Comparable[] a){ int N = a.length; int h = 1; while(h < N/3) h = 3*h +1; while(h>=1){ for (int i = h; i < N; i++) { for (int j = i; j >= h && less(a[j],a[j-h]) ; j-=h) { exch(a,j,j-h); } } h = h/3; } } private static boolean less(Comparable v, Comparable w){ //比较v是否小于w return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { //交换 Comparable t = a[i]; a[i] = a[j]; a[j] = t; } public static void show(Comparable[] a){ //单行打印数组 for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } public static boolean isSorted(Comparable[] a){ //判断是否有序 for (int i = 1; i < a.length; i++) { if(less(a[i], a[i-1])) return false; } return true; } }
总结：
1.排序算法的使用场景很多，结合实例学习便于理解，比如写一个扑克游戏，随机发牌的实现就是逆着使用排序算法（生成随机数）；在寻找凸包（convex hull）时使用的Graham scan核心也是排序算法（排列极角）
2. 算法效率的数学模型是一个复杂的问题，通过实例去分析，不要纠结精确的性能分析。
