十大排序算法全面解析-Java实现
前言
算法就是编程的灵魂，不会算法的程序员只配做码农。之前看到这句话受到一万点暴击伤害！同时也激起了自己的斗志，坦白说作为一个程序员，我一直知道算法的重要性，但是在算法这一块一直做的不够好，甚至除了大学学过这门课程之后就很少去接触它。因为一开始我就给算法贴上了难，烦，不怎么用的标签，现在想来其实都是在逃避问题。所以决定亡羊补牢，从头开始！
文章首发于个人博客【http://www.xiongfrblog.cn】
介绍
算法的学习也是有着阶段性的，从入门到简单，再到复杂，再到简单。最后的简单是当你达到一定高度之后对于问题能够准确的找到最简单的解答。就如同修仙一样，真正的高手一招足以击退万马千军！
算法里边最常用也是最基本的就是排序算法和查找算法了，本文主要讲解算法里边最经典的十大排序算法。在这里我们根据他们各自的实现原理以及效率将十大排序算法分为两大类：
- 非线性比较类排序：非线性是指算法的时间复杂度不能突破(nlogn)，元素之间通过比较大小来决定先后顺序。
- 线性非比较类排序：算法的时间复杂度能够突破(nlogn)，并且不通过比较来对元素排序。
具体分类我们上图说明：
排序算法分类
算法比较
这里给出算法的时间复杂度，空间复杂度以及稳定性的对比整理，同样通过图片的形式给出：
算法比较
在这里给出相关指标的解释
时间复杂度：时间复杂度本意是预估算法的执行时间，但实际上一个程序在计算机上执行的速度是非常快的，时间几乎可以忽略不计了，也就是失去了意义，所以这里意思是算法中执行频度最高的代码的执行的次数。反应当n发生变化时，执行次数的改变呈现一种什么样的规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
稳定性：在排序中对于相等的两个元素a,b。如果排序前a在b的前边，排序之后a也总是在b的前边。他们的位置不会因为排序而改变称之为稳定。反之，如果排序后a,b的位置可能会发生改变，那么就称之为不稳定。
下面就一一对十大算法进行详细的讲解，会给出他们的基本思想，图片演示，以及带有详细注释的源码。（本文所有的排序算法都是升序排序）
1.冒泡排序
1.1 基本思想
冒泡排序可以说是最简单的排序之一了，也是大部分人最容易想到的排序。即对n个数进行排序，每次都是由前一个数跟后一个数比较，每循环一轮， 就可以将最大的数移到数组的最后， 总共循环n-1轮，完成对数组排序。
1.2 图片演示
冒泡排序
1.3 代码展示
public static void bubbleSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
for(int i=0;i<len-1;i++) {
//j控制比较次数，第i次循环内需要比较len-i次
//但是由于是由arr[j]跟arr[j+1]进行比较，所以为了保证arr[j+1]不越界，j<len-i-1
for(int j=0;j<len-i-1;j++) {
//如果前一个数比后一个数大，则交换位置将大的数往后放。
if(arr[j]>arr[j+1]) {
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
2.选择排序
2.1 基本思想
选择排序可以说是冒泡排序的改良版，不再是前一个数跟后一个数相比较， 而是在每一次循环内都由一个数去跟 所有的数都比较一次，每次比较都选取相对较小的那个数来进行下一次的比较，并不断更新较小数的下标 这样在一次循环结束时就能得到最小数的下标，再通过一次交换将最小的数放在最前面，通过n-1次循环之后完成排序。 这样相对于冒泡排序来说，比较的次数并没有改变，但是数据交换的次数大大减少。
2.2 图片演示
选择排序
2.3 代码展示
public static void selectSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
for(int i=0;i<len-1;i++) {
//minIndex 用来保存每次比较后较小数的下标。
int minIndex=i;
//j控制比较次数，因为每次循环结束之后最小的数都已经放在了最前面，
//所以下一次循环的时候就可以跳过这个数，所以j的初始值为i+1而不需要每次循环都从0开始，并且j<len即可
for(int j=i+1;j<len;j++) {
//每比较一次都需要将较小数的下标记录下来
if(arr[minIndex]>arr[j]) {
minIndex=j;
}
}
//当完成一次循环时，就需要将本次循环选取的最小数移动到本次循环开始的位置。
if(minIndex!=i) {
int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
//打印每次循环结束之后数组的排序状态（方便理解）
System.out.println("第"+(i+1)+"次循环之后效果："+Arrays.toString(arr));
}
}
3.插入排序
3.1 基本思想
插入排序的思想打牌的人肯定很容易理解，就是见缝插针。 首先就默认数组中的第一个数的位置是正确的，即已经排序。 然后取下一个数，与已经排序的数按从后向前的顺序依次比较， 如果该数比当前位置排好序的数小，则将排好序的数的位置向后移一位。 重复上一步骤，直到找到合适的位置。 找到位置后就结束比较的循环，将该数放到相应的位置。
3.2 图片演示
插入排序
3.3 代码展示
public static void insertSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//i控制循环次数，因为已经默认第一个数的位置是正确的，所以i的起始值为1，i<len，循环len-1次
for(int i=1;i<len;i++) {
int j=i;//变量j用来记录即将要排序的数的位置即目标数的原位置
int target=arr[j];//target用来记录即将要排序的那个数的值即目标值
//while循环用来为目标值在已经排好序的数中找到合适的位置，
//因为是从后向前比较，并且是与j-1位置的数比较，所以j>0
while(j>0 && target<arr[j-1]) {
//当目标数的值比它当前位置的前一个数的值小时，将前一个数的位置向后移一位。
//并且j--使得目标数继续与下一个元素比较
arr[j]=arr[j-1];
j--;
}
//更目标数的位置。
arr[j]=target;
//打印每次循环结束之后数组的排序状态（方便理解）
System.out.println("第"+(i)+"次循环之后效果："+Arrays.toString(arr));
}
}
4.希尔排序
4.1 基本思想
希尔排序也称为"缩小增量排序"，原理是先将需要排的数组分成多个子序列，这样每个子序列的元素个数就很少，再分别对每个对子序列进行插入排序。在该数组基本有序后 再进行一次直接插入排序就能完成对整个数组的排序。所以，要采用跳跃分割的策略。这里引入“增量”的概念，将相距某个增量的记录两两组合成一个子序列，然后对每个子序列进行直接插入排序， 这样得到的结果才会使基本有序（即小的在前边，大的在后边，不大不小的在中间）。希尔排序就是 直接插入排序的升级版。
4.2 图片演示
希尔排序
4.3 代码展示
public static void shellSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;//数组的长度
int k=len/2;//初始的增量为数组长度的一半
//while循环控制按增量的值来划不同分子序列，每完成一次增量就减少为原来的一半
//增量的最小值为1，即最后一次对整个数组做直接插入排序
while(k>0) {
//里边其实就是升级版的直接插入排序了，是对每一个子序列进行直接插入排序，
//所以直接将直接插入排序中的‘1’变为‘k’就可以了。
for(int i=k;i<len;i++) {
int j=i;
int target=arr[i];
while(j>=k && target<arr[j-k]) {
arr[j]=arr[j-k];
j-=k;
}
arr[j]=target;
}
//不同增量排序后的结果
System.out.println("增量为"+k+"排序之后："+Arrays.toString(arr));
k/=2;
}
}
5.归并排序
5.1 基本思想
总体概括就是从上到下递归拆分，然后从下到上逐步合并。
递归拆分：先把待排序数组分为左右两个子序列，再分别将左右两个子序列拆分为四个子子序列，以此类推直到最小的子序列元素的个数为两个或者一个为止。
逐步合并（一定要注意是从下到上层级合并，可以理解为递归的层级返回）：将最底层的最左边的一个子序列排序，然后将从左到右第二个子序列进行排序，再将这两个排好序的子序列合并并排序，然后将最底层从左到右第三个子序列进行排序..... 合并完成之后记忆完成了对数组的排序操作
5.2 图片演示
归并排序
5.3 代码展示
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {3,8,6,2,1,8};
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
* 递归拆分
* @param arr 待拆分数组
* @param left 待拆分数组最小下标
* @param right 待拆分数组最大下标
*/
public static void mergeSort(int[] arr,int left,int right) {
int mid=(left+right)/2; //中间下标
if(left<right) {
mergeSort(arr,left,mid);//递归拆分左边
mergeSort(arr,mid+1,right);//递归拆分右边
sort(arr,left,mid,right);//合并左右
}
}
/**
* 合并两个有序子序列
* @param arr 待合并数组
* @param left 待合并数组最小下标
* @param mid 待合并数组中间下标
* @param right 待合并数组最大下标
*/
public static void sort(int[] arr,int left,int mid,int right) {
int[] temp=new int[right-left+1]; //临时数组，用来保存每次合并年之后的结果
int i=left;
int j=mid+1;
int k=0;//临时数组的初始下标
//这个while循环能够初步筛选出待合并的了两个子序列中的较小数
while(i<=mid && j<=right) {
if(arr[i]<=arr[j]) {
temp[k++]=arr[i++];
}else {
temp[k++]=arr[j++];
}
}
//将左边序列中剩余的数放入临时数组
while(i<=mid) {
temp[k++]=arr[i++];
}
//将右边序列中剩余的数放入临时数组
while(j<=right) {
temp[k++]=arr[j++];
}
//将临时数组中的元素位置对应到真真实的数组中
for(int m=0;m<temp.length;m++) {
arr[m+left]=temp[m];
}
}
6.快速排序
6.1 基本思想
快速排序也采用了分治的策略，这里引入了‘基准数’的概念。
- 找一个基准数（一般将待排序的数组的第一个数作为基准数）
- 对数组进行分区，将小于等于基准数的全部放在左边，大于基准数的全部放在右边。
- 重复1，2步骤，分别对左右两个子分区进行分区，一直到各分区只有一个数为止。
6.2 图片演示
快速排序
6.3 代码展示
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72,6,57,88,60,42,83,73,48,85};
quickSort(arr,0,9);
System.out.println(Arrays.toString(arr));
}
/**
* 分区过程
* @param arr 待分区数组
* @param left 待分区数组最小下标
* @param right 待分区数组最大下标
*/
public static void quickSort(int[] arr,int left,int right) {
if(left<right) {
int temp=qSort(arr,left,right);
quickSort(arr,left,temp-1);
quickSort(arr,temp+1,right);
}
}
/**
* 排序过程
* @param arr 待排序数组
* @param left 待排序数组最小下标
* @param right 待排序数组最大下标
* @return 排好序之后基准数的位置下标，方便下次的分区
*/
public static int qSort(int[] arr,int left,int right) {
int temp=arr[left];//定义基准数，默认为数组的第一个元素
while(left<right) {//循环执行的条件
//因为默认的基准数是在最左边，所以首先从右边开始比较进入while循环的判断条件
//如果当前arr[right]比基准数大，则直接将右指针左移一位，当然还要保证left<right
while(left<right && arr[right]>temp) {
right--;
}
//跳出循环说明当前的arr[right]比基准数要小，那么直接将当前数移动到基准数所在的位置，并且左指针向右移一位（left++）
//这时当前数（arr[right]）所在的位置空出，需要从左边找一个比基准数大的数来填充。
if(left<right) {
arr[left++]=arr[right];
}
//下面的步骤是为了在左边找到比基准数大的数填充到right的位置。
//因为现在需要填充的位置在右边，所以左边的指针移动，如果arr[left]小于或者等于基准数，则直接将左指针右移一位
while(left<right && arr[left]<=temp) {
left++;
}
//跳出上一个循环说明当前的arr[left]的值大于基准数，需要将该值填充到右边空出的位置，然后当前位置空出。
if(left<right) {
arr[right--]=arr[left];
}
}
//当循环结束说明左指针和右指针已经相遇。并且相遇的位置是一个空出的位置，
//这时候将基准数填入该位置，并返回该位置的下标，为分区做准备。
arr[left]=temp;
return left;
}
7.堆排序
7.1 基本思想
在此之前要先说一下堆的概念，堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。
大顶堆：每个结点的值都大于它的左右子结点的值，升序排序用大顶堆。
小顶堆：每个结点的值都小于它的左右子结点的值，降序排序用小顶堆。
所以，需要先将待排序数组构造成大顶堆的格式，这时候该堆的顶结点就是最大的数，将其与堆的最后一个结点的元素交换。再将剩余的树重新调整成堆，再次首节点与尾结点交换，重复执行直到只剩下最后一个结点完成排序。
7.2 图片演示
堆排序
7.3 代码展示
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72,6,57,88,60,42,83,73,48,85};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
if(arr==null) {
return;
}
int len=arr.length;
//初始化大顶堆（从最后一个非叶节点开始，从左到右，由下到上）
for(int i=len/2-1;i>=0;i--) {
adjustHeap(arr,i,len);
}
//将顶节点和最后一个节点互换位置，再将剩下的堆进行调整
for(int j=len-1;j>0;j--) {
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
/**
* 整理树让其变成堆
* @param arr 待整理的数组
* @param i 开始的结点
* @param j 数组的长度
*/
public static void adjustHeap(int[] arr,int i,int j) {
int temp=arr[i];//定义一个变量保存开始的结点
//k就是该结点的左子结点下标
for(int k=2*i+1;k<j;k=2*k+1) {
//比较左右两个子结点的大小，k始终记录两者中较大值的下标
if(k+1<j && arr[k]<arr[k+1]) {
k++;
}
//经子结点中的较大值和当前的结点比较，比较结果的较大值放在当前结点位置
if(arr[k]>temp) {
arr[i]=arr[k];
i=k;
}else{//说明已经是大顶堆
break;
}
}
arr[i]=temp;
}
/**
* 交换数据
* @param arr
* @param num1
* @param num2
*/
public static void swap(int[] arr, int num1,int num2) {
int temp=arr[num1];
arr[num1]=arr[num2];
arr[num2]=temp;
}
8.计数排序
8.1 基本思想
计数排序采用了一种全新的思路，不再是通过比较来排序，而是将待排序数组中的最大值+1作为一个临时数组的长度，然后用临时数组记录待排序数组中每个元素出现的次数。最后再遍历临时数组，因为是升序，所以从前到后遍历，将临时数组中值>0的数的下标循环取出，依次放入待排序数组中，即可完成排序。计数排序的效率很高，但是实在牺牲内存的前提下，并且有着限制，那就是待排序数组的值必须 限制在一个确定的范围。
8.2 图片演示
计数排序
8.3 代码展示
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72,6,57,88,60,42,83,73,48,85};
countSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void countSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//保存待排序数组中的最大值，目的是确定临时数组的长度（必须）
int maxNum=arr[0];
//保存待排序数组中的最小值，目的是确定最终遍历临时数组时下标的初始值（非必需，只是这样可以加快速度，减少循环次数）
int minNum=arr[0];
//for循环就是为了找到待排序数组的最大值和最小值
for(int i=1;i<len;i++) {
maxNum=maxNum>arr[i]?maxNum:arr[i];
minNum=minNum<arr[i]?minNum:arr[i];
}
//创建一个临时数组
int[] temp=new int[maxNum+1];
//for循环是为了记录待排序数组中每个元素出现的次数，并将该次数保存到临时数组中
for(int i=0;i<len;i++) {
temp[arr[i]]++;
}
//k=0用来记录待排序数组的下标
int k=0;
//遍历临时数组，重新为待排序数组赋值。
for(int i=minNum;i<temp.length;i++) {
while(temp[i]>0) {
arr[k++]=i;
temp[i]--;
}
}
}
9.桶排序
9.1 基本思想
桶排序其实就是计数排序的强化版，需要利用一个映射函数首先定义有限个数个桶，然后将待排序数组内的元素按照函数映射的关系分别放入不同的桶里边，现在不同的桶里边的数据已经做了区分，比如A桶里的数要么全部大于B桶，要么全部小于B桶里的数。但是A，B桶各自里边的数还是乱序的。所以要借助其他排序方式（快速，插入，归并）分别对每一个元素个数大于一的桶里边的数据进行排序。最后再将桶里边的元素按照顺序依次放入待排序数组中即可。
9.2 图片演示
桶排序
9.3 代码展示
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72,6,57,88,60,42,83,73,48,85};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//定义桶的个数，这里k的值要视情况而定，这里我们假设待排序数组里的数都是[0,100)之间的。
int k=10;
//用嵌套集合来模拟桶，外层集合表示桶，内层集合表示桶里边装的元素。
List<List<Integer>> bucket=new ArrayList<>();
//for循环初始化外层集合即初始化桶
for(int i=0;i<k;i++){
bucket.add(new ArrayList<>());
}
//循环是为了将待排序数组中的元素通过映射函数分别放入不同的桶里边
for(int i=0;i<len;i++) {
bucket.get(mapping(arr[i])).add(arr[i]);
}
//这个循环是为了将所有的元素个数大于1的桶里边的数据进行排序。
for(int i=0;i<k;i++) {
if(bucket.size()>1) {
//因为这里是用集合来模拟的桶所以用java写好的对集合排序的方法。
//其实应该自己写一个方法来排序的。
Collections.sort(bucket.get(i));
}
}
//将排好序的数重新放入待排序数组中
int m=0;
for(List<Integer> list:bucket) {
if(list.size()>0) {
for(Integer a:list) {
arr[m++]=a;
}
}
}
}
/**
* 映射函数
* @param num
* @return
*/
public static int mapping(int num) {
return num/10;
}
10.基数排序
10.1基本思想
就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字； 第1个排序关键字，第2个排序关键字，第3个排序关键字......然后，根据子关键字对待排序数据进行排序。
10.2 图片演示
基数排序
10.3 代码展示
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {720,6,57,88,60,42,83,73,48,85};
redixSort(arr,10,3);
System.out.println(Arrays.toString(arr));
}
public static void redixSort(int[] arr, int radix, int d) {
// 缓存数组
int[] tmp = new int[arr.length];
// buckets用于记录待排序元素的信息
// buckets数组定义了max-min个桶
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// 重置count数组，开始统计下一个关键字
Arrays.fill(buckets, 0);
// 将data中的元素完全复制到tmp数组中
System.arraycopy(arr, 0, tmp, 0, arr.length);
// 计算每个待排序数据的子关键字
for (int j = 0; j < arr.length; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
// 按子关键字对指定的数据进行排序
for (int m = arr.length - 1; m >= 0; m--) {
int subKey = (tmp[m] / rate) % radix;
arr[--buckets[subKey]] = tmp[m];
}
rate *= radix;
}
}
