【数据结构和算法一】常用排序算法

末蓝、 2022-12-22 11:23 185阅读 0赞

### 文章目录 ###

*  介绍
 *  冒泡排序
 *   *  优化
 *  插入排序
 *  选择排序
 *  希尔排序
 *  快速排序
 *  归并排序
 *  基数排序（桶排序）
 *   *  注意

# 介绍 #

如下的，代码都是基于从小到大排序的思路进行分析的。从大到小的话思想是一致的，只有某一小部分的代码改下即可。

# 冒泡排序 #

基本思想是：通过比较相邻元素的顺序进行交换。如果从小到大排序，就把大的一次向后移动，当循环一次时，最大的就到最后了。  
如下所示：

> 第一轮循环介绍如下，两个指针，一个指向当前，一个指向后一个，判断当前的数是不是比后面下，小的话就交换，不小就后移一位继续比较。

![在这里插入图片描述][20201120103843386.png_pic_center]

> 指针后移发小小了就进行交换  
> ![在这里插入图片描述][20201120104134837.png_pic_center]

![在这里插入图片描述][20201120104214856.png_pic_center]

> 继续比较，以此类推，第一轮虚幻完毕之后，就会将最大的移动到了最后。

**代码**  
代码描述：

> 第0轮，内层循环5次  
> 第1轮内层循环 4 次  
> 第k轮内层循环 length - 1 -k次  
> 总共需要几轮？length - 1 轮，因为最后一个数不用冒泡了

//冒泡排序
       public static void bubbleSort(int[] arr){ 
           int temp = 0;
           for(int i = 0;i<arr.length-1;i++){ 
               for(int j = 0;j<arr.length-1-i;j++){ 
                   if(arr[j] > arr[j+1]){ 
                       //交换
                       temp = arr[j];
                       arr[j] = arr[j+1];
                       arr[j+1] = temp;
                   }
               }
           }
       }

## 优化 ##

> 如果循环一次发现没有元素发生变化，就说明已经有序了。（相当于优化，没发生变化就退出了，不排了）

改进代码

//冒泡排序
        public static void bubbleSort(int[] arr){ 
            boolean flag = false;
            int temp = 0;
            for(int i = 0;i<arr.length-1;i++){ 
                for(int j = 0;j<arr.length-1-i;j++){ 
                    if(arr[j] > arr[j+1]){ 
                        //交换
                        temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        flag = true;
                    }
                }
                if(!flag){ 
                    break;
                }else{ 
                    flag = false;
                }
            }
        }

# 插入排序 #

插入排序的思想是：分为有序序列和无序序列。每次找到待插入的索引，将其后面的元素后移，留出坑位，待插入元素放进去  
第一步：默认第一个数就是有序的，所以有序列表有5 无序列表有 7 -1 2 4  
![在这里插入图片描述][2020112011300478.png_pic_center]  
第二步发现当前数字比有序列表都大，所以只需要直接指针后移即可，此时有序列表为(5 7)无序列表为 -1 2 4  
![在这里插入图片描述][20201120113131956.png_pic_center]  
第三步如下所示，在上次的过程中发现-1和前面比很小，所以找到合适的位置，发现-1应该放在0的位置，那么应该将其后移也就是 5 7 后移，将-1放在合适的位置如下所示。以此类推，直至所有的都完成排序  
![在这里插入图片描述][2020112011343752.png_pic_center]  
**代码**

//插入排序
        public static void insertSort(int[] arr){ 
            //-5,0,-2,6
            int j = 0;
            int temp = 0;
            //设置无序列表的起始索引为i,默认i可以从1开始;
            for(int i = 1;i<arr.length;i++){ 
                //将arr[i]与前面的所有有序序列进行比较
                //从 i-1比较到0 找到 待插入的位置
                if(arr[i] < arr[i-1]){ 
                    temp =arr[i];
                    j = i-1;
                    while(j >= 0 && arr[i] < arr[j]){ 
                        j--;
                    }
                    //找到待插入的位置 j+1 就是待插入的位置--执行移动
                    for(int m = i-1;m>=j+1;m--){ 
                        arr[m+1] = arr[m];
                    }
                    //替换
                    arr[j+1] = temp;
                }
    
            }
        }

# 选择排序 #

选择排序的基本思想是，比较和交换。在下标为0后找一个最小的放在0  
在1后找一个最小的放在下标为1处，依次类推.

> 第一步将min设置为arr\[0\]，在后面找到一个最小的，将其和index的值进行交换，并且Index指针后移

![在这里插入图片描述][20201120110732803.png_pic_center]  
![在这里插入图片描述][20201120110856648.png_pic_center]

> 第二步，继续min = arr\[index\]，在其后面找到最小的继续和arr\[index\]交换，以此类推，就可以找到所有的了。

![在这里插入图片描述][20201120111021981.png_pic_center]  
![在这里插入图片描述][20201120111036142.png_pic_center]  
**代码**  
分析：

> 设外层循环为i = 0 开始，需要遍历length - 1 次，因为最后一个不需要在找了肯定是有序的  
> 第i = 0次循环，将最小数的下标设置为min = i;  
> 内层循在0之后的数中找到最小值，如果找到的最小值不是mid = 0那就交换

//选择排序
        public static void selectSort(int[] arr){ 
            int min = 0;
            int temp = 0;
            for(int i =0;i<arr.length-1;i++){ 
                min = i;
                for(int j = i+1;j<arr.length;j++){ 
                    if(arr[j] < arr[min]){ 
                        min = j;
                    }
                }
                //执行交换
                if(min != i){ 
                    temp = arr[min];
                    arr[min] = arr[i];
                    arr[i] = temp;
                }
            }
        }

# 希尔排序 #

希尔排序就是对数据进行分组，  
第一次分成length / 2组，如下所示，有九个数据，分成4组，也就时候说，步长是4，a\[0\] a\[4\] a\[8\] 是第一组，a\[1\] a\[5\] 是第二组，以此类推  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center]  
第二步：将组内的元素用插入法排序，排成有序的，在对步长 = 4进行分组，分成4/2 = 2组，然后再分 2/ 2 = 1组，当为1组时排序完成就退出了。  
![在这里插入图片描述][20201120135844154.png_pic_center]  
**代码**  
思路：可以先判断最外层需要循环多少次，根据推理，当step>=1就需要进行排序，所以外层循环 while(step > 0)  
注意：希尔排序的本质和插入排序比较类似，插入排序从下标为1开始依次向前插入。而希尔排序是以组为单位，把数据和组内进行比较并插入。

//希尔排序
        public static void shellSort(int[] arr){ 
            /**1 *3 -5 2 7 6 1 * *找到分组之后，从每组的第二个开始遍历。为什么，因为假设每组的第一个是有序的 * 从第二个开始进行插入排序 * step = 3 */
    
            //最外层需要循环多少次？当步长>=1就需要进行排序
            int step = arr.length / 2;
            int j = 0;
            int temp;
            while(step > 0){ 
                for(int i = step;i<arr.length;i+=1){ 
                    //当前下标的前面都是有序的，我们要招到一个合适的位置，把当前元素插入进去
                    if(arr[i] < arr[i-step]){ 
                        temp = arr[i];
                        //当前元素比前一个小，才需要插入，因为前面是有序的
                        //找到插入位置
                        j = i-step;
                        while(j>=0 && arr[j] < arr[i]){ 
                            //如果前一个元素小的话我就继续向前
                            j-=step;
                        }
                        //找到待插入位置为j+step;
                        //将元素后移
                        for(int m = i-step;m<=j+step;m-=step){ 
                            arr[m+step] = arr[m];
                        }
                        //填充坑位
                        arr[j+step] = temp;
                    }
                }
                step /= 2;
            }
        }

# 快速排序 #

注意：市面上有很多让从下标为0开始作为基数，个人建议从下标为length/2作为基数。

快速排序的思想是，找一个基准数组分成左右两侧，左边是小的，右边是大的。在分别对左侧和右侧进行排序。

如下：数组

13 6 12 4 12 10 5 7 14

第一步首先，找到中间值mid最好使用中间值而不是用中间下标，因为可能中间的值可能会变化，

从high开始从右向左找小于mid的。

![在这里插入图片描述][20201120160743513.png_pic_center]

第二步找到小于mid的时候，那就将low循环找到大于mid的，

![在这里插入图片描述][2020112016075131.png_pic_center]

![在这里插入图片描述][20201120160759914.png_pic_center]

第三步将两个数进行交换

![在这里插入图片描述][20201120160810613.png_pic_center]

第四步high继续向下找

![在这里插入图片描述][20201120160818170.png_pic_center]

low继续向下找

![在这里插入图片描述][20201120160825779.png_pic_center]

找到合适的值之后继续交换，注意：这时候发现high的值和mid的值时相等的，我们在交换完之后需要将high–，需要结合程序理解这个图形

![在这里插入图片描述][20201120160835903.png_pic_center]

然后继续找找到之后继续交换

![在这里插入图片描述][20201120160842211.png_pic_center]

代码如下所示

//快速排序
    public static void quickSort(int[] arr,int left,int right){ 
        int middle = arr[(left+right)/2];
        int low = left;
        int high = right;
        int temp = 0;
        //在右侧找一个大的，当low >= high时退出循环
        while(low < high){ 
            //在左侧找一个大的
            while(arr[low] < middle){ 
                low++;
            }
            //在右侧找一个小的
            while(arr[high] > middle){ 
                high--;
            }
            //判断是不是low和high相等
            if(low >= high){ 
                break;
            }
            //进行交换
            temp = arr[low];
            arr[low] = arr[high];
            arr[high]=temp;
            if(arr[low] == middle){ 
                high--;
            }
            if(arr[high] == middle){ 
                low++;
            }
        }
        if(low == high){ 
            low++;
            high--;
        }
    
        if(left < high){ 
            //将左侧排序
            quickSort(arr,left,high);
        }
    
        if(right > low){ 
            //将右侧排序
            quickSort(arr,low,right);
        }
    }

# 归并排序 #

8 4 5 7 1 3 6 2

如上述数组，归并排序的思想如下

首先，将数据进行拆分，然后进行合并。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 1]  
和并的思路如下所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 2]  
假设以最后一次的合并来分析（其实按照上述的数组，一共需要合并7次）

第一次 合并 4 8

第二次合并 5 7以此类推

用最后一次分析：

创建一个temp数组，用来临时存放，用三个指针,left、mid、right。left为左侧有序列表的起始索引，

mid为左侧数组的最后一个元素的索引 arr\[mid+1\] 为右侧有序列表的第一个数

right为右侧有序列表的最后一个数。

1.  left元素和mid+1上的元素进行比较，如left小，那么将这个小的放在temp数组中区，将left++
2.  判断left数组和mid+1上的元素比较 若mid+1上的小，那么将其放在temp数组中，

当两侧由一方的数组放完了，那就说明可以退出循环，然后将另外一个数组剩下的元素放在temp数组中

最后将temp数组的元素赋值到原数组中  
**代码**

//归并排序
        public static void mergeSort(int[] arr,int left,int right,int[] temp){ 
            if(left < right){ 
                int mid = (right + left)/2;
                //进行左侧再分
                mergeSort(arr,left,mid,temp);
                mergeSort(arr,mid+1,right,temp);
                //进行合并
                merge(arr,left,mid,right,temp);
            }
        }
        //合并操作，
        /**1 * arr 原数组 * left 需要合并的最左侧的索引 * right 需要合并的最右侧索引 * mid 中间索引 -- 左侧数据的最后一个索引 */
        public static void merge(int[] arr,int left,int mid,int right,int[] temp){ 
            //外层循环什么时候结束？左右两侧由一方的值合并完成那就结束了
            int i = left;
            int tempLeft = 0;
            int index = 0;
            int j = mid+1;//右侧的起始索引
            while(i <= mid && j <= right){ 
                //当前位置的左侧和右侧元素比较，将小的放入temp
                if(arr[i] < arr[j]){ 
                    temp[index] = arr[i];
                    index++;
                    i++;
                }else{ 
                    temp[index] = arr[j];
                    index++;
                    j++;
                }
            }
            //排序完了后，可能左侧或者右侧还有剩下元素，直接放在temp中
            while(i<=mid){ 
                temp[index] = arr[i];
                index++;
                i++;
            }
            while(j<=right){ 
                temp[index] = arr[j];
                index++;
                j++;
            }
            //然后将合并好的数组放入到原数组中
            index = 0;
            tempLeft = left;
            while(tempLeft <= right){ 
                arr[tempLeft] = temp[index];
                tempLeft++;
                index++;
            }
        }

# 基数排序（桶排序） #

桶排序的图解思路如下所示  
创建一个二维数组，buket\[\]\[\]。行的个数为10，列的个数为目标排序数组的arr.length  
现有数组53 3 542 748 14 214  
第0轮排序是将每个数组的个位数放在和桶下标一致的桶里面。然后在把桶里面的数据收集起来放在原数组中  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 3]  
第1轮就是将收集好的原数组，再次将十位上的数组放在对应的桶里。如下所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 4]  
第2轮，在将其收集，然后放在如下的桶里。依次类推，主要放几轮？假设最大数的位数为3那么需要放3轮。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 5]  
**代码**  
代码描述：  
定义bucket二维数组为桶。但是每个桶里面具体放了多少个元素？，可以定义一个count一维数组来保存。  
1.首先找到最大的数的长度，就能找到最外层循环需要的执行的轮数  
2.遍历原数组arr 使其每一个数都进入到桶里面。  
3.当进入桶里面之后需要将所有的数据在同一的赋值到原数组中，当某一个桶的元素的值被复制完了，就认为这个桶已经空了，需要将count数组对应的值进行清零。

//桶排序
        public static void buketSort(int[] arr){ 
            int[][] buket = new int[10][arr.length];
            //需要一个数组来存放bucket的每一列放的个数
            int[] count = new int[10];
    
            //最外层需要几轮循环？应该找到最大的数，求其长度
            int max = arr[0];
            for(int i =1;i<arr.length;i++){ 
                if(arr[i] > max){ 
                    max = arr[i];
                }
            }
            int maxLength = (max + "").length();
            int temp = 1;
            int tempIndex = 0;
            //当3位数应该循环3次，k位数应该循环k次
           for(int i =0;i<maxLength;i++){ 
                //首先，遍历原数组，给他放在桶里
                for(int j =0;j<arr.length;j++){ 
                    //第0次最外层循环时找到个位数 就是 /1%10
                    //第一次最外层循环是 /10%10--所以在最外层加个temp
                    int index = arr[j] / temp %10;//找到下标
                    buket[index][count[index]] = arr[j];
                    count[index]++;//列里面的个数+1
                }
               //从桶里面收集出来回到原数组中，为下一次做准备
                for(int m = 0;m<10;m++){ 
                    for (int n =0;n<count[m];n++){ 
                        arr[tempIndex] = buket[m][n];
                        tempIndex++;
                    }
                    count[m] = 0;
                }
               tempIndex = 0;
               temp *= 10;
           }
        }

## 注意 ##

> 桶排序的速度非常快，但是很耗费内存，比如现在排序10000个数据，不算原数组的空间的话那么耗费的空间就是 10000 \* 11 \* 4 字节（假设里面放的int类型）数据量太多的情况下存在OOM的风险比较大

[20201120103843386.png_pic_center]: /images/20221120/30dff8b3085d447482fa222d440d0178.png
[20201120104134837.png_pic_center]: /images/20221120/73318e9913d44493b58938950bf3c427.png
[20201120104214856.png_pic_center]: /images/20221120/04951eba02a74abf9392560e557d3459.png
[2020112011300478.png_pic_center]: /images/20221120/559ac10ccee54ba1acb49eee96ce0776.png
[20201120113131956.png_pic_center]: /images/20221120/802d20b8b9984490a73362ed724a0bbe.png
[2020112011343752.png_pic_center]: /images/20221120/80c65af717c64b1a9e0eadec71689cb5.png
[20201120110732803.png_pic_center]: /images/20221120/3c48c4f132ad49cebaa4f7bda992d9c1.png
[20201120110856648.png_pic_center]: /images/20221120/c207275f96ee44d5ae738a4c85369c0d.png
[20201120111021981.png_pic_center]: /images/20221120/4eaa3f2bc1b243dbbc1b57d6b69245d8.png
[20201120111036142.png_pic_center]: /images/20221120/3699919942d84eeaaa5ba87c2bde307c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9ff3b3f465114b1388f0ac7d0460d1ce.png
[20201120135844154.png_pic_center]: /images/20221120/a91cc5430a7a4b1caab0bbecdc98649a.png
[20201120160743513.png_pic_center]: /images/20221120/1a9cec30dc3b4b9f85149e0857fec3db.png
[2020112016075131.png_pic_center]: /images/20221120/e480a91231cf42c19c0a9b90bbd69ff9.png
[20201120160759914.png_pic_center]: /images/20221120/6ee31298951c4b289c66f70ab27c4d19.png
[20201120160810613.png_pic_center]: /images/20221120/d1d6cf3dc56e4bc69a2e6eb2ce7d3409.png
[20201120160818170.png_pic_center]: /images/20221120/1a18184bc54544de8850dae7f0313507.png
[20201120160825779.png_pic_center]: /images/20221120/670c2ee9350e431d88c0122076253e93.png
[20201120160835903.png_pic_center]: /images/20221120/f2a1aadce64c4fe2affeb99be23279f2.png
[20201120160842211.png_pic_center]: /images/20221120/5fa835123b4e4fa5a68f2fc946ae0ee0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/11c3a34f1035479ea74e9a974febefd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/b06abdbe8c55420798fa68d823b92e09.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/72d858f14d744bd592bd594cd656f1d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/0c9b071283f2416eaf62b5d877ed4a18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/a2d1bb54d628442994d0e2e90bb68d63.png