常用排序算法的Java实现与分析
由于需要分析算法的最好时间复杂度和最坏时间复杂度，因此这篇文章中写的排序都是从小到大的升序排序。
带排序的数组为arr，arr的长度为N。时间复杂度使用TC表示，额外空间复杂度使用SC表示。
好多代码都用到了交换arr[i]和arr[j]的地方，这里先给出代码。
private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
（1）插入排序
1.1直接插入排序
算法思想：初始时第一个元素是有序的，在插入元素arr[i]时，arr[0] ~arr[i – 1]已经是有序的了，将arr[i]插入其中即可。
稳定性：如果遇到和arr[i]相等的元素，那么将arr[i]放在后面，所以直接插入排序是稳定的。
复杂度分析：arr基本有序（升序）时，直接插入排序的TC是O(N)；arr降序时，TC是O(N*N)；平均时间复杂度O(N*N)。直接插入排序的SC是O(1)。
算法实现：
public class InsertionSort_StraightInsertionSort { public static int[] sis(int[] arr) { for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } return arr; }
}
1.2希尔排序
算法思想：希尔排序的实质就是分组插入排序，该方法又称为缩小增量排序。先将arr分割成若干个子序列（由相隔某个增量的元素组成），分别进行直接插入排序，然后依次缩小增量再进行排序。待整个序列中的元素基本有序（增量足够小时），再对全体元素进行一次直接插入排序。
稳定性：不稳定
复杂度分析：TC最好为O(N) ，最坏 O(N * N)，平均TC为O(N*1.3)。SC为O(1)。
算法实现：
public class InsertionSort_ShellSort { public static int[] shellSort(int[] arr) { for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { for (int j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) { swap(arr, j, j + gap); } } } return arr; } }
（2）交换排序
2.1冒泡排序
算法思想：一次比较两个元素，如果他们的顺序错误就把他们交换过来。
稳定性：稳定
复杂度分析：arr升序时TC最好为O(N) ，arr降序时TC最坏 O(N * N)，平均TC为O(N*N)。SC为O(1)
算法实现：
public class Exchange_Bubble { public static int[] bubbleSort(int[] arr) { for (int i = arr.length; i != 0; i--) { for (int j = 1; j < i; j++) { if (arr[j] < arr[j - 1]) { swap(arr, j - 1, j); } } } return arr; } }
2.2快速排序
算法思想：1．先从数列中取出一个数作为基准数；2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。3．再对左右区间重复第二步，直到各区间只有一个数。
稳定性：不稳定
复杂度分析：arr升序时TC最好为O(NLogN) ，arr降序时TC最坏 O(NLogN)，平均TC为O(NLogN)。SC为O(1)
算法实现：
public class Exchange_QuickSort { public static int[] quickSort1(int[] arr) { return qs1(arr, 0, arr.length - 1); } private static int[] qs1(int[] arr, int left, int right) { if (left > right) { return arr; } int i = left; int j = right; int tmp = arr[left]; while (i < j) { while (i < j && arr[j] >= tmp) { j--; } while (i < j && arr[i] <= tmp) { i++; } if (i < j) { swap(arr, i, j); } } arr[left] = arr[i]; arr[i] = tmp; qs1(arr, left, i - 1); qs1(arr, i + 1, right); return arr; } }
(3)选择排序
3.1简单选择排序
算法思想：在要排序的一组数中，选择出最小的数与第一个数交换；然后在剩下的数中，选择出最小的数与第二个数交换，以此类推。
稳定性：稳定
复杂度分析：arr升序时，只是避免了交换元素的操作，TC最好仍旧为O(N*N) ；arr降序时TC最坏 O(N*N)，平均TC为O(N*N)。SC为O(1)
算法实现：
public class SelectionSort_SimpleSelectionSort { public static int[] simpleSelectionSort(int[] arr) { for (int i = 0; i < arr.length; i++) { int minIdx = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIdx]) { minIdx = j; } } if (arr[minIdx] < arr[i]) { swap(arr, minIdx, i); } } return arr; } }
3.2堆排序
算法思想：从小到大排序，构建大顶堆(堆首先是一棵完全二叉树，大顶堆每个节点的值都不大于父节点的值)，然后每次将堆顶元素和没有排序的最后的元素交换，重新构建堆（即重新得到最大的堆顶元素）。
稳定性：不稳定
复杂度分析：
最好情况：如果待排序数组是降序的，仍然需要O(N * logN)复杂度的比较操作，少了移动的操作；
最坏情况：如果待排序数组是升序的，不仅需要O(N * logN)复杂度的比较操作，而且需要O(N * logN)复杂度的交换操作。总的时间复杂度还是O(N * logN)。
在最好和最坏情况下，堆排序的时间复杂度都是O(NlogN)。堆排序时，由于每次重新恢复堆的时间复杂度为O(logN)，共N – 1次堆调整操作，再加上前面建立堆时N / 2次向下调整，
每次调整时间复杂度也为O(logN)。两次次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。
堆排序一般优于快速排序的重要一点是，数据的初始分布情况对堆排序的效率没有大的影响。
算法实现：
public class SelectionSort_HeapSort { public static int[] heapSort(int[] arr) { buildHeap(arr); for (int i = arr.length - 1; i >= 0; i--) { swap(arr, 0, i);//交换完后，大的元素跑到了数组的后面的部分 所以堆排序时 数组后面到前面逐渐变得有序 heapify(arr, 0, i); //调整回大顶堆，即重新找到未排序部分的最大值 } return arr; } private static void buildHeap(int[] arr) { for (int i = (arr.length - 1) / 2; i >= 0; i--) { heapify(arr, i, arr.length); } } //从index开始往下不断调整大顶堆 private static void heapify(int[] arr, int index, int heapSize) { int left = index * 2 + 1; int right = index * 2 + 2; int largest = index; while (left < heapSize) { if (arr[left] > arr[index]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } if (largest != index) { swap(arr, largest, index); } else { break; } index = largest; left = index * 2 + 1; right = index * 2 + 2; } } }
（4）不基于比较的排序
4.1桶排序
算法思想：桶排序可用于最大最小值相差较大的数据情况，要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。
把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
1.找出待排序数组中的最大值max、最小值min；2.我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶；4.每个桶各自排序；5.遍历桶数组，把排序好的元素放进输出数组
稳定性：稳定
复杂度分析：
N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：O(N)+O(M*(N/M)log(N/M))=O(N+N(logN-logM))=O(N+N*logN-N*logM)
当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。
桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。
算法实现：
public class NoCompare_BucketSort { public static int[] bucketSort(int[] arr) { int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int cur : arr) { max = Math.max(max, cur); min = Math.min(min, cur); } //计算桶的数量并构建初始的桶 int bucketNum = (max - min) / arr.length + 1; // int bucketNum = (max - min) + 1; //每个桶中只有一个元素的时候就是计数排序 List<List<Integer>> buckets = new ArrayList<>(); for (int i = 0; i < bucketNum; i++) { buckets.add(new ArrayList<>()); } //将每个元素放到桶中 for (int cur : arr) { int index = (cur - min) / arr.length; // int index = (cur - min); //每个桶中只有一个元素的时候就是计数排序 buckets.get(index).add(cur); } //对每个桶内的元素进行排序，可以使用直接插入排序等排序方法 int index = 0; for (List<Integer> bucket : buckets) { insertSort(bucket); for (int cur : bucket) { arr[index++] = cur; } } return arr; } private static void insertSort(List<Integer> bucket) { Integer[] arr = bucket.toArray(new Integer[bucket.size()]); for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } for (int i = 0; i < arr.length; i++) { bucket.set(i, arr[i]); } } }
4.2基数排序
算法思想： 基数排序（Radix Sort）是一种非比较型排序算法，它将整数按位数切割成不同的数字，然后按每个位分别进行排序。
基数排序的方式可以采用MSD（Most significant digital）或LSD（Least significant digital），MSD是从最高有效位开始排序，而LSD是从最低有效位开始排序。当然我们可以采用MSD方式排序，按最高有效位进行排序，将最高有效位相同的放到一堆，然后再按下一个有效位对每个堆中的数递归地排序，最后再将结果合并起来。但是，这样会产生很多中间堆（高位排序比低位排序多了空间开销）。所以，通常基数排序采用的是LSD方式。LSD基数排序实现的基本思路是将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
需要注意的是，对每一个数位进行排序的算法必须是稳定的，否则就会取消前一次排序的结果。
稳定性：稳定
复杂度分析：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。
空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。
算法实现：
public class NoCompare_RadixSort { public static int[] radixSort(int[] arr) { int maxLen = getMaxBit(arr);//得到arr中最大的数的长度 int[] tmp = new int[arr.length]; int[] count = new int[10];// 计数器 int radix = 1; for (int i = 1; i <= maxLen; i++) {// 进行maxLen次排序 Arrays.fill(count, 0);// 每次分配前清空计数器 for (int j = 0; j < arr.length; j++) { int k = (arr[j] / radix) % 10;// 统计每个桶中的记录数 count[k]++; } for (int j = 1; j < 10; j++) { count[j] = count[j - 1] + count[j];// 将tmp中的位置依次分配给每个桶 } for (int j = arr.length - 1; j != -1; j--) {// 将所有桶中的记录依次收集到tmp中 int k = (arr[j] / radix) % 10; tmp[count[k] - 1] = arr[j]; count[k]--; } for (int j = 0; j < arr.length; j++) {// 将临时数组的内容复制到arr中 arr[j] = tmp[j]; } radix = radix * 10; } return arr; } // 得到arr中最大的数的长度 private static int getMaxBit(int[] arr) { int maxNum = Integer.MIN_VALUE; for (int cur : arr) { maxNum = Math.max(maxNum, cur); } return String.valueOf(maxNum).length(); } }
（5）归并排序
算法思想：
将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行合并。
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，
可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
稳定性：稳定
复杂度分析：最好、最坏、平均TC都是O(NlogN)。SC是O(N)
算法实现：
public class MergeSort { //将arr[first~mid]和arr[mid~last]合并到tmp中 private static void mergeArray(int[] arr, int first, int mid, int last, int[] tmp) { int begin1 = first; int begin2 = mid + 1; int end1 = mid; int end2 = last; int k = 0; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] < arr[begin2]) { tmp[k++] = arr[begin1++]; } else { tmp[k++] = arr[begin2++]; } } while (begin1 <= end1) { tmp[k++] = arr[begin1++]; } while (begin2 <= end2) { tmp[k++] = arr[begin2++]; } //将辅助数组tmp的数据写回arr for (begin1 = 0; begin1 < k; begin1++) { arr[first + begin1] = tmp[begin1]; } } public static int[] mergeSort(int[] arr, int first, int last, int[] tmp) { if (first < last) { int mid = (first + last) / 2; mergeSort(arr, first, mid, tmp);//左边有序 mergeSort(arr, mid + 1, last, tmp);//右边有序 mergeArray(arr, first, mid, last, tmp);//将两个有序数列合并 } return arr; } }
此外，为了验证结果的正确性，可以写个和Arrays.sort()方法比较的代码。getIntArr得到一个大小是size，最大值小于bound的int数组。arrEquals比较两个int数组是否相等。
public class MyUtil { public static int[] getIntArr(int size, int bound) { int[] arr = new int[size]; Random r = new Random(); for (int i = 0; i < size; i++) { arr[i] = r.nextInt(bound); } return arr; } public static boolean arrEquals(int[] arr1, int[] arr2) { for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } }
以直接插入排序为例，我们可以这么用MyUtil。
public static void main(String[] args) { int times = 0; while (times++ < 100) { int[] arr = MyUtil.getIntArr(50, 100); int[] brr = arr.clone(); Arrays.sort(arr); if (!MyUtil.arrEquals(arr, sis(brr))) { System.out.println("Something Wrong"); } } System.out.println("Everything is OK."); }