欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

手把手教你搞懂冒泡排序和选择排序

程序员文章站 2022-03-16 20:08:59
目录冒泡排序原理:从头(左边)开始比较每一对相邻的元素,如果第1个比第2个大,就交换它们的位置,执行完一轮后,最末尾(最右边)就是最大的元素。举例:假设存在数组nums={6,8,2,9,4},对nu...

冒泡排序

原理:

从头(左边)开始比较每一对相邻的元素,如果第1个比第2个大,就交换它们的位置,执行完一轮后,最末尾(最右边)就是最大的元素。

举例:

假设存在数组nums={6,8,2,9,4},对nums数组进行排序

手把手教你搞懂冒泡排序和选择排序

从左往右开始,拿出两个元素进行对比,出现两种情况:

1.左边元素 <= 右边元素,不变

2.左边元素 > 右边元素,交换他们的位置(这里可以写成>=吗?不行,因为会造成排序不稳定)

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

接下来就是新的一轮排序,逻辑跟上图的流程是一样的,不同的是会将最大的元素排除在外,不用进行比较。

手撕代码:

/*
没有使用过优化策略的冒泡排序
 */
public class bubblesort1 {
    //测试数据
    public static int[] nums = {4,1,7,11,9,55};
    //main方法
    public static void main(string[] args){
        //这个for循环每循环完一次,end--,说明就把最大的元素给选出来了
        for (int end = nums.length - 1; end > 0; end--){
            for (int begin = 1; begin <= end; begin++){
                if(nums[begin] < nums[begin - 1]){    //每当发现左边的元素大于右边的元素
                    //交换元素
                    int temp = nums[begin];
                    nums[begin] = nums[begin - 1];
                    nums[begin - 1] = temp;
                }
            }
        }
        //打印验证结果
        for(int num : nums){
            system.out.print(num+"_");
        }
    }
}

时间复杂度为o(n^2),也就是n的平方,不过这是平均时间复杂度

存在最好时间复杂度o(n),那就是数组本来就有序,也就是说只扫描一遍就行了。

优化策略:

由于存在部分有序的情况,例如nums数组为{8,5,2,10,11,12},也就是说10,11,12都没有比较的必要了

优化代码:

/*
使用过优化策略的冒泡排序
 */
public class bubblesort1 {
    public static int[] nums = {4,1,7,11,9,55};
    public static void main(string[] args){
        for (int end = nums.length - 1; end > 0; end--){
            int sortindex = 1;  //记录最后一次交换位置
            for (int begin = 1; begin <= end; begin++){
                if(nums[begin] < nums[begin - 1]){
                    int temp = nums[begin - 1];
                    nums[begin - 1] = nums[begin];
                    nums[begin] = temp;
                    sortindex = begin;
                }
                end = sortindex;
            }
        }
        for(int num : nums){
            system.out.print(num+"_");
        }
    }
}

选择排序

原理:

从数组中找到最大的元素,然后与末尾(最右边)的元素交换位置,执行完一轮后,末尾(最右边)的那个元素就是最大的元素。

举例:

假设存在数组nums={5,8,1,9,3},对nums数组进行排序,准备一个maxidex代表当前最大元素的下标

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

接下来就是新的一轮排序,逻辑跟上图的流程是一样的,不同的是会将最大的元素排除在外,不用进行比较。

手撕代码:

/**
 * 选择排序
 */
public class selectionsort {
    //测试数据
    private static int[] nums = {6,3,2,8,9};
    //main方法
    public static void main(string[] args){
        //这个for循环每循环完一次,end--,说明就把最大的元素给选出来了
        for(int end = nums.length - 1; end > 0; end--){
            int maxindex = 0;   //假设下标0是数组中最大元素
            for(int begin = 1; begin <= end; begin++){  //从左往右开始比较
                if(nums[maxindex] < nums[begin]){   //发现存在一个元素大于假设最大元素
                    maxindex = begin;   //更改最大元素索引
                }
            }
            //最右边一个元素和最大值元素交换位置
            int temp = nums[maxindex];
            nums[maxindex] = nums[end];
            nums[end] = temp;
        }
        //打印结果
        for(int num : nums){
            system.out.print(num+"_");
        }
    }
}

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注的更多文章!