冒泡排序及其简单优化

Java基础

浏览数:110

2019-8-21

AD:资源代下载服务

冒泡排序是最基础的排序算法,每一轮的冒泡都是把最小的或者最大的冒到一端,是一种稳定的排序算法,时间复杂度为O(n^2)

原始的冒泡排序

    //冒泡排序
    void BubbleSort1(int* arr, int size)
    {
        int i = 0, j = 0;
    
        for (i = 0; i < size - 1; i++)//一共要排序size-1次
        {
            for (j = 0; j < size - 1 - i; j++)//选出该趟排序的最大值往后移动
            {
                if (arr[j] > arr[j + 1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    
    }

优化一:优化外层循环

在某一次外层循环发现没有发生交换时说明冒泡已经结束,因为接下来的循环区间都比这一次的要小,所以接下来的冒泡就无意义,则提前退出循环。优化后的冒泡排序最好时间复杂度是O(n),最坏时间复杂度是O(n2),平均时间复杂度是O(n2)

    //冒泡排序优化1
    void BubbleSort2(int* arr, int size)
    {
        int i = 0, j = 0;
    
        for (i = 0; i < size - 1; i++)//一共要排序size-1次
        {
            //每次遍历标志位都要先置为0,才能判断后面的元素是否发生了交换
            int flag = 0;
    
            for (j = 0; j < size - 1 - i; j++)//选出该趟排序的最大值往后移动
            {
                if (arr[j] > arr[j + 1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = 1;//只要有发生了交换,flag就置为1
                }
            }
    
            //判断标志位是否为0,如果为0,说明后面的元素已经有序,就直接return
            if (flag == 0)
            {
                return;
            }
        }
    }
    

优化2:优化内层循环

在每趟扫描中,记住最后一次交换发生的位置lastExchange,(该位置之后的相邻记录均已有序,因为正在冒的数是当前最小的,如果该数停止往上冒了,且后面没有冒泡的操作了,说明后面的数比这个数都小,且已经排好序)。下一趟排序开始时,R[1..lastExchange-1]是无序区,R[lastExchange..n]是有序区。这样,一趟排序可能使当前无序区扩充多个记录,因此记住最后一次交换发生的位置lastExchange,从而减少排序的趟数。

    void BubbleSort3(int* arr, int size)
    {
        int i = 0, j = 0;
        int k = size - 1,pos = 0;//pos变量用来标记循环里最后一次交换的位置  
        
        for (i = 0; i < size - 1; i++)//一共要排序size-1次
        {
            //每次遍历标志位都要先置为0,才能判断后面的元素是否发生了交换
            int flag = 0;
    
            for (j = 0; j <k; j++)//选出该趟排序的最大值往后移动
            {
                if (arr[j] > arr[j + 1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = 1;//只要有发生了交换,flag就置为1
                    pos = j;//循环里最后一次交换的位置 j赋给pos
                }
            }
    
            k = pos;
            //判断标志位是否为0,如果为0,说明后面的元素已经有序,就直接return
            if (flag == 0)
            {
                return;
            }
        }
    }


    

作者:XJBT