由于需要分析算法的最好时间复杂度和最坏时间复杂度，因此这篇文章中写的排序都是从小到大的升序排序。
带排序的数组为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(N*N)，平均TC为O(NLogN)。SC为O(LogN)
算法实现：
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.");
}