【算法之八大排序（带图解、复杂度分析）】 优化版冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序、堆排序。

前言

为了准备即将到来的面试，我对算法进行完整的复习，以及对于基础知识点的梳理。复习课程数据结构和算法:尚硅谷av54029771，下面是所有排序算法，带图解，以及思路分析。希望我们都能在面试中，顺利的写出来。理解远远比死背下来更加重要！！此博客相对比较长，如果你只想看其中的几个部分，可以从目录点进去。

排序算法介绍

排序算法分类

不希望当面试官问你，都有什么排序的时候，你只能说出冒泡，快速，选择，和堆排序，而是内部排序以及外部排序，内部排序包含什么什么，外部排序包含什么什么，这样一来,B格提升了好多有没有！！所以，首先，要把下面的记住！！

内部排序

指将需要处理的所有数据都加载到内部存储器中进行排序,我们通常所见的都是内部排序

• 插入排序
   1)直接插入排序
   2）希尔排序
• 选择排序
   1）简单选择排序
   2）堆排序
• 交换排序
   1)冒泡排序
   2)快速排序

外部排序

数据量过大，无法全部加载到内存中，需要借助外部存储进行排序

下面，开始正文！！！

冒泡排序

冒泡排序进行的排序过程

如图所示，线从这些中依次找到最大的，然后将未排序的继续找最大的，直到所有的变成有序的。

一般冒泡排序

//冒泡排序算法
int[] a=new int[]{9,8,6,5,7,3,2,2,0};
int temp=0;
for(int i=0;i<a.length;i++){
    flag=true;//必须要有，如果没有就不会跳出循环
    for(int j=0;j<a.length-i-1;j++){//注意这里是j<a.length-i-1 如果没有减1会发生数组越界
        if(a[j]>a[j+1]){
            temp=a[j];
            a[j]=a[j+1];
            a[j+1]=temp;
        }
    }
}
System.out.println(Arrays.toString(a));//用到java.util包中的Arrays

优化冒泡排序算法

//冒泡排序优化算法
int[] a=new int[]{9,8,6,5,7,3,2,2,0};
int temp=0;
boolean flag=true;//设置flag用来判断后面的是否有序，如果已经有序，则不不需要多次判断。
for(int i=0;i<a.length;i++){
    flag=true;//必须要有，如果没有就不会跳出循环
    for(int j=0;j<a.length-i-1;j++){//注意这里是j<a.length-i-1 如果没有减1会发生数组越界
        if(a[j]>a[j+1]){
            flag=false;
            temp=a[j];
            a[j]=a[j+1];
            a[j+1]=temp;
        }
    }
    if(flag){
        break;
    }
}
System.out.println(Arrays.toString(a));//用到java.util包中的Arrays

• 注意：这里加入flag表明，如果在判断中没有进行交换，则说明后面的已经有序，就不需要继续循环。例如{9，1，2，3，4，5，6，7，8}，进行第一次交换后变成{1.2.3.4.5.6.7.8.9}，开始第二次时候，发现没有任何交换，因为这时候已经呈有序状态。

选择排序

（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

选择排序图解

说明：

1. 选择排序一共有数组大小-1伦排序

2. 每1轮排序，又是一个循环，循环的规则

   • 先假定当前这个数是最小数
   • 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到小标
   • 当遍历到数组的最后时，就得到本轮最小数和下标
   • 交换

选择排序代码实现

public static void selectSort(double[] array){
    double min=array[0];
    int temp=0;
    for(int i=0;i<array.length;i++){
        min=array[i];
        temp=i;
        for(int j=i;j<array.length;j++){
            if(array[j]<min){
                min=array[j];
                temp=j;
            }
        }
        array[temp]=array[i];
        array[i]=min;
    }
    System.out.println(Arrays.toString(array));
}

插入排序

把n个待排序的元素堪称为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把他的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中适当的位置，使之成为新的有序表。

插入排序图解

说明：主要体现在，每找到一个数，就找到他相应的位置，在他之后的需要进行后移。

代码实现

public static void insertSort(double[] array){
    double temp=0;
    for(int i=1;i<array.length;i++){
        temp=array[i];
        for (int j=0;j<i;j++){
            if(array[i]<array[j]){//找到将要插入的点。
              int k=i;
              while (k>j){//找到过后，剩下的所有右移
                  array[k]=array[k-1];
                  k--;
              }
              array[j]=temp;
              break;
            }
        }
    }
    System.out.println(Arrays.toString(array));
}

希尔排序

• 希尔排序是一种插入排序，是一个更高效的版本，也称缩小增量排序。
• 希尔排序是把记录按下标的一定量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减到1时，整个文件恰被扽成一组，算法便终止。
  

希尔排序图解

希尔排序的两种方法

• 交换法
• 移动法（优化版）

希尔排序交换法代码实现

public static void shell(double[] array){
        double temp=0;
        //每次gap都除以2 表示每次不断分组，直到分组为1
        for(int gap=array.length/2;gap>0;gap/=2){
            for (int i=gap;i<array.length;i++){
                //这一段代码是交换式
               for(int j=i-gap;j>=0;j-=gap) {
                 if (array[j] > array[j + gap]) {
                        temp = array[j];
                       array[j] = array[j + gap];
                        array[j + gap] = temp;
                   }
              
            
        }
        System.out.println(Arrays.toString(array));
    }

希尔排序移动法代码实现（优化版）

public static void shell(double[] array){
        double temp=0;
        //每次gap都除以2 表示每次不断分组，直到分组为1
        for(int gap=array.length/2;gap>0;gap/=2){
            for (int i=gap;i<array.length;i++){
                //移动法（对此进行优化过的）
                int j=i;
                temp=array[j];
                while (j-gap>=0&&temp<array[j-gap]){
                    array[j]=array[j-gap];
                    j-=gap;
                }
                array[j]=temp;
            }
        }
        System.out.println(Arrays.toString(array));
    }

快速排序

• 快速排序是对冒泡排序的一种改进。
• 其基本思想是通过一趟排序要将排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归，以此达到震哥哥数据变成有序序列。
  

快速排序图解

说明：每次都选取最前面的为基准点，从左到右找到第一个大于基准点的和从右到左找到第一个小于基准点的进行交换。最终将基准点和左右两个指针碰面的地方数据进行交换。

快速排序代码实现

public static void quickSort(double [] array,int left,int right){
    if(left>right)return;
    //以中间的为基准点
    int i=left,j=right;
    double key=array[i];
    double temp=0;//用来交换的点。
    while (i!=j){
        //当队尾元素大于基准数据时候，向前挪动j指针
        while (j>i&&array[j]>=key){
            j--;
        }
        //当队首元素小于temp时候，向前挪动。
        while (j>i&&array[i]<=key){
            i++;
        }
        if(j>i){
            temp=array[j];
            array[j]=array[i];
            array[i]=temp;
        }
    }
    //最后确定位置
    array[left]=array[j];
    array[j]=key;
    quickSort(array,left,j-1);
    quickSort(array,j+1,right);
}

归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略，分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之。

归并排序图解

归并排序代码实现

//归并排序 分+合
public static void mergeSort(double [] arr,int left,int right,double[] temp){
    if(left>=right)return;
    int mid=(left+right)/2;
    mergeSort(arr,left,mid,temp);
    mergeSort(arr,mid+1,right,temp);
    merge(arr,left,mid,right,temp);
}
//归并排序 合
public static void merge(double[] arr,int left,int mid,int right,double[] temp){
    int i=0;
    int j=mid+1;
    int start=left;//记录一开始的位置
    //合并中
    while (left<=mid&&j<=right){
        if(arr[left]<arr[j]){
            temp[i++]=arr[left];
            left++;
        }else {
            temp[i++]=arr[j];
            j++;
        }
    }
    //表示前半段的已经全部放入temp中
        while (j<=right){
            temp[i++]=arr[j];
            j++;


    }//如果后半段的没有完的话
        while (left<=mid){
            temp[i++]=arr[left];
            left++;
        }


    //开始复制temp数组
    for(int k=0;k<i;k++){
        arr[start++]=temp[k];
    }
}

基数排序

基数排序的基本介绍

• 基数排序（redix sort）是属于“分配式排序”（distribution sort),又成为“桶子法”（bucket sort）货bin sort,顾名思义，它就是通过键值的各个位的值，将要排序的元素分配到这些“桶”中，达到排序的作用。
• 基数排序法是属于稳定性的程序，基数排序法的是效率高的稳定性排序法
• 基数排序是桶排序的扩展
• 基数排是这样实现的：将整数按照位数切割成不同的数字，然后按每个位数分别比较。

基数排序的基本思想

将所有待比较的数值统一为同样的数位长度，数位较短的数前面补0.然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

• 说明

1. 基数排序是对传统桶排序的扩展，速度很快
2. 基数排序是经典的空间换时间的方法，占用内存很大，当对海量数据排序时容易造成OutofMemoryError
3. 基数排序是稳定的。
4. 注意：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若讲过排序，这些记录的相对次序保持不变，即在原序列中。r[i]=r[j],且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序是算法稳定的；否则称为不稳定的
5. 有负数的数组，不用基数排序来进行排序。

基数排序代码实现

public static void bucketSort(int[] array){
    int[][] bucket=new int[10][array.length];
    int rounds=10;//轮数，第一次为10
    int [] bucketElementCount=new int[10];//每个篮子的第几个
    for(int digits=0;digits<3;digits++){//digitis表示次方，每次都是先除以10在取余进行比较
        int divisor= (int) Math.pow(10,digits);
        //第n轮
        for(int i=0;i<array.length;i++){
            int num=array[i]/divisor%rounds;
            bucket[num][bucketElementCount[num]]=array[i];
            bucketElementCount[num]++;
        }
        //复制结果到array里面
        for (int i=0,k=0;i<10&&k<array.length;i++){
            //如果bucketElementCount[num]里面有值将里面的值复制到array里面
            if(bucketElementCount[i]!=0){
                int point=0;
                while (bucketElementCount[i]>0){
                    array[k++]=bucket[i][point++];
                    bucketElementCount[i]--;
                }
            }
        }
    }
    System.out.println(Arrays.toString(array));
}

堆排序

1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，他的最好，最坏，平均时间复杂度均为O(nlogn),它也是不稳定排序。
2. 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。注意：没有要求结点的左孩子和有孩子的值的大小关系。
3. 每个结点的值度小于或等于其左右孩子结点的值，称为小顶堆
   

堆排序的基本思想

• 将待排序序列构造成一个大顶堆
• 此时，整个序列的最大值就是堆顶的根节点
• 将其与末尾元素进行交换，此时末尾就是最大值。
• 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列

堆排序图解

说明：堆排序好多地方都讲的不是很清楚，想要掌握最重要的还是要自己多画一画，理解最重要！

堆排序的代码实现

//堆排序
public static void heapSort(double arr[]){
    //进行第一轮，大致有序的堆就形成了，后序只需要比较堆顶。
   for(int i=(arr.length/2)-1;i>=0;i--){
        adjustHeap(arr,i,arr.length);
    }
    //System.out.println("堆排序"+Arrays.toString(arr));
   //交换操作。


    for(int i=1;i<arr.length;i++){
        double temp=arr[0];
        arr[0]=arr[arr.length-i];
        arr[arr.length-i]=temp;
        adjustHeap(arr,0,arr.length-i);
       //System.out.println("堆排序"+Arrays.toString(arr));
    }
    System.out.println("堆排序"+Arrays.toString(arr));
}
//将一个数组（二叉树）调整成一个大顶堆
public static void adjustHeap(double []arr,int i,int length){
    //暂时存放这个结点
    double temp=arr[i];
    //int k;
    for(int k=2*i+1;k<length;k=2*i+1){
        if(k+1<length&&arr[k+1]>arr[k]){
            //如果右子结点大于左子结点，那么把k值给右子结点
            k++;
        }//判断相比之下比较大的子节点和父节点谁大，如果小于的话交换
        if(temp<arr[k]){
            arr[i]=arr[k];
            //换父节点，继续遍历
            i=k;
            arr[k]=temp;
        }else {
            break;
        }
        //arr[k]=temp;
    }
}

时间复杂度表格

自己做的表，有点少女心，嘻嘻，但是掌握知识还是最重要der~,这个表格最好要记住哦，因为很多地方考！！！所以就划重点啦！

小结

这是这一段时间，我自己学习，总结，并且把所有都上手敲一遍。虽然好多人都觉得自己已经理解的很透彻了，但是当面试官让你写一遍，可能还是要抓耳挠腮好久，所以说多敲几遍是没有任何问题。我写笔记，然后过两天再把我写的笔记搬运到博客上，这样子我可以有再一次机会去复习。不要看不起基础哦，千里之堤，溃于蚁穴，往往基础的才是最重要的！！我们一起努力吧，我的学习+复习之路还很长，希望看到我博客的人，我们能一起努力！！成为更加优秀我们。