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

导读:本篇文章讲解 图解解析 + 代码实现:带你手撕冒泡、选择、插入、希尔排序。,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

目录

一、冒泡排序

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循环,将第一个数后的数据遍历一遍,找是否还有比第一个数更小的,记录下来,遍历完毕后将第一个数与最小的数进行交换。然后又确定第二数,找第二个数以后的数,是否还有比第二个数更小的,找到后与第二个数又进行交换,重复上面即可。

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

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

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

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

        以后的每次循环都是按照这种方式,直到最后两个数排完,数据就是有序的了。

 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、基本介绍

        前面我们介绍的选择排序,找到最小的就与前面的进行交换。而插入排序,就是将确定的数的后一位插入到前面即可。图形介绍:

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

        开始,id指向第一个数,mid指向第二个数,然后两个数进行比较。

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

        此时,1 比 3 小,但是3前面没数据了,于是将1插入到3的前面,注意这里是插入,不是交换。下一步 3 比 5 小,于是不用插入。

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

        经过三次比较,确定了 2 的位置在 1 和 3 直接,直接将 2 插入。 

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

        又经过四次比较,找到 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、基本介绍

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

        首先将数组分为两组,3、2、0 为一组,1、5为一组,g = arr.length / 2。

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

        2 和 3 进行判断,3 比 2 大 ,然后进行交换位置,交换后 j = j – g < 0(因为第一次的分为两组,所以 i – 2 )。所以 i++ ,j = i – g

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

        不需要交换, 然后 j = j – g < 0 ,所以 i++ ,j = i – g

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

        3 比 0 大 ,需要交换。然后 j = j – g > 0 , j = j – g

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

        交换后 j = j – g < 0 , i++ > arr.length 了,第一轮结束  

        第二轮:在arr.length / 2的基础上再除2 , 于是 g = 1 ;

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

        然后两两交换,交换后 进行j = j – g > 0 的判断 ,不成立则 i++ , j = i – g ,成立则 j = j – g ,就这样一直循环下去。第二轮后的结果:

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

        第二轮结束后,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;
            }
        }
    }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/119672.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!