C#版冒泡排序优化
之前写了一个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()写起来更优雅一些。
运行效果:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。