一、通用排序算法

定义通用函数swap，用于交换两个槽位的数值

  1. public void swap(int[] nums, int i, int j) {
  2.         int t = nums[i];
  3.         nums[i] = nums[j];
  4.         nums[j] = t;
  5.     }

1）冒泡排序

冒泡排序，顾名思义，就是不断将较大（小）的元素移动到最后，形成有序数组
此处使用了一个优化：扫描一遍，没有元素发生交换，就说明已经是有序了

  1. public void bubbleSort(int[] nums) {
  2.     for (int end = nums.length; end > 0; end--) {
  3.         boolean flag = false;
  4.         for (int j = 1; j < end; j++) {
  5.             if (nums[j - 1] > nums[j]) {
  6.                 swap(nums, j, j-1);
  7.                 flag = true;
  8.             }
  9.         }
  10.         if (flag == false) {
  11.             break;
  12.         }
  13.     }
  14. }
  1.  最优时间复杂度为 `O(n)`，平均时间复杂度为`O(n^2)`，空间复杂度为`O(1)`

2）插入排序

插入排序思路：

将数组分为两部分，前一部分和后一部分，前一部分是有序的，后一部分是还未排序的 1、选择后一部分的第一个元素 2、在前一部分中找到该元素应该插入的位置loc（这部分可以使用二分查找进行优化） 3、整体移动元素空出该loc位置，并插入该元素

  1. public void insertSort(int[] nums) {
  2.     for (int i = 1; i < nums.length; i++) {
  3.         int val = nums[i];
  4.         int loc = findByBinary(nums, 0, i, val);    // 找到应该插入的位置
  5.         for (int j = i - 1; j >= loc; j--) {    // 移动其他元素，腾出位置
  6.             nums[j+1] = nums[j];
  7.         }
  8.         nums[loc] = val;    // 插入选择的元素
  9.     }
  10. }
  11. public int findByBinary(int[] nums, int start, int end, int val) {
  12.     while (start < end) {
  13.         int mid = (start + end)/2;
  14.         if (nums[mid] == val) {
  15.             return mid;
  16.         } else if (nums[mid] > val) {
  17.             end = mid;
  18.         } else {
  19.             start = mid + 1;
  20.         }
  21.     }
  22.     return start;
  23. }
  1. 最优时间复杂度`O(n*logn)`，平均时间复杂度为`O(n^2)`，空间复杂度为`O(1)`

3）归并排序

归并排序思路：
这是一种分治的思路，将一段数据拆分为两段，每段又进行拆分，保证小段有序，再合成大段有序

  1. public void mergeSort(int[] nums) {
  2.     subMerge(nums, 0, nums.length);
  3. }
  4. public void subMerge(int[] nums, int s, int e) {
  5.     if (s >= e - 1) {    // 当段中没有元素或只有一个元素的时候，不用排序
  6.         return;
  7.     }
  8.     int mid = (s + e)/2;
  9.     subMerge(nums, s, mid);
  10.     subMerge(nums, mid, e);        // 让两段段内有序
  12.     int[] temp = new int[e - s];    // 使用一个临时数组存放新有序序列
  13.     int h1 = s, h2 = mid;
  14.     for (int i = 0; i < temp.length; i++) {
  15.         if ((h2 >= e) || (h1 < mid && nums[h1] < nums[h2])) {
  16.             temp[i] = nums[h1++];
  17.         } else {
  18.             temp[i] = nums[h2++];
  19.         }
  20.     }
  21.     for (int i = 0; i < temp.length; i++) {    // 将新有序序列复制回原数组
  22.         nums[s + i] = temp[i];
  23.     }
  24. }

最优时间复杂度O(n*logn)，平均时间复杂度为O(n*logn)，空间复杂度为O(n)

4）快速排序

快速排序也是一种分治的思想：

1、选择一个元素，让小于这个元素的值在左边，大于等于这个元素的值放在右边（下方代码没有加上随机选值的优化） 2、将选择的元素放在中间 3、继续分别快排左边和右边的元素

  1. public void quickSort(int[] nums) {
  2.     subQuick(nums, 0, nums.length - 1);
  3. }
  4. public void subQuick(int[] nums, int s, int e) {
  5.     if (s >= e) {
  6.         return;
  7.     }
  8.     int val = nums[s];
  9.     int head = s, tail = e;
  10.     while (head < tail) {
  11.         while (head < tail && nums[tail] >= val) {
  12.             tail--;
  13.         }
  14.         nums[head] = nums[tail];
  15.         while (head < tail && nums[head] <= val) {
  16.             head++;
  17.         }
  18.         nums[tail] = nums[head];
  19.     }
  20.     nums[head] = val;
  21.     subQuick(nums, s, head - 1);
  22.     subQuick(nums, head + 1, e);
  23. }
  1. 最优时间复杂度为`O(n*logn)`，平均时间复杂度为`O(n*logn)`，最坏时间复杂度为`O(n^2)`，空间复杂度为`O(logn)`

5）堆排序

堆排序的思想和上述排序不太一样，而是将内部建立成一棵树，树顶上的元素值最大（大根堆情况）：

1、调整堆中元素，形成大根堆 2、将堆顶元素取出，与树最后一个叶子节点进行交换 3、调整元素 4、重复序号2、3的过程，直到全部有序

  1. public void heapSort(int[] nums) {
  2.     for (int i = nums.length/2 - 1; i >= 0; i--) {
  3.         adjustHeap(nums, 0, nums.length);
  4.     }
  5.     for (int i = nums.length; i >= 0; i--) {
  6.         swap(nums, 0, i - 1);
  7.         adjustHeap(nums, 0, i-1);
  8.     }
  9. }
  10. public void adjustHeap(int[] nums, int loc, int len) {
  11.     int temp = nums[loc];
  12.     for (int k = 2*loc + 1; k < len; k = 2 * k + 1) {
  13.         if (k + 1 < len && nums[k+1] > nums[k]) {
  14.             k++;
  15.         }
  16.         if (nums[k] > temp) {
  17.             nums[loc] = nums[k];
  18.             loc = k;
  19.         } else {
  20.             break;
  21.         }
  22.     }
  23.     nums[loc] = temp;
  24. }

初始化建堆时间复杂度为O(n)
最优时间复杂度为O(n+nlogn)，平均时间复杂度为O(n+nlogn)，空间复杂度为O(1)

二、Java中的sort函数（针对Object对象）

Arrays中的sort函数流程如下，1.8中的LegacyMergeSort.userRequested为false：
判断是否使用legacyMergeSort进行排序，检查需要排序的元素个数，看数据规模
规模小于32：统计数组开头升序序列个数，使用二叉排序法（也是插入排序，只不过用二分查找优化过）
规模大于32：
划分多个大小为32的块
找到有序数据长度，如果长度太小，会使用二叉排序法进行扩展，保证分块内有序，分别存入数组起始下标、长度，并对栈中多个数组进行merge，重复此步骤，直到排序完成
最后处理，如果仍有数据没有merge，则进行merge操作，直到最后数据都合并到一起