南京北大青鸟

全国免费电话:400-885-5191

三分钟了解北大青鸟
当前位置:北大青鸟 > 学习园地 > 编程技巧

C#版冒泡排序优化

来源:未知      作者:中博IT教育      发布时间:2015-03-08 12:31:12

之前写了一个C#版冒泡排序的实现。由于之前的版本是用两层for循环来实现的,这个版本的排序还是有进一步优化的空间的。 之前的排序: int temp = 0; for (int i = arr.Length - 1; i 0; i--) { fo
之前写了一个C#版冒泡排序的实现。由于之前的版本是用两层for循环来实现的,这个版本的排序还是有进一步优化的空间的。
之前的排序:
int temp = 0;
for (int i = arr.Length - 1; i > 0; i--)
{
    for (int j = 0; j < i; j++)
    {
        if (arr[j] > arr[j + 1])
        {
            temp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = temp;
        }
    }
}
能够看出,由于有两层for循环的存在,使得整个排序必须要进行(n - 2)!次判断,即使第一次产生的数组就是已经排好序的。
对这个版本的冒泡排序进行优化:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _0301数组的冒泡排序_优化
{
    class Program
    {
        static void Main(string[] args)
        {
            int len = 0;        //数组大小
            int min = 0;        //数组下界
            int max = 0;        //数组上界
 
            Console.WriteLine("下面将产生一个随机数组");
 
            //接收数组大小
            do
            {
                Console.WriteLine("请输入数组大小,它必须是一个小于等于10的正整数:");
                len = int.Parse(Console.ReadLine());
            } while ((len <= 0) || (len > 10));
 
            //接收数组下界
            Console.WriteLine("请输入数组下界,它必须是一个整数:");
            min = int.Parse(Console.ReadLine());
 
            //接收数组上界
            do
            {
                Console.WriteLine("请输入数组上界,它必须是一个整数,并且比数组最小值大,且能让数组容纳{0}个数:", len);
                max = int.Parse(Console.ReadLine());
            } while ((max <= min) || ((max - min + 1) < len));
 
            Console.WriteLine();
            Console.WriteLine("数组长度:{0}\n数组下界:{1}\n数组上界:{2}", len, min, max);
            Console.WriteLine("生成数组如下:");
 
            int iSeed = 6;
            Random ra = new Random(iSeed);
            int[] arr = new int[len];
            //打印原数组的值
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = ra.Next(min, max);
 
                Console.Write(arr[i]);
                if (i < arr.Length - 1)
                {
                    Console.Write(",");
                }
                else
                {
                    Console.WriteLine();
                }
 
            }
 
            //开始进行数组排序
            Console.WriteLine("数组产生完毕,开始排序");
            Console.WriteLine();
 
            #region 原有排序,这种排序必须要比较(n -2)!次
            //int temp = 0;
            //for (int i = arr.Length - 1; i > 0; i--)
            //{
            //    for (int j = 0; j < i; j++)
            //    {
            //        if (arr[j] > arr[j + 1])
            //        {
            //            temp = arr[j + 1];
            //            arr[j + 1] = arr[j];
            //            arr[j] = temp;
            //        }
            //    }
            //}
            #endregion
 
            //这种排序最多比较(n - 2)!次,但如果当前已是最优排序结果则直接停止比较
            int temp = 0;
            bool swapped = true;
            do
            {
                swapped = false;
 
                for (int i = 0; i < arr.Length - 1; i++)
                {
                    if (arr[i] > arr[i + 1])
                    {
                        temp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = temp;
                        swapped = true;
                    }
                }
 
            } while (swapped);
 
            //打印排序后的结果
            Console.WriteLine("排序后结果:");
 
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i]);
                if (i < arr.Length - 1)
                {
                    Console.Write(",");
                }
                else
                {
                    Console.WriteLine();
                }
 
            }
            Console.WriteLine("程序结束");
            Console.ReadKey();
        }
    }
}
这个版本的排序将外层循环改成了do...while()实现,并设置一个标识变量swapped,如果本次内部循环未进行一次数据置换则说明数组序列已实现最优,立刻结束外层循环。这种排序最多比较(n - 2)!次,但如果当前已是最优排序结果则直接停止比较。

其实外层循环是for循环也可以实现这种效果,但相对来说do...while()写起来更优雅一些。
(责任编辑:南京北大青鸟)

分享到:

抢免费试听名额

名额仅剩66名

教育改变生活

WE CHANGE LIVES