黑马程序员技术交流社区

标题: 插入排序 [打印本页]
作者: 马毅    时间: 2012-12-15 19:01
标题: 插入排序
插入排序是假设一一个数组中的前一段(或者后一段)已经排好序,而将剩下的元素分别插入到合适的位置上,以达到排序目的的一种算法
以下是实现代码,对红色部分有不同的实现方法:
  1.         /// <summary>
  2.         /// 插入排序
  3.         /// </summary>
  4.         /// <param name="arr">要排序的数组</param>
  5.         static void InsertSort1( ref int[] arr)
  6.         {
  7.             int keyValue = 0;
  8.             int pos = 0;
  9.             for (int key = 1; key < arr.Length;key++ )
  10.             {
  11.                 keyValue = arr[key];
  12.                 pos = key - 1;
  13.                                while (pos >= 0 && arr[pos] > keyValue)
  14.                 {
  15.                     arr[pos + 1] = arr[pos];
  16.                     pos--;  
  17.                 }
  18.                 arr[pos + 1] = keyValue;
  19.             }

  21.         }
  22.         /// <summary>
  23.         /// 插入排序
  24.         /// </summary>
  25.         /// <param name="arr">要排序的数组</param>
  26.         static void InsertSort2(ref int[] arr)
  27.         {
  28.             int key;
  29.             for (int i = 1; i < arr.Length;i++ )
  30.             {
  31.                 key = i - 1;
  32.                 while(key >=0 && arr[key] > arr[key+1])
  33.                 {
  34.                     Swap(ref arr[key], ref arr[key + 1]);
  35.                     key --;
  36.                 }
  37.             }
  38.         }
  39.         /// <summary>
  40.         /// 交换两个数的值
  41.         /// </summary>
  42.         /// <param name="i">左值</param>
  43.         /// <param name="j">右值</param>
  44.         static void Swap(ref int i,ref int j)
  45.         {
  46.             int temp = i;
  47.             i = j;
  48.             j = temp;
  49.         }
复制代码
插入排序采用的是减治法,关于减治法的概念可以百度一下(哈哈,偷懒了)
关于其他算法请参考这里


作者: 许庭洲    时间: 2012-12-15 19:47
值得学习ing!
作者: 王晨    时间: 2012-12-15 21:05
受教了,谢谢分享



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2