选择排序

命题： 对于长度为N的数组，选择排序需要大约 N22 次比较和N次交换。

证明： 0到 N−1 的任意 i 都会进行一次交换和N−1−i次比较，因此总共有N次交换以及 (N−1)+(N−2)+...+2+1 = N(N−1)2 ~ N22 次比较

/** * 选择排序 */ public class SelectionSort { public static void sort(Comparable[] arr){ int n = arr.length; for(int i=0;i<n;i++){ int minIndex = i; for(int j=i+1;j<n;j++){ if(Tlt.less(arr[j],arr[minIndex])){ minIndex = j; } } Tlt.exch(arr,i,minIndex); } } }

插入排序

命题 对于随机排序的长度为N且元素不重复的数组，平均情况下插入排序需要~ N24 次比较以及~ N24 次交换。最坏情况下需要~ N22 次比较和 N22 次交换，最好情况下需要 N−1 次比较和0次交换。

/** * 插入排序 * 特点：可提前终止内循环，对于局部有序数组更有利 */ public class InsertionSort { /** * 简单方式，交换次数较多 */ public static void sort(Comparable[] arr){ int n = arr.length; for(int i=1;i<n;i++){ for(int j=i;j>0;j--){ if(Tlt.less(arr[j],arr[j-1])){ Tlt.exch(arr,j,j-1); }else{ break; } } } } /** * 优化方式，一个元素只交换一次 */ public static void sort2(Comparable[] arr){ int n = arr.length; for(int i=1;i<n;i++){ Comparable e = arr[i]; int j; for(j=i;j>0 && Tlt.less(e,arr[j-1]);j--){ // j-1向后移动 arr[j] = arr[j-1]; } arr[j] = e; } } /** * 局部排序 */ public static void sort2(Comparable[] arr,int l,int r){ for(int i=l+1;i<=r;i++){ Comparable e = arr[i]; int j; for(j=i;j>l && Tlt.less(e,arr[j-1]);j--){ // j-1向后移动 arr[j] = arr[j-1]; } arr[j] = e; } } public static void main(String[] args) { Integer[] random = Tlt.random(10, 0, 10); sort2(random,1,9); Tlt.show(random); } }

希尔排序

/** * @author fangxin * @date 2017/4/1. */ public class ShellSort { void sort(Integer a[]){ int h = 1; // 递增序列 int n = a.length; while(h<n/3){ h = 3*h+1;//1，4，13，40... } while(h>=1){ for (int i = h; i < n; i++){ for (int j = i; j >= h && Tlt.less(a[j],a[j-h]); j -= h){ Tlt.exch(a,j, j-h); } } // 按照递增序列递减 h = h/3; } } public static void main(String[] args) { Integer[] arr = new Integer[]{49,38,65,97,26,13,27,49,55,4}; ShellSort shellSort = new ShellSort(); shellSort.sort(arr); Tlt.show(arr); } }

希尔排序时间复杂度分析