冒泡排序法笔记

骑猪看日落 2024-02-17 19:01 28阅读 0赞

#### **冒泡排序简介** ####

冒泡排序法是一种简单并且常用的排序算法。其基本目的是对数组或列表中的数据进行由小到大的排序。

//以下为冒泡排序中一次排序的逻辑，其中array是目标数组，count为数组长度
    for(int i = 0; i < count - 1; i++)
    {
        if(array[i] > array[i+])
        {
            int temp = array[i];
            array[i] = array[i+1];
            array[i+1] = temp;
        }
    }

由上面的代码片段可以看出，冒泡排序的实质就是从第一个元素开始，将第i位与第i+1位的元素进行比较。
        如果前一位大于后一位就进行对掉，如果前一位小于或者等于后一位则不做调换。
        例如：
        //给定一个数组
        int[] array = new int[]{50, 10, 7, 3, 1};
        count = array.length //count = 5
        此数组经过一次以上的for循环后将会变为{10, 7, 3, 1, 50}
        可以看出，50从第一位被调换到了最后一位，这就是冒泡排序法。但是只经过一次排序还无法将所有元素的位置进行正确的定位。
        所以需要进行第二次排序，结果为{7, 3, 1, 10, 50};
        第三次排序，结果为{3, 1, 7, 10, 50};
        第四次排序，结果为{1, 3, 7, 10, 50};
        可见，通过4次排序后最终这个有5个元素的int类型数组已经变成了一个由小到大排序的数组。
        所以冒泡排序法的基础原理代码为：

//进行count-1次排序，将数组进行完全的排序
    for(int j = 0; j < count - 1; j++)
    {
        //单独排序一次的逻辑
        for(int i = 0; i < count - 1; i++)
        {
            if(array[i] > array[i+])
            {
                int temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
        }
    }

--------------------

##### **第一次优化** #####

由以上示例可以看出，因为在第一次进行排序时就已经把数组中最大的元素（50）排到了最后一位。
        所以在第二次排序时，实际上完全不需要讲当前最大元素（10）和最后一个元素（50）进行比较。
        而第三次排序时，也不需要讲当前最大元素（7）后最后两个元素比较。
        以此类推：

//经过优化过的代码片段，最外层的for循环没有变化。
    for(int j = 0; j < count - 1; j++)
    {
        //单独排序一次的逻辑，随着排序的进行，需要比较的元素数量会减少
        //第一次时需要将数组中的所有元素进行比较，以后逐次递减
        for(int i = 0; i < count - 1 - j; i++)
        {
            if(array[i] > array[i+])
            {
                int temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
        }
    }

通过以上优化，可以减少不必要的运算，增加整体运算速度。

--------------------

##### **第二次优化** #####

如果所需要比较的示例是类似{5,4,3,2,1}这种类型的数组的话，确实需要进行满次数4次的循环比较才可以将所有元素进行比较。
        但如果是类似{5,1,2,3,4},或者更加极端点{1,2,3,4,5}这种已经是从小到大进行排序的数据时。
        即使用上面优化过一次的算法也会造成不必要的浪费，所以才会有以下的优化方案：

//使用冒泡排序法进行比较的函数，传入一个int型数组
    void Sort(int[] sortArray)
    {
        //定义一个bool开关，对排序的最外层循环进行管理
        bool swapped = true;
        do
        {
            //设置开关为false
            swapped = false;
            for (int i = 0; i < sortArray.Length - 1; i++)
            {
                if (sortArray[i] > sortArray[i + 1])
                {
                    int temp = sortArray[i];
                    sortArray[i] = sortArray[i + 1];
                    sortArray[i + 1] = temp;
                    //如果进行了前后调换则说明排序没有完成。
                    //需要继续进行，将开关设置为true
                    swapped = true;
                }
            }
        } while (swapped);
    }

此函数中的算法的核心部分和前面的算法没有区别，有区别的是外层的循环比较部分。
        如需要比较的数组为{1,2,3,4,5}则在第一比较调用函数后，swapped这个控制开关就会变为false。
        因为说明没有需要继续比较的必要了，所以while循环也会结束。
        在处理不是必须所有元素都进行比较的数据时，此种优化算法要比之前的算法更加高效。

--------------------

##### **更进一步，第三次优化** #####

通过对NGUI中的BetterList类的学习，可以发现以上排序方法还有更进一步优化的空间。
        以下为NGUI中的BetterList类中关于排序的代码：

public void Sort (CompareFunc comparer)
        {
            int start = 0;
            //size是BetterList中的数组长度
            int max = size - 1;
            bool changed = true;
    
            while (changed)
            {
                changed = false;
    
                for (int i = start; i < max; ++i)
                {
                    if (comparer(buffer[i], buffer[i + 1]) > 0)
                    {
                        T temp = buffer[i];
                        buffer[i] = buffer[i + 1];
                        buffer[i + 1] = temp;
                        changed = true;
                    }
                    else if (!changed)
                    {
                        start = (i == 0) ? 0 : i - 1;
                    }
                }
            }
        }
    //约定当left大于right返回-1，left小于right返回1，相等返回0
    public delegate int CompareFunc (T left, T right);

可以看出，和第二次优化的大部分代码是相同的，最大的不同有两个地方：

1、排序条件的不同。  
由于使用了委托，使具体的判断条件可以根据使用场景不同而更加灵活的定义。  
并且由于BetterList类的数据为泛型（T）类型，所以通过委托来定义排序条件更加方便。  
相比之下，前两次的优化由于只使用了int类型数组，并且将判断条件直接写死在排序逻辑中，不利于维护和扩展。

2、添加了一个叫`start`的指针，并通过`else if`的分支对其进行维护。  
添加start指针并进行维护是对第二次优化的进一步优化。  
`changed`是一个开关变量，当`changed = true`时，表示已经发生过排序；`changed = false`时，表示顺序正常。  
此方法首先在for循环中进行了一次判断，如果需要排序`changed`就会被赋值为`false`。  
此时即使后面有不需要调换位置的地方，也不会执行对`start`的维护。  
所以，`else if(!changed){}`这个分支可以保证当前位置之前的所有元素均已排序完成。  
通过设置start指针，可以使下次执行`while`循环时从当前start处继续排序，而此时start位置前的元素都无需再次排序。