冒泡排序法(BubbleSort)的改进以及效率比较

  共用函数

        private void Swap(int& left, int& right)
        {
            int temp;

            temp = left;
            left = right;
            right =temp;
        }

基本冒泡排序

　　基本冒泡排序的最好、最坏、平均情况下的时间复杂度都为O(n^2)。故算法的平均时间复杂度也为O(n^2)。

算法如下：

 /// <summary>
        ///     冒泡排序的过程很简单，首先将第一个记录的关键字与第
        ///     二个记录的关键字进行比较，若按升序排序，则当第一个记录的
        ///     关键字大于第二个记录的关键字时，将两个记录交换。然后再比
        ///     较第二个记录和第三个记录的关键字。依次类推，直至第n-1个
        ///     记录和第n个记录的关键字进行比较为止。通过这样的一趟冒
        ///     泡排序，结果使得关键字最大的记录被安置在最后一个记录的位
        ///     置上，即它的最终位置。接着进行第二趟冒泡排序，对前n-1个
        ///     记录进行同样的操作，其结果是使关键字次大的记录被安置到
        ///     倒数第二个位置上。这样，通过n一1趟冒泡排序，就将n-1个记
        ///     录安置到相应的最终位置上，剩下的关键字最小的记录就放在
        ///     第一个位置，从而实现了升序排序。
        /// </summary>
        /// <param name="myArray"></param>
        public void BasicBubble(int [] myArray)
        {
            for(int i = 0; i < myArray.Length - 1; i++)          //循环的趟数
            {
                for(int j = 0; j < myArray.Length - 1 - i; j++)//每趟循环的次数
                {
                    if( myArray[j] > myArray[j+1] )
                    {
                        Swap(myArray[i], myArray[i+1]);
                    }
                }
            }
        }

第一种改进：不做无用功

　　这种算法最好的时间复杂度为O(n)。平均，最坏时刻复杂度为O(n^2)。

算法如下：

        /// <summary>
        /// 设置一个标志位，当没有交换的时候这个标志位不会变化，那么说明数据已经
        /// 排序好了，就不需要再进行剩余的循环。只有在标志位被重新设置的情况下才会
        /// 进行剩余的循环。
        /// </summary>
        /// <param name="myArray"></param>
        public static void ImproveBubble1(int [] myArray)
        {
            bool isSorted = false; 

            for(int i = 0; i < myArray.Length - 1 && !isSorted; i++)//只有在没有排序的情况下才继续循环
            {
                isSorted = true;                                                      //设定排序标志
                for(int j = 0; j < myArray.Length - 1 - i; j++)
                {
                    if( myArray[j] > myArray[j+1] )
                    {
                        isSorted = false;                                             //如果是没有排序，就重新设定标志
                        Swap(myArray[i], myArray[i+1]);
                    }
                }
            }
        }

第二种改进：记录犯罪现场

　　算法2最好的时间复杂度为O(n)。平均，最坏时刻复杂度为O(n^2)。

算法如下：

        /// <summary>
        ///     在冒泡排序中，每趟排序实现了将最大(升序)或
        ///     最小(降序)的记录安置到未排序部分的最后位置，即最终位置。
        ///     通过进一步观察研究，由于每趟排序过程中，通过和邻记录关键字两两
        ///     比较，大(升序)或小(降序)的记录在不断地往下沉或往后靠，
        ///     小(升序)或大(降序)的记录在不断往上冒或往前靠。
        ///     每经过一趟排序，在最后次交换位置后而的记录都已经排好序。根据
        ///     上面的思路，对n个记录进行第k趟排序，首先需在第k-1趟排
        ///     序时记下最后交换的位置。然后在第k趟排序时，将第一个记
        ///     录的关键字与第二个记录的关键字进行比较，符合交换条件时，
        ///     进行交换。再比较第二个记录和第三个记录的关键字，依次类
        ///     推，直至第m-1个记录和第m个记录的关键字进行比较，而不
        ///     需要比较至n-k-1个记录。在大部分排序中，m都小于n-k-1
        ///     从而减少了比较趟数和每趟的比较次数。由于在第一趟排序时，
        ///     没有上一趟排序的m值。因此，还要设置m的初始值为n-1。
        /// </summary>
        /// <param name="myArray"></param>
        public static void ImproveBubble2(int[] myArray)
        {
            int m = myArray.Length - 1;
            int k, j;

            while( m > 0 )
            {
                for( k=j=0; j<m; j++)
                {
                    if( myArray[j] > myArray[j+1])
                    {
                        Swap(myArray[j], smyArray[j+1]);
                        k = j; //记录每次交换的位置
                    }
                }
                m = k;        //记录最后一个交换的位置
            }
        }

第三种改进：双向扫描，一网打尽

　　算法最好的时间复杂度为O(n)，最坏时刻复杂度为O(n^2)。

算法如下：

        /// <summary>
        ///  对n个记录进行排序时，设up记录了从前面向后面依次进行扫描时最后的交换位置，
        ///  low记录了从后面向前面依次进行扫描时最前的交换位置。
        ///  由上个改进的冒泡排序的原理可知，up后面的记录和low前面的记录都已有序。
        ///  每趟排序都由两次不同方向的比较、交换组成。第一次是从未排好序的第一个记录开始，
        ///  即从low记录开始，向后依次两两比较，如果不符合条件，则交换之，
        ///  直至比较到未排好序的最后一个记录，即up记录为止。
        ///  同时记下最后一次交换的位置，并存于up。第二次是从未排好序的最后一个记录开始,
        ///  即从up记录开始，向前依次两两比较，如果不符合条件，则交换之，
        ///  直至比较到未排好序的第一个记录，即low记录为止。同时记下最后次交换的位置，
        ///  并存于low. 这样，就完成了一趟排序。
        ///  每趟排序都实现了将未排好序部分的关键字大的记录往后移(升序)，
        ///  关键字小的记录往前移（升序)，从而使两端已排好序（如果是降序，记录移动的方向则相反)。
        ///  未排好序部分的记录的首尾位置分别由low和up指明。
        ///  不断按上面的方法进行排序，使两端已排好序的记录不断增多，
        ///  未排好序部分的记录逐渐减少。即low和up的值不断接近，当low>=up时，
        ///  表明已没有未排好序的记录，排序就完成了。由于在第一趟排序时，
        ///  没有上趟排序的low和up值。因此，还要设置low和up的初始值分别为0和n-1。
        /// </summary>
        /// <param name="myArray"></param>
        public static void ImproveBubble3(int [] myArray)
        {
            int low, up, index, i;
            low = 0;
            up = myArray.Length - 1;
            index = low;

            while( up > low)
            {
                for( i=low; i<up; i++)        //从上向下扫描
                {
                    if(myArray[i]>myArray[i+1])
                    {
                        Swap(ref myArray[i], ref myArray[i+1]);
                        index = i; 
                    }
                }

                up = index;                     //记录最后一个交换的位置
                for(i=up; i>low; i--)             //从最后一个交换位置处从下向上扫描
                {
                    if(myArray[i]<myArray[i-1])
                    {
                        Swap(ref myArray[i], ref myArray[i-1]);
                        index = i;
                    }
                }
                low = index;                    //记录最后一个交换的位置
            }
        }