排序的概念：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持 不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳 定的；否则称为不稳定的。
1、插入排序
1）直接插入排序
基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。步骤：每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。可以看下面动画展示：
public class 直接插入排序 { public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } 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); } } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args) { int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48 insertionSort(arr); } }
插入排序优化（二分）
将待排序的元素与有序部分的元素比较时，不再挨个比较，而是用二分折中的方式进行比较，去寻找到arr[i]的位置，加快了比较效率
import java.util.Arrays; public class 直接插入排序二分 { public static void insertionSort(int[] arr) { int j,left,mid,right,temp; for(int i = 1;i<arr.length;i++){ left = 0; right = i-1; temp = arr[i]; /*找到合适的插入位置right+1，如果中间位置元素 *比要插入元素大，则查找区域向低半区移动，否则向高半区移动 */ while(left <= right){ mid = (left+right)/2; if(arr[mid]>temp){ right = mid-1; }else{ left = mid+1; } } /*right+1后的元素后移*/ for(j = i-1;j >= right+1;j--) { arr[j+1] = arr[j]; } /*将元素插入到指定位置*/ arr[j+1] = temp; } } public static void main(String[] args) { int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48 insertionSort(arr); } }
总结
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：最环情况：O(N²)。最好情况：O（N）
3. 空间复杂度：O(1)
4. 稳定性：稳定
5. 适用场景：待排序序列的元素个数不多时，且元素基本偏向有序。
2）希尔排序
希尔排序法又称缩小增量法，该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序法的基本思想是：首先取一个整数n（小于序列元素总数）作为间隔，
把待排序数字中所有数分成几个组，所有间隔相同的数分在同一组内，并对每一组内的数进行排序。缩小间隔n，重复上述分组和排序的工作。当达到n=1 时，所有记录统一在一组内排好序。其实从上面的希尔排序的思想中也能看出希尔排序的实现步骤：
- 选n，划分逻辑分组，组内进行直接插入排序。
- 不断缩小n，继续组内进行插入排序。
- 直到n=1，在包含所有元素的序列内进行直接插入排序。
其中缩小间隔gap 的取法有多种。最初 Shell 提出取 gap =n/2，gop =gap/2，直到 gap =1。后来 Knuth 提出取 gap =gap/3 +1。还有人提出都为好有人提 gap 互质为好。无论哪一种主张都没有得到证明。
import java.util.Arrays; public class 希尔排序 { public static void shellSort(int[] arr){ /*初始化划分增量*/ int n = arr.length; int temp; /*每次减小增量，直到n = 1*/ while (n > 1){ /*增量的取法之一：除2向下取整*/ n = n/2; /*对每个按gap划分后的逻辑分组，进行直接插入排序*/ for (int i = n; i < arr.length; ++i) { if (arr[i-n] > arr[i]) { temp = arr[i]; int j = i-n; while (j >= 0 && arr[j] > temp) { arr[j+n] = arr[j]; j -= n; } arr[j+n] = temp; } } } } public static void main(String[] args) { int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48 shellSort(arr); } }
希尔排序优化（二分）
由于希尔排序是基于插入排序的，所以在插入排序中也可运用直接插入排序中的优化方式，所有也可以以二分折中的方式来优化希尔排序。
package 插入排序; import java.util.Arrays; public class 希尔排序二分 { public static void shellSort(int[] arr) { int j, left, mid, right, temp; int n = arr.length; while (n > 1) { n /= 2; for (int i = n; i < arr.length; i++) { left = 0; right = i - 1; temp = arr[i]; while (left <= right) { mid = (left + right) / 2; if (arr[mid] > temp) { right = mid - 1; } else { left = mid + 1; } } for (j = i - n; j >= right + 1; j-=n) { arr[j + n] = arr[j]; } arr[j + n] = temp; } } } public static void main(String[] args) { int[] arr = {1, 8, 6, 29, 10, 14, 37, 48};//排序结果为1,6,8,10,14,29,37,48 shellSort(arr); } }
总结
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。时间复杂度：平均情况：(nlogn)~ o(n²) 。最好情况：o(n¹˙³)。最环情况： o(n²) 。
- 空间复杂度：0(1)
- 稳定性：不稳定
- 适用场景：待排序序列元素较少时。
2、归并排序
1945年，约翰·冯·诺依曼（John von Neumann）发明了归并排序。归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。
基本思路：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
动画展示：
import java.util.Arrays; public class 归并排序 { static void merge(int[] arr, int[] result, int start, int end) { if (start >= end) return; int len = end - start, mid = (len >> 1) + start; int start1 = start; int start2 = mid + 1; /*通过递归不断分成小块，然后再进行排序*/ merge(arr, result, start1, mid); merge(arr, result, start2, end); int k = start; /*进行比较排序*/ while (start1 <= mid && start2 <= end) result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; /*防止某段期间的数组整体大于另一段数组，所有接着将剩余的数拷贝到result数组中*/ while (start1 <= mid) result[k++] = arr[start1++]; while (start2 <= end) result[k++] = arr[start2++]; /*重新拷贝到原数组*/ for (k = start; k <= end; k++) arr[k] = result[k]; } public static void mergesort(int[] arr) { int[] result = new int[arr.length]; merge(arr, result, 0, arr.length - 1); } public static void main(String[] args) { int[] arr = {1, 8, 6, 29, 10, 14, 37, 48};//排序结果为1,6,8,10,14,29,37,48 mergesort(arr); System.out.println(Arrays.toString(arr)); } }
总结
1. 归并的缺点在于需要O(N)的空间复杂度，但是其速度仅次于快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
5.适用场景：待排序序列中元素较多，并且要求较快的排序速度时。
归并排序解决海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
