八大排序算法（下）

归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该方法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各个答案拼接在一起，即为分而治之）。

实现思想

具体步骤

代码实现

//分+合方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if(left < right) {
int mid = (left + right) / 2; //中间索引
//向左递归进行分解
mergeSort(arr, left, mid, temp);
//向右递归进行分解
mergeSort(arr, mid + 1, right, temp);
//合并
merge(arr, left, mid, right, temp);
}
}
//合并的方法
/\*\*
\*
\* @param arr 排序的原始数组
\* @param left 左边有序序列的初始索引
\* @param mid 中间索引
\* @param right 右边索引
\* @param temp 做中转的数组
\*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 初始化i, 左边有序序列的初始索引
int j = mid + 1; //初始化j, 右边有序序列的初始索引
int t = 0; // 指向temp数组的当前索引
//(一)
//先把左右两边(有序)的数据按照规则填充到temp数组
//直到左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j <= right) {//继续
//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
//即将左边的当前元素，填充到 temp数组
//然后 t++, i++
if(arr[i] <= arr[j]) {
temp[t] = arr[i];
t += 1;
i += 1;
} else { //反之,将右边有序序列的当前元素，填充到temp数组
temp[t] = arr[j];
t += 1;
j += 1;
}
}
//(二)
//把有剩余数据的一边的数据依次全部填充到temp
while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[j];
t += 1;
j += 1;
}
//(三)
//将temp数组的元素拷贝到arr
//注意，并不是每次都拷贝所有
t = 0;
int tempLeft = left; //
//第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3
//最后一次 tempLeft = 0 right = 7
while(tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}

注释写的很详细，这里就不做过多论述了。

基数排序

基数排序（RADIX-SORT）属于“分配式排序”，又称“桶子法”，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的效果。

基数排序是属于稳定性的排序，基数排序法是效率高的稳定性排序法

基数排序是桶排序的扩展。

基本思想

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低为开始，依次进行排序。

这样从最低位排序一直到最高位排序完成以后，数列就是一个有序序列。

图文说明

代码实现

public static void radixSort(int[] arr) {
//根据前面的推导过程，我们可以得到最终的基数排序代码
//1.得到最大的位数
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int maxLength = (max + " ").length(); //转字符串 去length 得到长度
//定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
//说明
//1. 二维数组包含10个一维数组
//2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
//3. 名明确，基数排序是使用空间换时间的经典算法
int[][] bucket = new int[10][arr.length];
//循环处理
for (int i = 0, n = 1; i < maxLength; i++, n \*= 10) {
int[] bucketElementCounts = new int[10];
//第n轮
for (int j = 0; j < arr.length; j++) {
//取出每个元素的个位的值
int digitOfElement = arr[j] / n % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
int index = 0;
//遍历每一桶，并将桶中数据，放入原数组
for (int k = 0; k < bucketElementCounts.length; k++) {
//如果桶中有数据，我们放入到原数组
if (bucketElementCounts[k] != 0) {
//循环该桶即第K个桶（即第k个一维数组），放入
for (int l = 0; l < bucketElementCounts[k]; l++) {
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
bucketElementCounts[k] = 0;
}
// System.out.println("第" + (i + 1) + "轮基数排序后：" + Arrays.toString(arr));
}
}
}

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆是什么？

具有完全以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆，不要求节点的左孩子和右孩子值的大小。

每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆

一般升序采用大顶堆，降序采用小顶堆

基本思想

1. 将待排序序列构造成一个大顶堆
2. 此时，整个序列的最大值就是堆顶的最大值
3. 将其与末尾元素进行交换，此时末尾就为最大值
4. 然后将剩下的n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，就得到一个有序序列了。

图解

步骤一：构造初始堆。将给定无序序列构造成一个大顶堆

1.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

3.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

4.这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无序序列构造成了一个大顶堆。

步骤二 ：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

6.将堆顶元素9和末尾元素4进行交换

7.重新调整结构，使其继续满足堆定义

8.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

9.后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

代码实现

public static void headSort(int arr []){
// System.out.println("堆排序");
int temp = 0;
// //分步完成
// adjustHeap(arr,1,arr.length);
// System.out.println("第一次"+ Arrays.toString(arr));
// adjustHeap(arr,0,arr.length);
// System.out.println("第二次"+ Arrays.toString(arr));
//将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
for (int i = arr.length /2 -1;i >=0;i --){
adjustHeap(arr,i,arr.length);
}
/\*\*
\* 2.将堆顶元素与末尾元素交换，将最大元素沉到数组末端
\* 3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行
\*/
for (int j = arr.length -1; j > 0; j--){
//交换
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr,0,j);
}
// System.out.println("数组="+Arrays.toString(arr));
}
/\*\*
\*
\* @param arr 待调整的数组
\* @param i 表示非叶子节点在数组中的索引
\* @param length 表示对多少个元素进行调整，length是在逐渐减少
\*/
public static void adjustHeap(int arr [],int i,int length){
int temp =arr[i]; //先取出当前元素的值，保存在临时变量
//开始调整
//说明
//1，k = i \*2 +1 k是i节点的左子节点
for (int k = i \* 2 +1; k < length; k = i \* 2 +1) {
if (k+1 < length && arr[k] < arr [k+1]){ //说明左子节点的值小于右子节点的值
k ++;
}
if (arr [k] > temp){ //如果子节点大于父节点
arr[i] = arr [k]; //把较大的值赋给当前节点
i = k;
}else {
break;
}
}
//当for 循环结束后，我们已经将以i 为父节点的树的最大值，放在了最顶（局部）
arr [i] = temp; //将temp值放到调整后的位置
}
}

这篇介绍是三种排序确定有点难，需要大家先理解实现思路，在debug进去程序，去看每一步的操作。

八大排序算法时间复杂度分析

排序算法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n^2)	O(n^2)	稳定	O(1)	n小时较好
交换	O(n^2)	O(n^2)	不稳定	O(1)	n小时较好
选择	O(n^2)	O(n^2)	不稳定	O(1)	n小时较好
插入	O(n^2)	O(n^2)	稳定	O(1)	大部分已排序较好
基数	O(logRB)	O(logRB)	稳定	O(n)	B是真数（0-9）R是基数（个十百）
Shell	O(nlogn)	O(n^s) 1<s<2	不稳定	O(1)	s是所选分组
快排	O(nlogn)	O(n^2)	不稳定	O(nlogn)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好

平均时间复杂度和最坏时间复杂度

1. 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

2. 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

   ​

我个人喜欢快排，尤其是递归实现的快排，理解思想和代码阅读都很容易，在开发中遇到排序通常调用的是集合工具类Arrays的sort()方法，它底层也是用的快排。