图解常见排序算法

1. 冒泡排序

冒泡排序属于交换排序的一种，从数组的第一个角标开始逐个与后面的元素进行比较，如果小于就将其置换

首先取出第一个元素，与后面的元素挨个比较，如果大于后面的某个元素就将两个元素位置互换，然后继续比较直到最后一个。第二轮从第二个元素开始比较、第三轮从第三个以此类推，最后一轮比较完毕就会形成一个有序数组

        int[] arr = {5,1,2,9,7};

        //轮数

        for (int i=0;i<arr.length-1;i++){

            //从第i个元素开始比较

            for (int j = i+1;j<arr.length;j++){

                if(arr[i]>arr[j]){

                    //交换位置

                    int temp = arr[i];

                    arr[i] = arr[j];

                    arr[j] = temp;

                }

            }

            System.out.println("第"+(i+1)+"轮："+Arrays.toString(arr));

        }

        System.out.println(Arrays.toString(arr));

打印结果：

第1轮：[1, 5, 2, 9, 7]

第2轮：[1, 2, 5, 9, 7]

第3轮：[1, 2, 5, 9, 7]

第4轮：[1, 2, 5, 7, 9]

[1, 2, 5, 7, 9]

2. 快速排序

从数组中选取一个标准数，小于标准数的元素放在左边、大于标准数的元素放在右边，然后把分开的两个数组再进行以上操作，此步骤可通过递归来实现。

选择5为标准数进行分边，将1、2放在左边，7、9放在右边，通过递归将左右两个数组再次进行分边，当不能再分即数组块<2时跳出方法，以此类推最后会得出一个有序数组。代码部分：

public static void quickSort(int[] arr,int start,int end){

        //递归结束条件

        if(start>=end){

            return;

        }

        int standard = arr[start];//选取第start个元素为标准数

        int low = start;//低位指针

        int high = end;//高位指针

        //通过一个循环将小的数字分配到标准数左边、

        //大的放在右边，标准数放在中间

        //循环的结束条件为两个指针碰撞即low==high，

        while (low<high){

            //首先从高位开始找比标准数小的数字

            while (low<high&&standard<=arr[high]){

                //将高位角标+1继续比较

                high--;

            }

            //找到比标准数小的数字放在low角标处,此时的low即start

            arr[low] = arr[high];


            //从低位开始找比标准数大的数字

            while (low<high&&arr[low]<=standard){

                //将低位指针+1继续比较

                low++;

            }

            //找到比标准数大的数字放在high角标处

            arr[high] = arr[low];

        }

        //能执行到这说明low==high，将标准值放在low/high角标中

        arr[low] = standard;

        System.out.println("start:"+start+"--end:"+end+"--"+Arrays.toString(arr));

        //执行完以上步骤后就完成了第一轮数字分配，

        //通过递归将分开的两个数组再次进行数组分配

        quickSort(arr,start,low-1);//将左边数组进行数字分配

        quickSort(arr,low+1,end);//将右边数组进行数字分配

    }

执行如下代码：

 int[] arr = {5,1,7,9,2};

 quickSort(arr,0,arr.length-1);

 System.out.println("-------------");

 System.out.println(Arrays.toString(arr));

打印结果

start:0--end:4--[2, 1, 5, 9, 7]

start:0--end:1--[1, 2, 5, 9, 7]

start:3--end:4--[1, 2, 5, 7, 9]

-------------

[1, 2, 5, 7, 9]

3. 直接插入排序

从第二个元素开始与第一个元素进行比较，如果小于第一个元素则交换位置。然后从第三个元素开始与第二个元素进行比较，如果小于第二个元素进行位置互换，再拿着第二个元素跟第一个元素比较，大于第一个元素就交换位置，以此类推

     int[] arr = {5,1,7,9,2};

     for (int i=1;i<arr.length;i++){

            //如果当前遍历数字小于前一个数字

            if(arr[i]<arr[i-1]){

                int temp = arr[i];//记录下来当前遍历的数字

                int j;

                //将temp与前面数字进行比较，

                //如果小于前面数字将前一数字，

                //就将当前数字设置成与前一数组相同

                for (j = i-1;j>=0&&arr[j]>temp;j--){

                    arr[j+1] = arr[j];

                }

                //最后还要将temp放在j+1的位置

                arr[j+1] = temp;

            }

     }

    System.out.println(Arrays.toString(arr));

打印结果：

[1, 2, 5, 7, 9]

代码可能与上面的文字描述有些出入，但目的都是为了交换位置。

4. 希尔排序

首先获取到数组长度，将长度/2得到一个步长，举个例子来说明一下步长的作用，假如有一个长度为5的数组，那么步长就是2，将第4个元素和第2(4-步长)个元素进行比较，小于前面数字则交换位置，再将第2个元素与第0(2-步长)个元素比较，小于前面数字交换位置。然后再将第3个和第一个比较，以此类推，比较完一轮后将步长/2进行下一轮比较。

• 
  
• 第一轮：将5、7、2和1、9进行比较得到第二轮
  
• 第二轮：将2、1、5、9、7按步长为1进行比较
  

        int[] arr = {5,1,7,9,2};

        //遍历步长,每遍历一轮步长除2，直到小于等于0跳出循环

        for (int d = arr.length/2;d>0;d/=2){


            //遍历每个元素

            for (int i = d;i<arr.length;i++){

                //遍历本步长组中的元素

                for (int j=i-d;j>=0;j-=d ){

                    //将当前元素与加上步长的元素比对

                    //如果当前元素大就交换位置

                    if (arr[j]>arr[j+d]){

                        //交换位置

                        int temp = arr[j];

                        arr[j] = arr[j+d];

                        arr[j+d] = temp;

                    }

                }

            }

            System.out.println("d:"+d+Arrays.toString(arr));

        }

        System.out.println(Arrays.toString(arr));

打印结果:

d:2[2, 1, 5, 9, 7]

d:1[1, 2, 5, 7, 9]

[1, 2, 5, 7, 9]

第一个for循环步长的轮数，第二个for循环从步长开始遍历后面每个元素，第三个for循环用于遍历一个步长组然后交换位置。

5. 简单选择排序

选择排序跟冒泡排序类似，从一个数字开始往后遍历，选出最小值并记录其角标然后第一位进行位置交换，再从第二个数字开始做以上操作以此类推

    int[] arr = {2,3,5,1};

    for (int i=0;i<arr.length-1;i++){

            int index = i;

            for (int j=i+1;j<arr.length;j++){

                //记录本轮最小值角标

                if(arr[j]<arr[index]){

                    index = j;

                }

            }

            //交换位置

            if(i!=index) {

                int temp = arr[i];

                arr[i] = arr[index];

                arr[index] = temp;

            }

            System.out.println("第"+(i+1)+"轮："+Arrays.toString(arr));

      }

     System.out.println("----------------");

     System.out.println(Arrays.toString(arr));

打印结果：

第1轮[1, 3, 5, 2]

第2轮[1, 2, 5, 3]

第3轮[1, 2, 3, 5]

----------------

[1, 2, 3, 5]

6. 归并排序

归并排序就是将一堆无序数字分成两部分，左右两边都保证有序，最后再将两边有序数字进行排序

通过递归的方式将数组拆分直到被拆分的数组长度<=1未知，原始数组可拆分为A和B，A数组又可拆分为C和D，D数组又可拆分为G和H，数组G和H长度都为1所以不能再往下进行拆分，因为数组G和H长度都为1所以可视为两个数组都是有序的，然后通过归并算法将G和H合并成一个有序数组，此时数组D就变成了[1,2]，再通过归并算法将C和D合并成有序数组，此时A就变成了[1,2,5]，依次类推最终就可以实现排序功能。

//归并算法就是将左右两边的两个有序数组归并成一个有序数组

public static void merge(int[] arr,int low,int middle,int high){

        int[] temp = new int[high-low+1];//创建一个临时数组

        int i = low;//第一个数组需要遍历的角标

        int j = middle+1;//第二个数组需要遍历的角标

        int index = 0;//记录临时数组的下表

        //遍历两个数组，取出小的数字放入临时数组中

        while (i<=middle&&j<=high){

            //把小的数据放入临时数组中，小的一方角标+1

            if(arr[i]<arr[j]){

                temp[index] = arr[i];

                i++;

            }else {

                temp[index] = arr[j];

                j++;

            }

            //临时数组角标+1

            index++;

        }

        //处理右边多余的数据

        while (j<=high){

            temp[index] = arr[j];

            j++;

            index++;

        }

        //处理左边多余的数据

        while (i<=middle){

            temp[index] = arr[i];

            i++;

            index++;

        }


        //将临时排好序的临时数组放入到原数组

        for (int k=0;k<temp.length;k++){

            arr[low+k] = temp[k];

        }

    }

重点说一下下面的两个取多余数据的代码，首先这两个while循环是互斥的，什么时候会执行这两个while循环呢？假如左边的所有数据都小于右边的第一个数据，此时会将左边数组全部放到临时数组中，当放入最后一个元素后左边数组的角标i已经>middle了，会跳出第一个while循环，但是右面的元素还没有放入到临时数组，所以要将右边多余的数字放入到临时数组。其他部分注释标的都很清楚就不一一叙述了，下面来看数组拆分的算法：

    public static void mergeSort(int[] arr,int low,int high){

        //递归结束条件

        if(high<=low){

            return;

        }

        int middle = (high+low)/2;

        //处理左边

        mergeSort(arr,low,middle);

        //处理右边

        mergeSort(arr,middle+1,high);

        //归并

        merge(arr,low,middle,high);

    }

    ...

    //以下代码在main()方法中运行

    int[] arr = {2,3,5,1,11,2,15};

    mergeSort(arr,0,arr.length-1);

    System.out.println(Arrays.toString(arr));

通过递归的方式拆分数组，然后结合上面写的归并算法进行排序。下面来看代印结果：

[1, 2, 2, 3, 5, 11, 15]

7. 基数排序

创建一个长度为10的二维数组，遍历无序数组，将个位数为0 - 9的放在二维数组的第0-9个位置，然后按顺序将元素取出，再将十位数为0 - 9的放在二维数组的第0-9个位置，然后再取出，以此类推最后会得到一个有序数组

首先创建一个二维数组也就是图中中间的那个数组，然后遍历需要排序的数组将个位数为0 - 9的元素放入到二维数组中0 - 9位置，然后再从前到后将元素逐个取出，这样第一轮就完成了，然后再进行下一轮，进行的轮数就是最大数的长度。

 //基数排序

    public static void radixSort(int[] arr){

        //存数组中最大的数，目的获取其位数

        int max = Integer.MIN_VALUE;

        for (int x:arr){

            if(x>max){

                max = x;

            }

        }

        //最大值长度

        int maxLength = (max+"").length();

        //创建一个二维数组存储临时数据

        int[][] temp = new int[10][arr.length ];

        //创建一个数组，用来记录temp内层数组存储元素的个数

        int[] count = new int[10];

        //将数据放入二维数组中

        for (int i =0,n=1;i<maxLength;i++,n*=10){

            for (int j=0;j<arr.length;j++){

                int number = arr[j]/n;

                //将number放入指定数组的指定位置

                temp[number][count[number]] = arr[j];

                //将count数组中记录元素个数的元素+1

                count[number]++;

            }

            //从二维数组中取数据

            int index = 0;

            for (int x=0;x<count.length;x++){

                if(count[x]!=0){

                    for (int y=0;y<count[x];y++){

                        arr[index] = temp[x][y];

                        index++;

                    }

                    count[x] = 0;

                }

            }

        }

    }

    ...

    //以下代码在main()方法中运行

    int[] arr = {11,2,6,552,12,67,88,72,65,23,84,17};

    radixSort(arr);

    System.out.println(Arrays.toString(arr));

• 
  
• 首先遍历数组取出最大值，通过最大值确定轮数
  
• 创建一个二维数组和一个存放二维数组每个角标中元素个数的数组
  
• 将元素放入到二维数组中指定的位置
  
• 从二维数组中逐个将元素取出
  

打印结果：

[2, 6, 11, 12, 17, 23, 65, 67, 72, 84, 88, 552]