概述
排序算法分类
在我们日常处理数据的时候，排序是最经常用到，如果一层层的嵌套for循环会让代码的效率变得非常低，这个时候，我们就要借用排序的理念来优化我们的代码，目前有十个比较经典的排序算法：
1、冒泡排序
2、快速排序
3、插入排序
4、希尔排序
5、选择排序
6、堆排序
7、归并排序
8、计数排序
9、桶排序
10、基数排序
具体的如下图所示：（图转自https://www.cnblogs.com/onepixel/articles/7674659.html）
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
算法复杂度
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
1、冒泡排序
冒泡排序：
1、设置个标识位；
2、不断的比较前后两个元素的大小，如果前一个值比后一个值大就交换两个元素的位置，改变标识位的值，否则不变，并且指针指向后一个元素；
3、重复2的步骤，当遇到标识位没有变化或者循环结束，排序完成
代码块：
boolean flag = true;
for (int i = 0;i<data.length;i++){
for (int j = 0;j<data.length-i-1;j++){
if (data[j]>data[j+1]){
int temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
//转换标识位
flag = false;
}
}
if (flag)
//如果没有进行转换，flag=true，跳出循环
break;
else
flag = true;
}
2、快速排序
快速排序：(申明两个指针，head指向链表头，tail指向链表尾）
从链表尾tail开始，当tail指向元素的值比head大的时候，则tail往前移动一个位置，当tail指向元素的值小于head指向元素的值得时候，交换head和tail所指元素的值，然后从head继续开始比较，如果head指向元素的值大于tail指向的值，则交换head和tail所指元素的值，否则head往后移动一个位置，直到head=tail的时候，结束第一轮循环。
其实head第一次指向的值，我们称它为一个基准，然后通过上面的思路循环，最后可以做到这个基准值的左边是小于它的，基准值得右边是大于它的，这样才算完成第一轮的循环，而左右两个区间还是无序数列，需要通过递归的方式，一步步对这些无序数列进行排序。
代码块：
public void kpSort(int[] source,int start,int end){
//保留大区间的头尾
int i = start;
int j = end;
int value = source[start];
//当i!=j的时候，说明本轮循环还未结束
while (i<j){
//从链表尾开始循环
while (source[j]>=source[i] && j>i)
j--;
source[i] = source[j];
source[j] = value;
//从链表头开始循环
while (source[i]<=source[j] && i<j)
i++;
source[j] = source[i];
source[i] = value;
}
//递归左右两个无序区间的数列
if (i>start)kpSort(source,start,i-1);
if (j<end)kpSort(source,j+1,end);
}
3、插入排序
插入排序的思路：
1、从当前排序数列的第二个元素开始，比较第二个元素与第一个元素的大小，如果小于则两个元素互换位置
2、当进行步骤一之后，会将指针继续指向下一个元素，指针前的元素都是排好序的了，那么指针指向下一个元素，比较指针指向元素的值与前一个值的大小，如果大于则不变，如果小于则将前一个元素后移一位，然后继续比较移动元素前一位元素的值，直到找到比指针指向元素值来的小的值，则插到该值的后边
3、循环第二步操作，直到数列尾
这个插入排序还是很好理解的，也就是当前有个排好序的数列，如果你要插入一个元素，你就需要从后面一个个的往前进行比较，比较的过程中还要将比当前元素大的值往后移动一位，直到找到符合条件的位置，才可以插入，这样当前数列还是一个有序数列，以此类推循环到数列尾。
代码块：
int nowValue;
int preIndex;
for (int i = 1 ;i<data.length;i++){
nowValue = data[i];
preIndex = i-1;
//如果需要比较的前一个元素的索引比0来的大
//或者preIndex所指元素的值大于需要插入的值则后移比较的元素
while (preIndex>=0 && data[preIndex]>nowValue){
data[preIndex+1] = data[preIndex];
preIndex--;
}
data[preIndex+1] = nowValue;
}
4、希尔排序
希尔排序：希尔排序其实是插入排序的改进版，因为在上面插入排序的过程中，我们发现这个排序需要从后面一直往前进行比较，也就是如果值特别小的情况下，可能还需要进行n次的比较才能进入下一次的插入，这样效率上很慢，在这个基础上，这个排序算法增多了一个区间，也就是保证左边区间的值在固定规则上比右边来的小，这样就减少了插入排序可能比较的时间。
代码块：
//间隔区间的值
int grep = data.length/2;
int j;
for (;grep>0;grep/=2){
for (int i = grep;i<data.length;i++){
//nowValue表示当前需要比较元素的值
int nowValue = data[i];
//将当前元素与相隔grep元素的前一个元素进行比较，找到交换点
for (j = i-grep;j>=0 && data[j]>nowValue;j-=grep){
data[j+grep] = data[j];
}
data[j+grep] = nowValue;
}
}
这个代码块最需要注意的其实是最里层的循环，这个循环有两个跳出循环的条件
1、j>=0:这个条件表示当前指针指向的元素没有再相隔grep个元素的前一个元素了，也就是当j为负数的时候，跳出循环，将比较的值赋值给第一个元素。
2、data[j]>nowValue:这个条件又是怎么回事呢，你会发现我们一开始i是从比较小的值开始的，也就是从数组前面的某个位置开始跟相隔grep元素进行比较，在外层，i的值一直增加，也就意味着后面j一开始的值也会变得越来越大，然后我们要比较相隔grep元素，可能就不止一个了，比如你当前元素可能比相隔2*grep的元素还小，那么就不可能直接交换了，基于此也可以看出，这个交换也是基于插入排序的，按照插入排序的思路，需要一步步的往前进行比较，直到找到比当前元素还小的值，就在这个元素后的grep替换元素的值。这个时候，我们应该知道跳出循环后为啥还有个data[j+grep] = nowValue;语句了，因为如果你要插入的元素刚刚好是第一个元素的情况下（相隔grep前没有元素），你跳出了循环，就没可能给第一个元素进行赋值操作，那么最后得到的结果也就是错的，这个地方就是为了解决这种情况。
5、选择排序
选择排序也是一个非常容易理解的排序算法
1、将数组第一个值作为最小值，然后遍历整个数组，找到真正的最小值，然后跟这个值进行替换
2、循环一的步骤，直到数组尾
代码块：
int minValue;
int index;
for (int i = 0 ;i<data.length;i++){
minValue = data[i];
index = i;
for (int j = i+1;j<data.length;j++){
if (data[j]<minValue){
minValue = data[j];
index = j;
}
}
data[index] = data[i];
data[i] = minValue;
}
关于为什么说选择排序也是不稳定排序呢，我举个例子，需要排序{5,4,3,5,2}
发现了什么，我第一次交换的时候，把第一个元素5的值交换到数组最后，然后再继续进行交换的操作，但是数组第四个元素5的值会一直在第一个元素5的值得前面，也就是相同元素值排序之后无法保证前后顺序，所以说选择排序是不稳定的排序。
6、堆排序
堆排序的结构类似于完全二叉树的结构，有两种方式进行排序，一种是小根堆，小根堆的根是完全二叉树中最小的，可以取最小的值保存为数组的第一个元素，以此递归，直到数组结束；另一种是大根堆，大根堆正好和小根堆相反，大根堆的根是完全二叉树中最大的，可以取最大的值保存为数组的最后一个元素，以此递归。
我以大根堆举例，一个完整的节点有它的本身节点、父节点、左孩子、右孩子，而大根堆的结构是要保证父节点肯定比本身节点来的大，并且本身节点、左孩子、右孩子三者中，本身节点的值也必须是最大的，只有实现这的规则才算的上是大根堆。
代码块如下：
public static void heapSort(int[] a) {
int i;
//i的第一个取值很重要，a.length/2-1的值代表有叶子结点的最后一个根节点
//获取到这个节点，我们就可以一层层的往上进行调整
for (i = a.length / 2 -1; i >= 0; i--) {// 构建一个大顶堆
adjustHeap(a, i, a.length - 1);
}
for (i = a.length-1; i > 0; i--) {// 将堆顶记录和当前未经排序子序列的最后一个记录交换
int temp = a[0];
a[0] = a[i];
a[i] = temp;
adjustHeap(a, 0, i - 1);// 将a中前i-1个记录重新调整为大顶堆
}
}
public static void adjustHeap(int[] a, int i, int len) {
int temp, j;
temp = a[i];
//2*i+1代表当前节点的左孩子
for (j = 2 * i+1; j < len; j = j*2+1) {// 沿关键字较大的孩子结点向下筛选
//如果左孩子比右孩子小，则将指针指向右孩子
if (j < len && a[j] < a[j + 1])
++j; // j为关键字中较大记录的下标
//如果左右孩子中最大的一个值不大于根节点的值，则直接跳出
if (temp >= a[j])
break;
//将左右孩子值中最大的一个并且大于根节点的值赋值给当前的根节点
//将指针移到左右孩子中最大的一个，往值大的左或者右二叉树进行调整
a[i] = a[j];
i = j;
}
//将最初始指向的值赋值给当前i指向的节点
a[i] = temp;
}
代码块中需要注意几个点：
第一，我们建立大顶堆需要获取到带有叶子结点的最后一个根节点，从这个根节点开始往回进行调整，而这个节点的值=数组长度/2-1
第二，当我们比较完当前节点和左右孩子中最大的一个值得时候，同时也要保证左右孩子的下一层结构也符合大顶堆的结构，这样就需要一层层的往下进行遍历，直到没有左右孩子为止。
7、归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
1、不断分裂成子序列，递归到左边界大于等于右边界返回；
2、将已经排序好的子序列不断合并，直到没有子序列，返回结果。
代码块：
public int[] sort(int[] source, int left, int right) {
if (left >= right)
return source;
int mid = (right + left) / 2;
//排序左边区域
sort(source, left, mid);
//排序右边区域
sort(source, mid + 1, right);
//返回合并的值
return merge(source, left, mid, right);
}
public int[] merge(int[] source, int left, int mid, int right) {
//申请个临时的数组空间存储排序好的子序列
int[] temp = new int[right - left + 1];
//左子序列第一个元素指针
int i = left;
//右子序列第一个元素指针
int j = mid + 1;
//临时数组空间索引
int index = 0;
//对左右子序列进行比较大小后插入到临时数组
while (i <= mid && j <= right) {
if (source[i] > source[j])
temp[index++] = source[j++];
else
temp[index++] = source[i++];
}
//如果i<=mid说明左子序列已经全部插入到临时数组空间
//将右子序列剩下的值插入到临时数组空间的尾部
while (i <= mid)
temp[index++] = source[i++];
//跟上面正好相反，右子序列已经全部插入，左子序列剩余部分插入操作
while (j <= right)
temp[index++] = source[j++];
//将临时数组数据覆盖本次左右子序列所涉及的数组范围
for (int x = 0; x < temp.length; x++)
source[x + left] = temp[x];
return source;
}
在只有十个元素的数据量情况下排序费时情况
冒泡排序
选择排序
插入排序
希尔排序
归并排序
快速排序
堆排序
总结
本次学习了七种排序算法，受益良多，从上面的时间也可以看出，在数据量比较少的时候，归并排序、快速排序、堆排序其实费时还比较长，所以应该根据不同情况来选择适合的排序算法。
参考链接：
https://www.cnblogs.com/onepixel/articles/7674659.html
https://blog.csdn.net/jianyuerensheng/article/details/51263453
https://blog.csdn.net/qq_27680317/article/details/78549875?utm_source=blogxgwz0
https://blog.csdn.net/qq_39776901/article/details/77387923?utm_source=blogxgwz2
https://blog.csdn.net/min996358312/article/details/68068689?utm_source=blogxgwz1
