大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 三大初级排序算法

三大初级排序算法

关键词:排序算法三大初级排序算法  阅读(743) 赞(11)

[摘要]本文主要是对三大初级排序算法的讲解,希望对大家学习三大初级排序算法有所帮助。

  1、冒泡排序

  冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉,较小的数据上升。它是O(n^2)的算法。

  2、插入排序

  插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。

  3、Shell排序

  Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。平均效率是O(nlogn)。

  冒泡排序C#实现:

  /// <summary>

  /// 冒泡排序

  /// </summary>

  public class BubbleSort : ISort

  {

  public int[] Sort(int[] array)

  {

  if (array != null)

  {

  for (int i = 0; i < array.Length; i++)

  {

  for (int j = 1; j < array.Length - i; j++)

  {

  Swap(ref array[j - 1], ref array[j]);

  }

  }

  }

  return array;

  }

  public static void Swap(ref int int1, ref int int2)

  {

  if (int1 > int2)

  {

  int temp = int1;

  int1 = int2;

  int2 = temp;

  }

  }

  }

  插入排序C#实现:

  /// <summary>

  /// 插入排序

  /// </summary>

  public class InsertSort : ISort

  {

  public int[] Sort(int[] array)

  {

  if (array != null)

  {

  int k = 1;//使用k变量,后面更好的扩展到Shell排序

  for (int i = k; i < array.Length; i++)

  {

  int current = array[i];

  int preIndex = i - k;

  while (preIndex >= 0 && preIndex < array.Length && current < array[preIndex])

  {

  array[preIndex + k] = array[preIndex];

  preIndex = preIndex - k;

  }

  array[preIndex + k] = current;

  }

  }

  return array;

  }

  }

  Shell排序C#实现:

  /// <summary>

  /// shell排序

  /// </summary>

  public class ShellSort : ISort

  {

  public int[] Sort(int[] array)

  {

  if (array != null)

  {

  int[] list = { 9, 5, 3, 2, 1 };

  foreach (int k in list)

  {

  for (int i = k; i < array.Length; i++)

  {

  int current = array[i];

  int preIndex = i - k;

  while (preIndex >= 0 && preIndex < array.Length && current < array[preIndex])

  {

  array[preIndex + k] = array[preIndex];

  preIndex = preIndex - k;

  }

  array[preIndex + k] = current;

  }

  }

  }

  return array;

  }

  }

 

  性能测试代码:

  class Program

  {

  public static Random re = new Random();

  static void Main(string[] args)

  {

  Stopwatch stw1 = new Stopwatch();

  Stopwatch stw2 = new Stopwatch();

  Stopwatch stw3 = new Stopwatch();

  int[] intArray1 = GetArray(int.MaxValue/100000);

  int[] intArray2 = GetArray(int.MaxValue/100000);

  int[] intArray3 = GetArray(int.MaxValue/100000);

  ISort sort1 = new BubbleSort();//冒泡排序

  stw1.Start();

  int[] result1 = sort1.Sort(intArray1);

  stw1.Stop();

  Console.WriteLine("输出排序的结果(冒泡排序)");

  Console.WriteLine("程序共运行时间:" + stw1.Elapsed.ToString());

  ISort sort2 = new InsertSort();//插入排序

  stw2.Start();

  int[] result2 = sort2.Sort(intArray2);

  stw2.Stop();

  Console.WriteLine("输出排序的结果(插入排序)");

  Console.WriteLine("程序共运行时间:" + stw2.Elapsed.ToString());

  ISort sort3 = new ShellSort();//Shell排序

  stw3.Start();

  int[] result3 = sort3.Sort(intArray3);

  stw3.Stop();

  Console.WriteLine("输出排序的结果(Shell排序)");

  Console.WriteLine("程序共运行时间:" + stw3.Elapsed.ToString());

  //输出排序的结果

  //OutputResult(result1, result2, result3);

  Console.ReadKey();

  }

  }



相关评论