图解解析 + 代码实现：带你手撕冒泡、选择、插入、希尔排序。

深藏阁楼爱情的钟 2023-10-02 20:25 16阅读 0赞

**目录**

一、冒泡排序

1、基本介绍

2、代码实现

二、 选择排序

1、基本介绍

2、代码实现

三、插入排序

1、基本介绍

2、代码实现

四、希尔排序

1、基本介绍

2、代码实现（交换排序）

3、代码实现（移位排序）

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

## 一、冒泡排序 ##

> ### 1、基本介绍 ###
> 
> 冒泡排序是重复地走访要排序的元素，依次比较两个相邻的元素，如果它们的顺序与自己规定的不符合，则把两个元素的位置交换。走访元素重复地进行，直到没有相邻元素需要交换为止，完成整个排序过程。
> 
>  **▶ 算法原理**
> 
> 1、比较相邻元素，如果前一个元素大于后一个元素，则交换。  
> 2、依次向后对每一对相邻元素做同样的工作，直到队列末尾，第一轮过后最大的元素就位于最后一个元素位置了。  
> 3、重复以上步骤，直到最后一个元素位置的前一位为止（因为最后一位已经排了）。  
> 4、持续每次对越来越少的元素重复上面步骤，直到第一个元素和第二个元素交换后顺序为从大到小或从小到大，排序结束。
> 
> ### 2、代码实现 ###
> 
> 冒泡排序实际上就是两个数两个数的比较，每循环一次将最大或最小的数放在最后，剩下的就继续两两比较。
> 
>     public static void bubbleSort(int[] arr){
>             //中间变量，用来交换数据
>             int temp = 0;
>     
>             //外层循环
>             for (int i = 0 ; i < arr.length - 1 ; i++){
>     
>                 //内层循环，每次找到最大的数后放在最后，下次遍历则会少一次，及arr.length - i - 1
>                 for(int j = 0; j < arr.length - i - 1; j++){
>                     //判断大小
>                     if(arr[j] > arr[j + 1]){
>                         //将两数进行交换
>                         temp = arr[j];
>                         arr[j] = arr[j + 1];
>                         arr[j + 1] = temp;
>                     }
>                 }
>             }
>     
>     }

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

## 二、 选择排序 ##

> ### 1、基本介绍 ###
> 
> 首先第一次确定第一个数为最小的，然后利用for循环，将第一个数后的数据遍历一遍，找是否还有比第一个数更小的，记录下来，遍历完毕后将第一个数与最小的数进行交换。然后又确定第二数，找第二个数以后的数，是否还有比第二个数更小的，找到后与第二个数又进行交换，重复上面即可。
> 
> ![55d89dc096bf48e581797bdd0a1cf119.png][]
> 
> ![0c9b0b55d1d24c358044e35bf8cf85d1.png][]
> 
> ![242178300f7840dabc772e9cfa720aba.png][]
> 
> ![540feec38b9d41c2a5474a70e29d7e12.png][]
> 
> 以后的每次循环都是按照这种方式，直到最后两个数排完，数据就是有序的了。
> 
> ### 2、代码实现 ###
> 
>     public static void choiceSort(int[] arr){
>             
>             //用来记录最小的数
>             int arrData = 0;
>             //记录最小的数的下标
>             int arrindx = 0;
>             
>             //外层循环，直到 arr.length - 1 即可
>             for(int i = 0; i < arr.length - 1; i++){
>                 //首先把arr[i] 当做最小的数，并记录下标
>                 arrData = arr[i];
>                 arrindx = i;
>     
>                 //内层循环，遍历 i 以后的数，找到比 arr[i] 还小的数
>                 for (int j = i + 1; j < arr.length; j++){
>                     //找到更小的数，就进行记录
>                     if(arrData > arr[j]){
>                         arrData = arr[j];
>                         arrindx = j;
>                     }
>                 }
>                 //循环完毕，说明找到了，最小的数，与arr[i] 进行交换即可
>                 arr[arrindx] = arr[i];
>                 arr[i] = arrData;
>             }
>     
>     }

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

## 三、插入排序 ##

> ### 1、基本介绍 ###
> 
> 前面我们介绍的选择排序，找到最小的就与前面的进行交换。而插入排序，就是将确定的数的后一位插入到前面即可。图形介绍：
> 
> ![5f46febe7e6f4155847cb1994eb6ff35.png][]
> 
> 开始，id指向第一个数，mid指向第二个数，然后两个数进行比较。
> 
> ![81edbcd912a741b6911e55016d3cb554.png][]
> 
> 此时，1 比 3 小，但是3前面没数据了，于是将1插入到3的前面，注意这里是插入，不是交换。下一步 3 比 5 小，于是不用插入。
> 
> ![28b0f63fcb474a7ea0e02a4713e627ab.png][]
> 
> 经过三次比较，确定了 2 的位置在 1 和 3 直接，直接将 2 插入。
> 
> ![2983059be8b44cb199e922395616c77b.png][]
> 
> 又经过四次比较，找到 0 的位置 在 1 的前面，于是将 0 插入到 1 的前面即可。
> 
> ### 2、代码实现 ###
> 
>     public static void insertSort(int[] arr){
>             
>             //下标为 0 的数是确定的，从下标为 1 开始循环
>             for (int i = 1; i < arr.length; i++){
>     
>                 // 将下标为 i 的数暂存起来
>                 int arrData = arr[i];
>                 //从 i - 1 开始往前循环
>                 int arrIndx = i - 1;
>                 //判断退出的条件 大于等于0
>                 while (arrIndx >= 0){
>                     //如果arrData 大于 下标为arrIndx 的数，则位置找到，退出循环
>                     if (arrData > arr[arrIndx]){
>                         break;
>                     }
>                     //没有找到，就将前面的数往后移
>                     arr[arrIndx + 1] = arr[arrIndx];
>                     arrIndx--;
>                 }
>                 //找到位置后，就将暂存的数据arrData 插入到下标为arrIndx的位置
>                 arr[arrIndx + 1] = arrData;
>             }
>     
>         }

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

## 四、希尔排序 ##

> ### 1、基本介绍 ###
> 
> ![db31ebf9f0d54eee86c11444cb5bfaa3.png][]
> 
> 首先将数组分为两组，3、2、0 为一组，1、5为一组，g = arr.length / 2。
> 
> ![3ef88883a7fb4476854a7e9b85679161.png][]
> 
> 2 和 3 进行判断，3 比 2 大 ，然后进行交换位置，交换后 j = j - g < 0（因为第一次的分为两组，所以 i - 2 ）。所以 i++ ，j = i - g
> 
> ![207c5826d9d84eb490cddad610665945.png][]
> 
> 不需要交换， 然后 j = j - g < 0 ,所以 i++ ，j = i - g
> 
> ![f112d5d5f3e34275a19c56b29324205e.png][]
> 
> 3 比 0 大 ，需要交换。然后 j = j - g > 0 , j = j - g
> 
> ![7cca2e07169e4259a22856abd7c9aeb9.png][]
> 
> 交换后 j = j - g < 0 , i++ > arr.length 了，第一轮结束
> 
> 第二轮：在arr.length / 2的基础上再除2 ， 于是 g = 1 ；
> 
> ![88f365e4347843019fec0cc1ab868e90.png][]
> 
> 然后两两交换，交换后 进行j = j - g > 0 的判断 ，不成立则 i++ , j = i - g ，成立则 j = j - g ，就这样一直循环下去。第二轮后的结果：
> 
> ![a2c49431fd294216ab82a16da7567e51.png][]
> 
> 第二轮结束后，g / 2 = 0 结果不大于 0，所以排序结束
> 
> ### 2、代码实现 （交换排序） ###
> 
>     public static void shellSort_exchange(int[] arr){
>             //做中间变量，进行数据交换
>             int temp = 0;
>             
>             // g 首先数组总长除以2， 然后每次除以2
>             for(int g = arr.length / 2 ; g > 0 ; g /= 2){
>     
>                 // i 从 g 的位置开始遍历
>                 for(int i = g ; i < arr.length ; i++){
>     
>                     // j 从 i - g 的位置开始向前遍历，j 的位置由 j - g 来决定
>                     for(int j = i - g ; j >= 0 ; j -= g){
>     
>                         //判断 下标(j + g) 和 下标j 位置的数的大小，然后进行交换
>                         if(arr[j + g] < arr[j]){
>                             //交换即可
>                             temp = arr[j + g];
>                             arr[j + g] = arr[j];
>                             arr[j] = temp;
>                         }
>                     }
>                 }
>             }
>         }
> 
> ### 3、代码实现（移位排序） ###
> 
> 移位排序的思想与前面的交换排序一样的，只是在交换数的方式上有变化。交换排序数的交换方式来自冒泡排序，而移位排序数的交换方式来自插入排序。
> 
>     public static void test1(int[] arr){
>             //与前面一样，开始数组长度除以2 ， 然后每次除以2
>             for(int g = arr.length / 2 ; g > 0 ; g /= 2){
>     
>                 // i 从 g 位置开始，每次加一
>                 for(int i = g ; i < arr.length ; i++){
>     
>                     //定义 j 的位置 为 i
>                     int j = i ;
>                     //将 下标为 i 位置的数暂存起来
>                     int temp = arr[i];
>                     
>                     //判断 下标j位置的数 和 j - g 位置的数，与前面一样
>                     if(arr[j] < arr[j - g] ){
>     
>                         //遍历循环
>                         while(j - g >= 0 && temp < arr[j - g]){
>     
>                             //满足条件，就移位，将前面的数 (下标j - g) 往后移 (下标j)
>                             arr[j] = arr[j - g];
>     
>                             j -= g;// j 每次 -g
>                         }
>                     }
>                     //退出循环或判断条件后，将暂存的temp (arr[i]) 赋值给 arr[j]
>                     arr[j] = temp;
>                 }
>             }
>         }

[55d89dc096bf48e581797bdd0a1cf119.png]: https://img-blog.csdnimg.cn/55d89dc096bf48e581797bdd0a1cf119.png
[0c9b0b55d1d24c358044e35bf8cf85d1.png]: https://img-blog.csdnimg.cn/0c9b0b55d1d24c358044e35bf8cf85d1.png
[242178300f7840dabc772e9cfa720aba.png]: https://img-blog.csdnimg.cn/242178300f7840dabc772e9cfa720aba.png
[540feec38b9d41c2a5474a70e29d7e12.png]: https://img-blog.csdnimg.cn/540feec38b9d41c2a5474a70e29d7e12.png
[5f46febe7e6f4155847cb1994eb6ff35.png]: https://img-blog.csdnimg.cn/5f46febe7e6f4155847cb1994eb6ff35.png
[81edbcd912a741b6911e55016d3cb554.png]: https://img-blog.csdnimg.cn/81edbcd912a741b6911e55016d3cb554.png
[28b0f63fcb474a7ea0e02a4713e627ab.png]: https://img-blog.csdnimg.cn/28b0f63fcb474a7ea0e02a4713e627ab.png
[2983059be8b44cb199e922395616c77b.png]: https://img-blog.csdnimg.cn/2983059be8b44cb199e922395616c77b.png
[db31ebf9f0d54eee86c11444cb5bfaa3.png]: https://img-blog.csdnimg.cn/db31ebf9f0d54eee86c11444cb5bfaa3.png
[3ef88883a7fb4476854a7e9b85679161.png]: https://img-blog.csdnimg.cn/3ef88883a7fb4476854a7e9b85679161.png
[207c5826d9d84eb490cddad610665945.png]: https://img-blog.csdnimg.cn/207c5826d9d84eb490cddad610665945.png
[f112d5d5f3e34275a19c56b29324205e.png]: https://img-blog.csdnimg.cn/f112d5d5f3e34275a19c56b29324205e.png
[7cca2e07169e4259a22856abd7c9aeb9.png]: https://img-blog.csdnimg.cn/7cca2e07169e4259a22856abd7c9aeb9.png
[88f365e4347843019fec0cc1ab868e90.png]: https://img-blog.csdnimg.cn/88f365e4347843019fec0cc1ab868e90.png
[a2c49431fd294216ab82a16da7567e51.png]: https://img-blog.csdnimg.cn/a2c49431fd294216ab82a16da7567e51.png