首发公众号「bigsai」
文章已收录在 我的Github bigsai-algorithm
绪论
身为程序员，十大排序是是所有合格程序员所必备和掌握的，并且热门的算法比如快排、归并排序还可能问的比较细致，对算法性能和复杂度的掌握有要求。bigsai作为一个负责任的Java和数据结构与算法方向的小博主，在这方面肯定不能让读者们有所漏洞。跟着本篇走，带你捋一捋常见的十大排序算法，轻轻松松掌握！
首先对于排序来说大多数人对排序的概念停留在冒泡排序或者JDK中的Arrays.sort()，手写各种排序对很多人来说都是一种奢望，更别说十大排序算法了，不过还好你遇到了本篇文章！
对于排序的分类，主要不同的维度比如复杂度来分、内外部、比较非比较等维度来分类。我们正常讲的十大排序算法是内部排序，我们更多将他们分为两大类：基于比较和非比较这个维度去分排序种类。
- 非比较类的有桶排序、基数排序、计数排序。也有很多人将排序归纳为8大排序，那就是因为基数排序、计数排序是建立在桶排序之上或者是一种特殊的桶排序，但是基数排序和计数排序有它特有的特征，所以在这里就将他们归纳为10种经典排序算法。而比较类排序也可分为
- 比较类排序也有更细致的分法，有基于交换的、基于插入的、基于选择的、基于归并的，更细致的可以看下面的脑图。
交换类
冒泡排序
冒泡排序，又称起泡排序，它是一种基于交换的排序典型，也是快排思想的基础，冒泡排序是一种稳定排序算法，时间复杂度为O(n^2).基本思想是：循环遍历多次每次从前往后把大元素往后调，每次确定一个最大(最小)元素，多次后达到排序序列。(或者从后向前把小元素往前调)。
具体思想为(把大元素往后调)：
- 从第一个元素开始往后遍历，每到一个位置判断是否比后面的元素大，如果比后面元素大，那么就交换两者大小，然后继续向后，这样的话进行一轮之后就可以保证最大的那个数被交换交换到最末的位置可以确定。
- 第二次同样从开始起向后判断着前进，如果当前位置比后面一个位置更大的那么就和他后面的那个数交换。但是有点注意的是，这次并不需要判断到最后，只需要判断到倒数第二个位置就行(因为第一次我们已经确定最大的在倒数第一，这次的目的是确定倒数第二)
- 同理，后面的遍历长度每次减一，直到第一个元素使得整个元素有序。
例如2 5 3 1 4排序过程如下：
实现代码为：
public void maopaosort(int[] a) {
// TODO Auto-generated method stub
for(int i=a.length-1;i>=0;i--)
{
for(int j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
int team=a[j];
a[j]=a[j+1];
a[j+1]=team;
}
}
}
} 快速排序
快速排序是对冒泡排序的一种改进，采用递归分治的方法进行求解。而快排相比冒泡是一种不稳定排序,时间复杂度最坏是O(n^2),平均时间复杂度为O(nlogn),最好情况的时间复杂度为O(nlogn)。
对于快排来说，基本思想是这样的
- 快排需要将序列变成两个部分，就是序列左边全部小于一个数，序列右面全部大于一个数，然后利用递归的思想再将左序列当成一个完整的序列再进行排序，同样把序列的右侧也当成一个完整的序列进行排序。
- 其中这个数在这个序列中是可以随机取的，可以取最左边，可以取最右边，当然也可以取随机数。但是通常不优化情况我们取最左边的那个数。
实现代码为：
public void quicksort(int [] a,int left,int right)
{
int low=left;
int high=right;
//下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！
if(low>high)//作为判断是否截止条件
return;
int k=a[low];//额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
{
while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
{
high--;
}
//这样就找到第一个比它小的了
a[low]=a[high];//放到low位置
while(low<high&&a[low]<=k)//在low往右找到第一个大于k的，放到右侧a[high]位置
{
low++;
}
a[high]=a[low];
}
a[low]=k;//赋值然后左右递归分治求之
quicksort(a, left, low-1);
quicksort(a, low+1, right);
} 插入类排序
直接插入排序
直接插入排序在所有排序算法中的是最简单排序方式之一。和我们上学时候 从前往后、按高矮顺序排序，那么一堆高低无序的人群中，从第一个开始，如果前面有比自己高的，就直接插入到合适的位置。一直到队伍的最后一个完成插入整个队列才能满足有序。
直接插入排序遍历比较时间复杂度是每次O(n),交换的时间复杂度每次也是O(n),那么n次总共的时间复杂度就是O(n^2)。有人会问折半(二分)插入能否优化成O(nlogn),答案是不能的。因为二分只能减少查找复杂度每次为O(logn),而插入的时间复杂度每次为O(n)级别，这样总的时间复杂度级别还是O(n^2).
插入排序的具体步骤：
- 选取当前位置(当前位置前面已经有序) 目标就是将当前位置数据插入到前面合适位置。
- 向前枚举或者二分查找，找到待插入的位置。
- 移动数组，赋值交换，达到插入效果。
实现代码为：
public void insertsort (int a[])
{
int team=0;
for(int i=1;i<a.length;i++)
{
System.out.println(Arrays.toString(a));
team=a[i];
for(int j=i-1;j>=0;j--)
{
if(a[j]>team)
{
a[j+1]=a[j];
a[j]=team;
}
else {
break;
}
}
}
} 希尔排序
直接插入排序因为是O(n^2),在数据量很大或者数据移动位次太多会导致效率太低。很多排序都会想办法拆分序列，然后组合，希尔排序就是以一种特殊的方式进行预处理，考虑到了数据量和有序性两个方面纬度来设计算法。使得序列前后之间小的尽量在前面，大的尽量在后面，进行若干次的分组别计算，最后一组即是一趟完整的直接插入排序。
对于一个长串，希尔首先将序列分割(非线性分割)而是按照某个数模(取余这个类似报数1、2、3、4。1、2、3、4)这样形式上在一组的分割先各组分别进行直接插入排序,这样很小的数在后面可以通过较少的次数移动到相对靠前的位置。然后慢慢合并变长，再稍稍移动。
因为每次这样插入都会使得序列变得更加有序，稍微有序序列执行直接插入排序成本并不高。所以这样能够在合并到最终的时候基本小的在前，大的在后，代价越来越小。这样希尔排序相比插入排序还是能节省不少时间的。
实现代码为：
public void shellsort (int a[])
{
int d=a.length;
int team=0;//临时变量
for(;d>=1;d/=2)//共分成d组
for(int i=d;i<a.length;i++)//到那个元素就看这个元素在的那个组即可
{
team=a[i];
for(int j=i-d;j>=0;j-=d)
{
if(a[j]>team)
{
a[j+d]=a[j];
a[j]=team;
}
else {
break;
}
}
}
} 选择类排序
简单选择排序
简单选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
实现代码为：
public void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i; // 最小位置
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j; // 更换最小位置
}
}
if (min != i) {
swap(arr, i, min); // 与第i个位置进行交换
}
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} 堆排序
对于堆排序，首先是建立在堆的基础上，堆是一棵完全二叉树，还要先认识下大根堆和小根堆，完全二叉树中所有节点均大于(或小于)它的孩子节点，所以这里就分为两种情况
- 如果所有节点大于孩子节点值，那么这个堆叫做大根堆，堆的最大值在根节点。
- 如果所有节点小于孩子节点值，那么这个堆叫做小根堆，堆的最小值在根节点。
堆排序首先就是建堆，然后再是调整。对于二叉树(数组表示)，我们从下往上进行调整，从第一个非叶子节点开始向前调整，对于调整的规则如下：
建堆是一个O(n)的时间复杂度过程，建堆完成后就需要进行删除头排序。给定数组建堆(creatHeap)
①从第一个非叶子节点开始判断交换下移(shiftDown)，使得当前
京公网安备 11010502036488号