C#：冒泡排序，已经排好序的优化

第一层循环，i从 0到max-1 第二个循环，j从0到max-i-1 每次比较j与j 1的大小，如果发生位置交换，hasExchagend置true 如果第一次冒泡没发生交换，hasExchagend == false，说明已经全部是排好顺序的，直接break

代码语言：javascript复制

public static void BubbleSort(int[] array)
        {
            bool hasExchagend = false;
            for (int i = 0; i < array.Length - 1; i  )
            {
                hasExchagend = false;
                for (int j = 0; j < array.Length - 1 -i; j  )
                {
                    if (array[j] < array[j   1])
                    {
                        Exchange(ref array[j], ref array[j   1]);
                        hasExchagend = true;
                    }
                }
                if(!hasExchagend)
                {
                    return;
                }
            }
        }

测试

已经排好顺序的数组int[] array = new int[] { 1, 2,3, 4, 5, 6 }; 只要循环5次得到结果

此算法中代码为2层嵌套循环，外层循环执行（n-1）次，内层循环平均执行n/2次，故在不考虑代码中return语句的情况下，时间复杂度为O(n^2)

最佳情况下，只执行一遍循环的时间复杂度为O(n). 最差o(n^2),就是完全执行2次 平均o(n^2)

源码

https://github.com/luoyikun/UnityForTest SortScene场景

c# 测试 算法 优化 源码

0 人点赞