排序算法汇总II.md
排序算法汇总 II
插入排序：
插入排序的思想非常简单，生活中有一个很常见的场景：在打扑克牌时，我们一边抓牌一边给扑克牌排序，每次摸一张牌，就将它插入手上已有的牌中合适的位置，逐渐完成整个排序。
有两种写法：
- 交换法： 在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置。
- 移动法： 在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。
具体写法如下：
一、交换法
1 | public static void insertSort(int[] arr){ |
当数字少于两个时，不存在排序问题，当然也不需要插入，所以我们直接从第二个数字开始往前插入。
整个过程就像是已经有一些数字坐成了一排，这时一个新的数字要加入，这个新加入的数字原本坐在这一排数字的最后一位，然后它不断地与前面的数字比较，如果前面的数字比它大，它就和前面的数字交换位置。
二、移动法
实际上，新插入的这个数字并不一定适合与它交换的数字所在的位置。也就是说，它刚换到新的位置上不久，下一次比较后，如果又需要交换，它马上又会被换到前一个数字的位置。
由此，我们可以想到一种优化方案：让新插入的数字先进行比较，前面比它大的数字不断向后移动，直到找到适合这个新数字的位置后，新数字只做一次插入操作即可。
代码如下：
1 | public static void insertSort(int[] arr){ |
时间复杂度O(nlogn)的排序算法
希尔排序
希尔排序本质上是对插入排序的一种优化，它利用了插入排序的简单，又克服了插入排序每次只交换相邻两个元素的缺点。它的基本思想是：
- 将待排序数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组
- 逐渐缩小间隔进行下一轮排序
- 最后一轮时，取间隔为 11，也就相当于直接使用插入排序。但这时经过前面的「宏观调控」，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成
其中，每一遍排序的间隔在希尔排序中被称之为增量，所有的增量组成的序列称之为增量序列.增量依次递减，最后一个增量必须为 11，所以希尔排序又被称之为「缩小增量排序」。
1 | public static void shellSort(int[] arr){ |
实际上，这段代码可以优化一下。我们现在的处理方式是：处理完一组间隔序列后，再回来处理下一组间隔序列，这非常符合人类思维。但对于计算机来说，它更喜欢从第 gap 个元素开始，按照顺序将每个元素依次向前插入自己所在的组这种方式。虽然这个过程看起来是在不同的间隔序列中不断跳跃，但站在计算机的角度，它是在访问一段连续数组。
1 | public static void shellSort(int[] arr){ |
增量序列
增量序列如果选得不好，希尔排序的效率可能比插入排序效率还要低。
以 Knuth 增量序列为例，使用 Knuth 序列进行希尔排序的代码如下：
1 | public static void shellSortByKnuth(int[] arr){ |
快速排序
它的时间复杂度也是 O(nlogn)O(nlogn)，但它在时间复杂度为 O(nlogn)O(nlogn) 级的几种排序算法中，大多数情况下效率更高，所以快速排序的应用非常广泛。再加上快速排序所采用的分治思想非常实用。
- 从数组中取出一个数，为基数（pivot）;
- 遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域。
- 将左右两个区域视为两个数组，重复前两个步骤，直到排序完成。
说明：
事实上，快速排序的每一次遍历，都将基数摆到了最终位置上。第一轮遍历排好 1 个基数，第二轮遍历排好 2 个基数（每个区域一个基数，但如果某个区域为空，则此轮只能排好一个基数），第三轮遍历排好 4 个基数（同理，最差的情况下，只能排好一个基数），以此类推。总遍历次数为 logn～n 次 。
- 快速排序的递归框架具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public static void quickSort(int[] arr){
quickSort(arr,0,arr.length-1);
}
public static void quickSort(int[] arr ,int start,int end){
// 将数组分区，并获得中间值的下标
int mid = partition(arr, start,end);
// 对左边区域快速排序
quickSort(arr,start,mid-1);
// 对右边区域快速排序
quickSort(arr,mid+1,end);
}
public static int partition(int[] arr, int start , int end){
// TODO: 将 arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
}第二种关于区域划分的方法，使用双指针。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start,int end){
if(start>=end) return;
int mid = partition(arr,start,end);
quickSort(arr,start,mid-1);
quickSort(arr,mid+1,end);
}
public static int partition(int[] arr,int start,int end){
int pivot = arr[start];
int left = start+1;
int right = end;
while(left<right){
while(left<right && arr[left]<=pivot) left++;
if(left!=right){
swap(arr,left,right);
right--;
}
}
if(left == right && arr[right]>pivot) right--;
if(right!=start) swap(arr,start,right);
return right;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public static int partition(int[] arr,int start ,int end){
int pivot = arr[start];
int left = start+1;
int right = end;
while(left<right){
while(left<right && arr[left]<=pivot) left++;
while(left<right && arr[right]>=pivot) right--;
if(left<right){
swap(arr,left,right);
left++;
right--;
}
}
if(left == right && arr[right]>pivot) right--;
swap(arr,start,right);
return right;
}
归并排序
只要开辟一个长度等同于两个数组长度之和的新数组，并使用两个指针来遍历原有的两个数组，不断将较小的数字添加到新数组中，并移动对应的指针即可。
根据这个思路，可以写出合并两个有序列表的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20private static int[] merge(int[] arr1, int[] arr2) {
int[] res = new int[arr1.length+arr2.length];
int idx1 = 0,idx2=0;
while(idx1 < arr1.length && idx2< arr2.length){
if(arr1[idx1]<=arr2[idx2]){
res[idx1+idx2] = arr1[idx1];
idx++;
}else{
res[idx1+idx2] = arr2[idx2];
idx2++
}
}
while(idx1<arr1.length){
res[idx1+idx2]=arr1[idx1++];
}
while(idx2<arr2.length){
res[idx1+idx2]=arr1[idx2++];
}
return res;
}将数组拆分层有序数组
拆分过程使用了二分的思想，这是一个递归的过程，归并排序使用的递归框架如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public static void mergeSort(int[] arr) {
if (arr.length == 0) return;
int[] result = mergeSort(arr, 0, arr.length - 1);
// 将结果拷贝到 arr 数组中
for (int i = 0; i < result.length; i++) {
arr[i] = result[i];
}
}
// 对 arr 的 [start, end] 区间归并排序
private static int[] mergeSort(int[] arr, int start, int end) {
// 只剩下一个数字，停止拆分，返回单个数字组成的数组
if (start == end) return new int[]{arr[start]};
int middle = (start + end) / 2;
// 拆分左边区域
int[] left = mergeSort(arr, start, middle);
// 拆分右边区域
int[] right = mergeSort(arr, middle + 1, end);
// 合并左右区域
return merge(left, right);
}归并排序的优化：减少临时空间的开辟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53public static void mergeSort(int[] arr) {
if (arr.length == 0) return;
int[] result = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, result);
}
// 对 arr 的 [start, end] 区间归并排序
private static void mergeSort(int[] arr, int start, int end, int[] result) {
// 只剩下一个数字，停止拆分
if (start == end) return;
int middle = (start + end) / 2;
// 拆分左边区域，并将归并排序的结果保存到 result 的 [start, middle] 区间
mergeSort(arr, start, middle, result);
// 拆分右边区域，并将归并排序的结果保存到 result 的 [middle + 1, end] 区间
mergeSort(arr, middle + 1, end, result);
// 合并左右区域到 result 的 [start, end] 区间
merge(arr, start, end, result);
}
// 将 result 的 [start, middle] 和 [middle + 1, end] 区间合并
private static void merge(int[] arr, int start, int end, int[] result) {
int middle = (start + end) / 2;
// 数组 1 的首尾位置
int start1 = start;
int end1 = middle;
// 数组 2 的首尾位置
int start2 = middle + 1;
int end2 = end;
// 用来遍历数组的指针
int index1 = start1;
int index2 = start2;
// 结果数组的指针
int resultIndex = start1;
while (index1 <= end1 && index2 <= end2) {
if (arr[index1] <= arr[index2]) {
result[resultIndex++] = arr[index1++];
} else {
result[resultIndex++] = arr[index2++];
}
}
// 将剩余数字补到结果数组之后
while (index1 <= end1) {
result[resultIndex++] = arr[index1++];
}
while (index2 <= end2) {
result[resultIndex++] = arr[index2++];
}
// 将 result 操作区间的数字拷贝到 arr 数组中，以便下次比较
for (int i = start; i <= end; i++) {
arr[i] = result[i];
}
}