一 希尔排序
1.1 插入排序的问题
我们看简单的插入排序可能存在的问题. 数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小)
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.
1.2 基本介绍
希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
1.3 思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含 的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止
1.4 代码实现
public static void shellSort3(int[] arr) {
int temp = 0;
int count = 0;
//缩小增量，对每一组进行简单插入排序
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//为什么从gap开始依次增量排序。因为前面的0-gap-1是各组的第一个元素（有序表）。
for (int i = gap; i < arr.length; i++) {
insertI(arr,i,gap);
}
System.out.println("希尔排序第" + (++count) + "轮 =" + Arrays.toString(arr));
}
}
/**
* 插入arr[i]到所在组正确位置的代码（insertI）
* 已经保证i所在组前面的元素已经是有序的
* @param arr
* @param i
* @param gap
*/
private static void insertI(int[] arr, int i, int gap) {
//下一个比较的下标
int compareIndex = i - gap;
int temp = arr[i];//注意刚开始就要保留该值
while(compareIndex >= 0 && arr[compareIndex] > temp) {
//后移
arr[compareIndex+gap] = arr[compareIndex];
compareIndex -= gap;
}
/*
* 此时要么没找到比他更小的，compareIndex=-1。放本组第一个=compareIndex+gap
* 要么找到了比他更小的，本次插入位置应该在compareIndex的后面。compareIndex+gap
*/
arr[compareIndex+gap] = temp;
}
1.5 小结
- 增量=分组数。增量越大，分组越多。增量最小时（为1），分组数量也是1.
- 每个分组内部进行
简单插入排序
二 快速排序
2.1 基本介绍
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两 部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
原理:
快速排序,说白了就是给基准数据找其正确索引位置的过程.
2.2 个人理解
- 为什么首先从后半部分开始？能不能从前半部分开始？
我觉得是要看基准值的下标。假如我们用第一个元素作为基准值，我们用temp存储了它的值。然后从后半部分开始的话，当high的下标所在值小于基准值的话。就会用low下标的位置来存储之前发现的小值.
之后开始反向遍历low，发现大的，又用high的位置来存储。
这样的话我们会发现一个规律
- 当一个下标的值被存储时（temp或其他下标），那这个下标就需要存储其他下标（不排除原下标）的值。比如：刚开始low下标的值被temp存储了，那之后high发现的小值就被low下标所在位置存储。
2.3 代码实现
package com.nrsc.sort;
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后:");
for (int i : arr) {
System.out.println(i);
}
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找寻基准数据的正确索引
int index = getIndex(arr, low, high);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
quickSort(arr, 0, index - 1);
quickSort(arr, index + 1, high);
}
}
private static int getIndex(int[] arr, int low, int high) {
// 基准数据
int tmp = arr[low];
while (low < high) {
// 当队尾的元素大于等于基准数据时,向前挪动high指针
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果队尾元素小于tmp了,需要将其赋值给low
arr[low] = arr[high];
// 当队首元素小于等于tmp时,向前挪动low指针
while (low < high && arr[low] <= tmp) {
low++;
}
// 当队首元素大于tmp时,需要将其赋值给high
arr[high] = arr[low];
}
// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
arr[low] = tmp;
return low; // 返回tmp的正确位置
}
}
1.4 总结
- 快速排序基准值两边的并不是有序的，只是都是比基准值小或大。
三 归并排序
3.1 基本介绍
（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取
3.2 基本思想
3.3 理解
咋一看，总感觉分治的思想和快速排序很象。都是讲整体分，然后都有递归
区别
- 快速是按基准值分，两边的元素可能不一致。
- 归并在分的阶段没有排序，在治的阶段排序（
治完局部有序，保证两个局部融合的时候元素时有序的） - 快速不需要治的阶段
3.4 代码实现
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2、设定两个指针变量，最初位置分别指向两个已经排好序的数组序列的起始位置；
3、比较两个指针所指向的元素，选择相对小的元素放入到申请的合并空间里，并移动此指针到下一位置；
4、继续重复步骤3直到某一指针达到序列尾；
5、当一个指针到达一个序列尾时，将另一序列剩下的所有元素直接复制到合并序列尾。
package com.atguigu;
public class MergeSort {
//两路归并算法，两个排好序的子序列合并为一个子序列
public void merge(int []a,int left,int mid,int right){
int []tmp=new int[a.length];//辅助数组
int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针
while(p1<=mid && p2<=right){
if(a[p1]<=a[p2])
tmp[k++]=a[p1++];
else
tmp[k++]=a[p2++];
}
while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
while(p2<=right) tmp[k++]=a[p2++];//同上
//复制回原素组
for (int i = left; i <=right; i++)
a[i]=tmp[i];
}
/**
* 递归保证了总是分无可分阶段，才会治
* @param a
* @param start
* @param end
*/
public void mergeSort(int [] a,int start,int end){
if(start<end){//当子序列中只有一个元素时结束递归
/*
* 分
*/
int mid=(start+end)/2;//划分子序列
mergeSort(a, start, mid);//对左侧子序列进行递归排序
mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
/*
* 治
*/
merge(a, start, mid, end);//合并
}
}
public void test(){
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
mergeSort(a, 0, a.length-1);
System.out.println("排好序的数组：");
for (int e : a)
System.out.print(e+" ");
}
}
四 堆排序
参考：
https://blog.csdn.net/g1607058603/article/details/80796097
4.1 小结
什么是堆？
一种数据结构与，分为大顶堆（每个非叶子节点都比其孩子节点的值大）和小顶堆。
堆是一种特殊的完全二叉树。主要步骤有哪些？
先要构建大顶堆（小顶堆），然后依次去掉堆顶，并把最后一个元素放在堆顶。结束标志，堆中没元素了如何表示堆？
用数组表示。根据观察得出：左节点下标=父节点下标*2+1构建时需要从堆中的最后一个元素开始调整吗？
不要，需要从最后一个非叶子节（下标=arr.length()/2-1）点开始遍历。
初始化构建微观上是自上而下的（即每次交换后都需要继续往下检查，交换后的节点是否比子节点都大），宏观上是自下而上（即从最后一个非叶子节点开始）为什么之后只需要
自上而下调整？
这个之前也比较纠结！
先分析：
- 从第二次开始调整，我们可以发现堆
已经都是有序的（大顶堆或小顶堆）。当我们把最后一个元素放在堆顶上后，堆可能会无效。所以我们需要调整。从上到下调整是因为：只要调整后的值大于子节点，我们就不需要考虑以这个子节点为堆顶的堆是否有序（必然有序）。所以结束调整的信号也是：调整后的值大于子节点
- 思想思路
堆顶元素可能不在一个正确的位置。我们就需要不断调整它的位置，需要先拿到这个元素的值（用temp存储），如果该元素的现在位置（下标一直在变）的两个子节点都比他小。那就停止调整了。
4.2 代码实现
public static int[] heapSort(int[] target) {
//判断数组，即判断堆是否存在
if (target != null && target.length > 1) {
// 从初始堆的最后一个非叶子节点开始调整
int pos = target.length / 2 - 1;// 因为索引从0开始，第N/2-1处（N为节点数量）的节点正好是二叉树的最后一个非叶子节点
while (pos >= 0) {
//从初始堆的最后一个非叶子节点开始，从右到左，从下到上的调整各个元素
/*
* pos一直在减小，即堆一直在在变大
* 这里需要知道
*/
shiftDown(target, pos, target.length - 1);
pos--;
}
// 经过一轮堆调整后，将大根堆的根元素与堆的最后一个元素交换
for (int i = target.length - 1; i > 0; i--) {
int temp = target[i];// 将最大堆的第一个元素和最后一个元素交换
target[i] = target[0];
target[0] = temp;
shiftDown(target, 0, i - 1);// 此时只要将第一个元素放到合适的位置就行，因为其他位置都已经是有序的了
}
return target;
}
return target;
}
/**
* @description 自上而下调整为最大堆，将需要调整的元素放在合适的位置。
以start元素为堆顶，开始调整
* @author rico
* @created 2017年5月25日 上午9:45:40
* @param target
* @param start
* @param end
*/
private static void shiftDown(int[] target, int start, int end) {
//将节点i换到适合自己的位置，一直和子节点比较，
//一直向下走，直到不能走了为止
int i = start;//i是父节点
int j = 2 * start + 1;//节点i左孩子的索引
int temp = target[i];//从该元素开始调整堆
while (j <= end) {// 迭代条件，否则就不是叶子节点
//否则就是单叶子
if (j < end && target[j + 1] > target[j]) {//找出较大子女，将节点i的左孩子和右孩子进行比较
j = j + 1; //右孩子比较大，存储较大的叶子节点下标
}
if (target[j] <= temp) {// 父亲大于子女，这个temp是不变的，是要放置在正确位置的那个元素
break;//不操作，结束调整。
} else {//父亲小于子女
target[i] = target[j];//将子女中较大的值赋给父亲
i = j;//将较大的子节点作为根节点，比较该根节点和其子女和值大小，看是否需要调整。
j = 2 * j + 1;//继续调整。以j为堆顶
}
}
//结束之后，将最开始的堆顶元素放到合适位置的下标。不排除i=start
target[i] =temp;
}
