Java实现冒泡排序和选择排序

朱雀 2021-03-11 15:08 596阅读 0赞

冒泡排序:依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。  
冒牌排序是稳定排序法。

代码如下:

/**
         * 冒泡排序
         *      依次比较相邻的两个元素,如果前边的元素大于后边的元素则交换
         *      这样每次先排好的是最后一位
         *     3  1  6  8  0
         *     1  3  6  0  8   第0次比较:4次   从第一位开始到最后一位,排好了最后一位
         *     1  3  0  6  8   第1次比较:3次   从第一位开始到倒数第二位,排好了倒数第二位
         *     1  0  3  6  8   第2次比较:2次   ...
         *     0  1  3  6  8   第3次比较:1次   ...
         *     共比较4次
         *     完成!
         */
        @Test
        public void testBubbleSort(){
            // 准备待排序的数组
            int[] arr = {3,1,6,8,0};
    
            // 定义一个flag,用来记录上一轮是否有元素进行交换,
            // 如果上一轮没有元素进行交换,说明已经排序完成,停止排序(优化)
            boolean flag;
    
            for (int i = 0; i < arr.length - 1; i++) {//外层控制的是比较的轮数
                //每轮初始flag为true
                flag = true;
                for (int j = 0; j < arr.length - i - 1; j++) {//内层控制的是每轮比较的次数
    
                    // 比较相邻两数的大小,如果前边的数大于后边的数,则交换位置
                    if (arr[j] > arr[j+1]){
    
                        // 交换位置
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        //如果发生交换则flag改为false
                        flag = false;
                    }
                }
                // 如果flag为true,则说明排序已经完成,结束循环
                if (flag){
                    break;
                }
            }
            System.out.println(Arrays.toString(arr));//[0, 1, 3, 6, 8]
        }

选择排序：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，直至有序。  
选择排序是不稳定排序法。  
代码如下：

/**
         * 选择排序 : 拿每次循环的第一个元素i依次与后边的每个元素j比较,
         *            如果i > j,则交换两元素的位置,每轮循环结束后会将较小的数往前排,
         *            下次循环从本次的元素的后边一个元素开始
         * 3  1  8  6  0
         * 0  1  3  8  6    第0次比较:4次   从第一位开始到最后一位,排好了第一位
         * 0  1  3  8  6    第1次比较:3次   从第二位开始到最后一位,排好了第二位
         * 0  1  3  8  6    第2次比较:2次   ...
         * 0  1  3  8  6    第3次比较:1次   ...
         */
        @Test
        public void testSelectionSort(){
            // 准备待排序的数组
            int[] arr = {3,1,8,6,0};
    
            for (int i = 0; i < arr.length - 1; i++) {//外层控制循环轮数
    
                for (int j = i + 1; j < arr.length; j++) {//内层控制每轮循环的次数
    
                    // 拿每次循环的第一个元素i依次与后边的每个元素j比较
                    if (arr[i] > arr[j]){
    
                        // 交换位置
                        int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));//[0, 1, 3, 6, 8]
        }

排序算法稳定性：  
排序前后相同的元素前后的位置不会改变的成为稳定排序算法，否则则是不稳定排序算法。  
如：数组中存在元素 arr\[i\] = arr\[j\] ,且 arr\[i\] 在 arr\[j\] 的前面,若使用算法排序后 arr\[i\] 和 arr\[j\] 的前后顺序不会发生改变,则说明该排序算法稳定，否则为不稳定排序算法。