【Java数据结构和算法】011-排序：冒泡排序、选择排序、插入排序、希尔排序*

忘是亡心i 2023-10-05 04:59 24阅读 0赞

> 备注：希尔排序很强大，但是还是未能完全理解！
> 
> 时间：2020年11月23日10时53分

**目录**

0、警醒自己

一、冒泡排序

1、基本介绍

2、思路图解

3、代码实现

4、运行结果

5、测试冒泡排序的速度

代码（封装成方法）：

运行结果（13s）：

二、选择排序

1、基本介绍

2、选择排序思想

3、思路图解

编程逻辑：

4、代码实现

5、运行结果

6、测试选择排序的速度

代码（封装成方法）：

运行结果（2s有点强啊）：

三、插入排序

1、基本介绍

2、插入排序思想

3、思路图解

4、代码演示

5、运行结果

6、插入排序速度测试

代码：

运行结果（恐怖如斯，不到1s，939毫秒）：

四、希尔排序

1、简单插入排序存在的问题

2、希尔排序法介绍

3、希尔排序基本思想

4、代码演示（交换式）

代码实现：

运行结果：

备注：

5、代码演示（交换式）速度测试

代码：

运行结果（尴尬7s）：

6、代码演示（移位式）速度测试

代码实现：

运行结果（卧槽，8万数据，20毫秒）：

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

# 0、警醒自己 #

**1、学习不用心，骗人又骗己；**

**2、学习不刻苦，纸上画老虎；**

**3、学习不惜时，终得人耻笑；**

**4、学习不复习，不如不学习；**

**5、学习不休息，毁眼伤身体；**

**7、狗才等着别人喂，狼都是自己寻找食物；**

# 一、冒泡排序 #

## 1、基本介绍 ##

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒；

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下 来没有进行过交换，就说明序列有序，因此要在排序过程中设置 一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，再进行)

## 2、思路图解 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70][]

## 3、代码实现 ##

package com.zb.ds.sort;
    
    //冒泡排序
    public class BubbleSort {
        public static void main(String[] args) {
            int[] nums = {3,9,-1,10,-2};
            boolean flag = false;//true代表交换过
            int temp;//辅助变量
            for (int i = 0; i < nums.length; i++) {
                //一趟确定一个数，五个数就需要五趟
                //每一趟确定一个数，也就是每一趟少比1个数
                for (int j = 0; j < nums.length-1-i; j++) {
                    //五个元素，第一次排序只需要交换四次，往后分别是3、2、1次
                    if(nums[j] > nums[j+1]){//大于才交换
                        temp = nums[j];
                        nums[j] = nums[j+1];
                        nums[j+1] = temp;
                        flag = true;
                    }
                }
                //如果比完了，一次也没交换，说明顺序对了
                if(!flag){
                    break;
                }else {
                    flag = false;
                }
            }
            //输出排序后的数组
            for (int num : nums) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

## 4、运行结果 ##

-2 -1 3 9 10

## 5、测试冒泡排序的速度 ##

### 代码（封装成方法）： ###

package com.zb.ds.sort;
    
    import java.util.Random;
    
    //冒泡排序
    public class BubbleSort {
        public static void main(String[] args) {
            int[] nums = new int[80000];
            for (int i = 0; i < 80000; i++) {
                nums[i] = new Random().nextInt(8000000);
            }
            //排序前时间
            long start = System.currentTimeMillis();
            System.out.println("排序前时间：" + start);
            sort(nums);
            //排序后时间
            long end = System.currentTimeMillis();
            System.out.println("排序后时间：" + end);
            //程序执行时间
            System.out.println("程序执行时间为：" + (end-start)/1000 + "秒！");
        }
        public static void sort(int[] nums){
            boolean flag = false;//true代表交换过
            int temp;//辅助变量
            for (int i = 0; i < nums.length; i++) {
                //一趟确定一个数，五个数就需要五趟
                //每一趟确定一个数，也就是每一趟少比1个数
                for (int j = 0; j < nums.length-1-i; j++) {
                    //五个元素，第一次排序只需要交换四次，往后分别是3、2、1次
                    if(nums[j] > nums[j+1]){//大于才交换
                        temp = nums[j];
                        nums[j] = nums[j+1];
                        nums[j+1] = temp;
                        flag = true;
                    }
                }
                //如果比完了，一次也没交换，说明顺序对了
                if(!flag){
                    break;
                }else {
                    flag = false;
                }
            }
        }
    }

### 运行结果（13s）： ###

排序前时间：1605927173472
    排序后时间：1605927186622
    程序执行时间为：13秒！

# 二、选择排序 #

## 1、基本介绍 ##

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的；

## 2、选择排序思想 ##

选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr\[0\]~arr\[n-1\]中选取最小值，与arr\[0\]交换，第二次从arr\[1\]~arr\[n-1\]中选取最小值，与arr\[1\]交换，第三次从arr\[2\]~arr\[n-1\]中选取最小值，与arr\[2\]交换，…，第i次从arr\[i-1\]~arr\[n-1\]中选取最小值，与arr\[i-1\]交换，…, 第n-1次从arr\[n-2\]~arr\[n-1\]中选取最小值，与arr\[n-2\]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列；

**遍历查找，找到第1个最小值，与第1个元素交换位置，再找第2个最小值，再与第2个元素交换位置，以此类推，直到找到所有值；**

## 3、思路图解 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1][]

第一趟找到最小的是1，与第1个元素8进行位置交换；

第二趟找到最小的是2，与第2个元素3进行位置交换；

以此类推，直到第7趟，确定了前7个元素是从小到大，第8个元素自然是最大的，排序也就完成了；

### 编程逻辑： ###

1、选择排序一共有数组大小 - 1 趟排序；

2. 每1趟排序，又是一个循环，循环的规则(代码) ：

2.1先假定当前这个数是最小数；

2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标；

2.3 当遍历到数组的最后时，就得到本轮最小数和下标；

2.4 交换；

## 4、代码实现 ##

package com.zb.ds.sort;
    
    public class SelectionSort {
        public static void main(String[] args) {
            int[] nums = {8,3,2,1,7,4,6,5};
            int min,index;//记录最小值的索引
            //选择次数是7次
            for (int i = 0; i < nums.length-1; i++) {
                //每一次从当前元素开始查找，找到最后一个
                //拿到当前元素的值，用于比较
                min = nums[i];
                index = i;
                for (int j = i+1; j < nums.length; j++) {
                    //如果当前值最小值比下一个值大，那么当前最小值就变成下一个值
                    if(min>nums[j]){
                        min = nums[j];
                        index = j;
                    }
                }
                //遍历完之后，说明当前的min就是最小值了，根据index和min进行交换
                nums[index] = nums[i];
                nums[i] = min;
            }
            //排序后，输出
            for (int num : nums) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

## 5、运行结果 ##

1 2 3 4 5 6 7 8

## 6、测试选择排序的速度 ##

### 代码（封装成方法）： ###

package com.zb.ds.sort;
    
    import java.util.Random;
    
    public class SelectionSort {
        public static void main(String[] args) {
            int[] nums = new int[80000];
            for (int i = 0; i < 80000; i++) {
                nums[i] = new Random().nextInt(8000000);
            }
            //排序前时间
            long start = System.currentTimeMillis();
            System.out.println("排序前时间：" + start);
            sort(nums);
            //排序后时间
            long end = System.currentTimeMillis();
            System.out.println("排序后时间：" + end);
            //程序执行时间
            System.out.println("程序执行时间为：" + (end-start)/1000 + "秒！");
        }
        public static void sort(int[] nums){
            int min,index;//记录最小值的索引
            //选择次数是7次
            for (int i = 0; i < nums.length-1; i++) {
                //每一次从当前元素开始查找，找到最后一个
                //拿到当前元素的值，用于比较
                min = nums[i];
                index = i;
                for (int j = i+1; j < nums.length; j++) {
                    //如果当前值最小值比下一个值大，那么当前最小值就变成下一个值
                    if(min>nums[j]){
                        min = nums[j];
                        index = j;
                    }
                }
                //遍历完之后，说明当前的min就是最小值了，根据index和min进行交换
                nums[index] = nums[i];
                nums[i] = min;
            }
        }
    }

### 运行结果（2s有点强啊）： ###

排序前时间：1605928974701
    排序后时间：1605928977117
    程序执行时间为：2秒！

# 三、插入排序 #

## 1、基本介绍 ##

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的；

## 2、插入排序思想 ##

插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表；

## 3、思路图解 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2][]

## 4、代码演示 ##

package com.zb.ds.sort;
    
    //插入排序
    public class InsertSort {
        public static void main(String[] args) {
            int[] arr = {101,34,119,1};
            int[] sortA = sortA(arr);
            for (int i : sortA) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
        public static int[] sortA(int[] arr){
            int[] tempArr = new int[arr.length];
            tempArr[0] = arr[0];
            boolean flag = false;
            //遍历从第二个到最后一个
            for (int i = 1; i < arr.length; i++) {
                //拿到一个要插入的元素arr[i]
                for (int j = i-1; j >= 0; j--) {
                    //从最后一个开始比较，如果比最后一个大，就往后插入，反之将最后一个往后移动一位，倒数第二个进行比较，
                    // 如果大于倒数第二个就插入其后，否则以此类推，后移，比较...
                    if(arr[i]>tempArr[j]){
                        tempArr[j+1] = arr[i];
                        //找到位置了，标记后跳出循环
                        flag = true;
                        break;
                    }else {
                        //重点就在这了
                        //1、让tempArr[j]往后走一位
                        tempArr[j+1] = tempArr[j];
                        //2、让arr[i]与tempArr[j-1]比较，也就是下一轮
                        //将标记重置为没找到，要不然找到一个就以为都找到了，最小的那个会出错
                        flag = false;
                    }
                }
                //如果一直没找到位置，说明此时的arr[i]最小，放在tempArr[0]
                if(!flag){
                    tempArr[0] = arr[i];
                }
            }
            return tempArr;
        }
    }

## 5、运行结果 ##

1 34 101 119

## 6、插入排序速度测试 ##

### 代码： ###

package com.zb.ds.sort;
    
    import java.util.Random;
    
    //插入排序
    public class InsertSort {
        public static void main(String[] args) {
            int[] nums = new int[80000];
            for (int i = 0; i < 80000; i++) {
                nums[i] = new Random().nextInt(8000000);
            }
            //排序前时间
            long start = System.currentTimeMillis();
            System.out.println("排序前时间：" + start);
            sort(nums);
            //排序后时间
            long end = System.currentTimeMillis();
            System.out.println("排序后时间：" + end);
            //程序执行时间
            System.out.println("程序执行时间为：" + (end-start)/1000 + "秒！");
        }
        public static void sort(int[] arr){
            int[] tempArr = new int[arr.length];
            tempArr[0] = arr[0];
            boolean flag = false;
            //遍历从第二个到最后一个
            for (int i = 1; i < arr.length; i++) {
                //拿到一个要插入的元素arr[i]
                for (int j = i-1; j >= 0; j--) {
                    //从最后一个开始比较，如果比最后一个大，就往后插入，反之将最后一个往后移动一位，倒数第二个进行比较，
                    // 如果大于倒数第二个就插入其后，否则以此类推，后移，比较...
                    if(arr[i]>tempArr[j]){
                        tempArr[j+1] = arr[i];
                        //找到位置了，标记后跳出循环
                        flag = true;
                        break;
                    }else {
                        //重点就在这了
                        //1、让tempArr[j]往后走一位
                        tempArr[j+1] = tempArr[j];
                        //2、让arr[i]与tempArr[j-1]比较，也就是下一轮
                        //将标记重置为没找到，要不然找到一个就以为都找到了，最小的那个会出错
                        flag = false;
                    }
                }
                //如果一直没找到位置，说明此时的arr[i]最小，放在tempArr[0]
                if(!flag){
                    tempArr[0] = arr[i];
                }
            }
        }
    }

### 运行结果（恐怖如斯，不到1s，939毫秒）： ###

排序前时间：1605941125659
    排序后时间：1605941126598
    程序执行时间为：0秒！

# 四、希尔排序 #

（不易理解，但妙不可言）

## 1、简单插入排序存在的问题 ##

当需要插入的数是较小的数时，后移的次数明显很多，对效率有影响；

## 2、希尔排序法介绍 ##

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。**希尔排序也是一种插入排序**，它是简单插入排序经过改进之后的一个更高效的版本，也称为**缩小增量排序；**

## 3、希尔排序基本思想 ##

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；

随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3][]

## 4、代码演示（交换式） ##

### 代码实现： ###

package com.zb.ds.sort;
    
    import java.util.Arrays;
    
    //希尔排序
    public class ShellSort {
        public static void main(String[] args) {
            //原始数据
            int[] arr = {8,9,1,7,2,3,5,4,6,0};
            //希尔排序
            int groupNum = arr.length / 2 ;
            int temp;
            //循环进行分组，当1/2=0的时候说明进行了最后的插入排序了，也就是完成了排序，结束即可
            while (groupNum!=0){
                for (int i = groupNum; i < arr.length; i++) {
                    //从第groupNum个开始循环，这是后面的元素
                    for (int j=i-groupNum;j>=0;j-=groupNum){
                        //如果当前元素大于加上步长后的元素，就交换
                        if(arr[j] > arr[j+groupNum]){
                            temp = arr[j];
                            arr[j] = arr[j+groupNum];
                            arr[j+groupNum] = temp;
                        }
                    }
                }
                groupNum = groupNum/2;//计算下一轮组数
            }
            System.out.println("排序后：" + Arrays.toString(arr));
        }
    
    }

### 运行结果： ###

排序后：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

### 备注： ###

我觉得还有需要优化的地方，因为最后一轮排序，后面很多步已经不需要了；

## 5、代码演示（交换式）速度测试 ##

### 代码： ###

package com.zb.ds.sort;
    
    import java.util.Random;
    
    //希尔排序
    public class ShellSort {
        public static void main(String[] args) {
            int[] nums = new int[80000];
            for (int i = 0; i < 80000; i++) {
                nums[i] = new Random().nextInt(8000000);
            }
            //排序前时间
            long start = System.currentTimeMillis();
            System.out.println("排序前时间：" + start);
            sort(nums);
            //排序后时间
            long end = System.currentTimeMillis();
            System.out.println("排序后时间：" + end);
            //程序执行时间
            System.out.println("程序执行时间为：" + (end-start)/1000 + "秒！");
        }
        public static void sort(int[] arr){
            //希尔排序
            int groupNum = arr.length / 2 ;
            int temp;
            //循环进行分组，当1/2=0的时候说明进行了最后的插入排序了，也就是完成了排序，结束即可
            while (groupNum!=0){
                for (int i = groupNum; i < arr.length; i++) {
                    //从第groupNum个开始循环，这是后面的元素
                    for (int j=i-groupNum;j>=0;j-=groupNum){
                        //如果当前元素大于加上步长后的元素，就交换
                        if(arr[j] > arr[j+groupNum]){
                            temp = arr[j];
                            arr[j] = arr[j+groupNum];
                            arr[j+groupNum] = temp;
                        }
                    }
                }
                groupNum = groupNum/2;//计算下一轮组数
            }
        }
    }

### 运行结果（尴尬7s）： ###

（这有点尴尬啊，还没有插入排序快！）

排序前时间：1606098244591
    排序后时间：1606098252028
    程序执行时间为：7秒！

## 6、代码演示（移位式）速度测试 ##

### 代码实现： ###

package com.zb.ds.sort;
    
    import java.util.Random;
    
    //希尔排序
    public class ShellSort2 {
        public static void main(String[] args) {
            int[] nums = new int[80000];
            for (int i = 0; i < 80000; i++) {
                nums[i] = new Random().nextInt(8000000);
            }
            //排序前时间
            long start = System.currentTimeMillis();
            System.out.println("排序前时间：" + start);
            sort(nums);
            //排序后时间
            long end = System.currentTimeMillis();
            System.out.println("排序后时间：" + end);
            //程序执行时间
            System.out.println("程序执行时间为：" + (end-start)/1000 + "秒！");
        }
        public static void sort(int[] arr){
            //希尔排序
            int groupNum = arr.length / 2 ;
            //循环进行分组，当1/2=0的时候说明进行了最后的插入排序了，也就是完成了排序，结束即可
            while (groupNum!=0){
                for (int i = groupNum; i < arr.length; i++) {
                    int j = i;
                    int temp = arr[j];
                    if(arr[j]<arr[j-groupNum]){
                        while (j-groupNum>=0 && temp < arr[j-groupNum]){
                            arr[j] = arr[j-groupNum];
                            j-=groupNum;
                        }
                        //当while退出，找到了插入的位置
                        arr[j] = temp;
                    }
                }
                groupNum = groupNum/2;//计算下一轮组数
            }
        }
    }

### 运行结果（卧槽，8万数据，20毫秒）： ###

排序前时间：1606099042282
    排序后时间：1606099042302
    程序执行时间为：0秒！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201121100148361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201121110206395.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201121123416632.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201123074858187.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70