2023下半年软件设计师上午题——冒泡排序

时间:2024-05-03 10:55:10

        快速排除法,根据冒泡排序特性,每一趟排序都会确实最大/最小值,故升序两趟后,最后两个元素应该是已经排序好的第二大,和最大的元素,所以排除B,D,再因为每次排序都会两两交换,所以排除A,立即选C。

排序原理

        第一轮,12和5进行比较,5小,放在前面,然后12再和23比较,符合顺序,不动,然后23和6进行比较,6小,23放后面,然后23和2比较,2小,23放在最后,至此,第一轮结束;

        第二轮,5和12比较,顺序符合,不动,然后6和12比较,6小,放前面,12往后移,12再和2比较,2小,则放前面,12放后面,至此,第二轮结束;

        以此类推。。。

拓展

n个元素最多只需要n-1次/趟排序即可完成。

时间复杂度:

Java代码实现

public class Main{

public static void main(String[] args){

    int [] arr = new int[]{12,2,84,65,-51,57,88,11,33};

    int temp = 0;

    for(int i = 0; i<arr.length-1; i++){//遍历数组次数

        for(int j = 0; j<arr.length-1-i; j++ ){//第i次遍历的交换次数

            if(arr[j] > arr[j+1]){

                temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

            }

        }

    }

    //将数组输出

    for(int i = 0 ; i<arr.length ; i++){

        System.out.print(arr[i] + " ");

        }

    }

}

参考:《大话数据结构》

勉励自己,加油,加油!

         时常提醒自己,不要忘了理想,好好生活,为了理想而生活;我有自己的追求,我有自己的理想,勇敢的去捍卫它,勇敢的追寻它!