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

訾博ZiBo

发布于 2025-01-06 16:37:25

1920

文章被收录于专栏：全栈开发工程师全栈开发工程师

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

0、警醒自己

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

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

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

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

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

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

一、冒泡排序

1、基本介绍

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

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

2、思路图解

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、思路图解

第一趟找到最小的是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、思路图解

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时，整个文件恰被分成一组，算法便终止；

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秒！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-06，如有侵权请联系 cloudcommunity@tencent.com 删除

排序

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度