[数据结构与算法之排序算法]

package sort;import java.util.Arrays;public class SelectionSort extends Sort{ //数据分布，完全随机，大致有序，大致平稳 //算法的执行时间除了与算法的策略有关之外，还与数据分布有关系； public SelectionSort(int[] arr){ super(arr); } @Override public void sort() { for(int i = 0;i arr[j]){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } System.out.println(Arrays.toString(arr)); }}

冒泡排序是一种间的排序算法，他重复的走访要排序的数列，一次比较两个元素，如果它们的顺序错误就交换一下，走访数列的工作是重复的，直到没有需要交换的，也就是该数列已经排序完毕。
其时间复杂度为：O(n^2)
空间复杂度为：O(1)
稳定性：稳定

动态图：

package sort;import java.util.Arrays;public class BubbleSort extends Sort{ public BubbleSort(int[] arr){ super(arr); } @Override public void sort() { for(int i=0;i arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } System.out.println(Arrays.toString(arr)); }}

它的工作原理是通过构建有序序列，对于未排序序列，再已经有序的序列中从后往前扫描，找到相应的插入位置并插入。
它的时间复杂度为；O(n^2)
空间复杂度为：O(1)
稳定性：稳定

动态图演示：

代码实现：

package sort;import java.util.Arrays;public class InsertionSort extends Sort{ public InsertionSort(int[] arr){ super(arr); } @Override public void sort() { for(int i=1;i0&&arr[j-1]>e;j--){ arr[j] = arr[j-1]; } arr[j] = e; } System.out.println(Arrays.toString(arr)); }}

也叫缩小增量排序，它是第一个突破O(n^2)的排序算法；
它是插入排序的升级版，相比插入排序它的步长为1，所以我们定义一个变量向前减减即可，但是希尔排序的步长不定，核心还是插入排序；
其时间复杂度为：O(n^1.3)
空间复杂度为：O(1)
稳定性：不稳定

动态图演示：

代码实现：

package sort;import java.util.Arrays;public class ShellSort extends Sort{ public ShellSort(int[] arr){ super(arr); } @Override public void sort() { int len = arr.length; for(int gap = len / 2;gap> 0;gap=gap/2){ for(int i = gap;i= 0 && arr[j-gap] > e) { arr[j] = arr[j - gap]; j = j-gap; } arr[j] = e; } } System.out.println(Arrays.toString(arr)); }}

归并排序是建立在归并操作上的一种有效的排序算法，该算法采用分治法的一个非常典型的应用，将已有序的子序列合并，得到完全有序的序列；也就是先让每个子序列有序，再让子序列段间有序。若将两个有序表合并为一个有序表，成为二路归并。
其时间复杂度为：O(nlogn)
空间复杂度为：O(n)
稳定性：稳定

动态图：

代码实现：

package sort;import java.util.Arrays;public class MergeSort extends Sort { public MergeSort(int[] arr){ super(arr); } @Override public void sort() { mergeSort(0,arr.length-1); System.out.println(Arrays.toString(arr)); } private void mergeSort(int L, int R) { //当做指针大于等于右指针则递归结束； if(L >= R){ return; } int mid = (L+R) / 2; mergeSort(L,mid);//先左后右； mergeSort(mid+1,R) //如是前面的最后一个比后面的第一个元素大才向上递归。 if(arr[mid] > arr[mid+1]){ merge(L,mid,R); } }//向上合并数列 private void merge(int L,int mid, int R) { //先将原数组复制一份； int[] aux = new int[R-L+1]; for(int k=L;k<=R;k++){ aux[k-L] = arr[k]; } int i = L; int j = mid+1; //判断如是前面部分已经排完，则后面部分直接赋值即可，反之一样； //若是都没完，则判断两部分那个元素值小先赋值。 for(int k=L;k<=R;k++){ if(i>mid){ arr[k] = aux[j-L]; j++; }else if(j > R){ arr[k] = aux[i-L]; i++; }else if(aux[i-L] < aux[j-L]){ arr[k] = aux[i-L]; i++; }else{ arr[k] = aux[j-L]; j++; } } }}

package sort;public class TestSort { public static void main(String[] args) { //0 完全随机 1 大致有序 2 大致平稳 数据量为10000个 ArrayData data = new ArrayData(0); //ArrayData data = new ArrayData(1); //ArrayData data = new ArrayData(2); int[] arr = data.makeData(); test01(arr); test02(arr); test03(arr); test04(arr); test05(arr); } private static void test01(int[] arr){ BubbleSort bubbleSort = new BubbleSort(arr); Long start = System.currentTimeMillis(); bubbleSort.sort(); Long end = System.currentTimeMillis(); System.out.println("冒泡排序所用时间："+ (end - start)); } private static void test02(int[] arr){ SelectionSort selectionSort = new SelectionSort(arr); Long start = System.currentTimeMillis(); selectionSort.sort(); Long end = System.currentTimeMillis(); System.out.println("选择排序所用时间："+ (end - start)); } private static void test03(int[] arr){ InsertionSort insertionSort = new InsertionSort(arr); Long start = System.currentTimeMillis(); insertionSort.sort(); Long end = System.currentTimeMillis(); System.out.println("插入排序所用时间："+ (end - start)); } private static void test04(int[] arr){ ShellSort shellSort = new ShellSort(arr); Long start = System.currentTimeMillis(); shellSort.sort(); Long end = System.currentTimeMillis(); System.out.println("哈希排序所用时间："+(end - start)); } private static void test05(int[] arr){ MergeSort mergeSort = new MergeSort(arr); Long start = System.currentTimeMillis(); mergeSort.sort(); Long end = System.currentTimeMillis(); System.out.println("归并排序所用时间："+ (end - start)); }}