冒泡排序及优化

小鱼儿 2022-01-12 16:45 188阅读 0赞

# 思路 #

![冒泡排序及优化][watermark_size_16_text_QDUxQ1RP5Y2a5a6i_color_FFFFFF_t_100_g_se_x_10_y_10_shadow_90_type_ZmFuZ3poZW5naGVpdGk]

# 代码 #

package com.zgz;
    
    /**
     * 冒泡排序
     *  优化思路：
     *      1. 引入标志位，判断数列是否有序，若有序则跳出不执行剩下的几轮循环
     *      2. 界定数列有序区(3，4，2，1，5，6，7，8), 记录最后一次交换的位置，更新无序数列的边界
     * @author guozhenZhao
     * @date 2019年4月4日
     */
    public class BubbleSort {
    
        public static void main(String[] args) {
            int[] arr = {1,2,3,4,5,6,8,9,5,0};
            sort(arr);
            print(arr);
        }
    
        static void sort(int[] arr) {
            //最好时间复杂度O(n)
            for(int i=0; i<arr.length; i++) {
                //标志位，如果上一轮冒泡排序已经全部有序,则减少循环次数
                Boolean isSorted = true;
                //无序数列的边界
                int sortBorder = arr.length-1;
                //最后一次交换的位置
                int lastChangePos = 0;
                for(int j=0; j<arr.length-1-i; j++) {
                    if(arr[j]>arr[j+1]) {
                        swap(arr, j, j+1);
                        //进行了排序，说明元素无序
                        isSorted = false;
                        //记录元素交换的位置
                        lastChangePos = j;
                    }
                }
                //把无序数列的边界更新为最后一次交换元素的位置
                sortBorder = lastChangePos;
                if(isSorted) {
                    break;
                }
            }
        }
    
        static void swap(int[] arr, int i, int j) {
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i]= temp;
        }
    
        static void print(int[] arr) {
            for(int i=0; i<arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
            System.out.println();
        }
    
    }

转载于:https://blog.51cto.com/13416247/2374362

[watermark_size_16_text_QDUxQ1RP5Y2a5a6i_color_FFFFFF_t_100_g_se_x_10_y_10_shadow_90_type_ZmFuZ3poZW5naGVpdGk]: https://s1.51cto.com/images/blog/201904/04/1e1f66a4acfd508731ca55dd34b2dff4.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=