排序算法

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace ConsoleApp4
  8 {
  9     class Program
 10     {
 11         static void Main(string[] args)
 12         {
 13             {
 14                 //直接插入排序
 15                 int[] arr = { 23, 22, 12, 30, 10 };
 16                 Console.WriteLine("待排序的数组为: ");
 17                 PrintArr(arr);
 18                 SortDirect(arr);
 19                 Console.WriteLine("直接插入排序后的数组为: ");
 20                 PrintArr(arr);
 21             }
 22             {
 23                 //折半插入排序
 24                 int[] arr = { 8,18,20,33,39,21 };
 25                 Console.WriteLine("待排序的数组为: ");
 26                 PrintArr(arr);
 27                 HalfSort(arr);
 28                 Console.WriteLine("折半插入排序后的数组为: ");
 29                 PrintArr(arr);
 30             }
 31             
 32             Console.Read();
 33         }
 34 
 35         private static void PrintArr(int[] arr)
 36         {
 37             foreach (var item in arr)
 38             {
 39                 Console.Write(item + "  ");
 40             }
 41             Console.WriteLine();
 42         }
 43 
 44 
 45         /// <summary>
 46         /// 直接插入排序
 47         /// </summary>
 48         /// <param name="arr">待排序数组</param>
 49         static void SortDirect(int[] arr)
 50         {
 51 
 52             /*
 53               待排序数组{23, 22, 12, 30, 10 }          从小到大排序
 54               第一轮排序  22 23 12, 30, 10             22 和 23比较     
 55               第二轮排序  12  22  23  30  10           12   和  23 比较   换位->    12  和   22 比较  换位
 56               第三轮排序   12  22  23  30  10          30  和  23 比较     
 57               第四轮排序   10  12  22  23  30          10 和  30 比较 换位   ->   10  和 23  比较  换位->  10 和22  比较 换位  ->  10 和 12 比较  换位
 58 
 59             */
 60             for (int i = 1; i < arr.Length; i++)
 61             {     //假设已经到了第二轮排序  待排 22 23 12, 30, 10          i = 2   
 62                 var curValue = arr[i];         //curValue = 12
 63                 var temp = i;         //temp = 2
 64                 while(temp > 0 &&(arr[temp-1] > curValue)) //1.arr[temp-1] = 23  > curValue=12   2.    arr[temp-1] = 22   > curValue = 12
 65                 {
 66                     arr[temp] = arr[temp-1];        //1.  第三位变成23     2.   第二位变成  22
 67                     temp--;                           //1.temp = 1        2.  temp = 0
 68                 }
 69                 arr[temp] = curValue;      //最小的始终放到最前边
 70             }
 71         }
 72 
 73         /// <summary>
 74         /// 折半插入排序
 75         /// </summary>
 76         /// <param name="arr">{8,18,20,33,39,21}</param>
 77         static void HalfSort(int[] arr)
 78         {
 79             int len = arr.Length;              //数组长度6
 80             int insertValue = arr[len- 1];     //待插入数据为21
 81 
 82             int low = 0;
 83             int high = len - 2;     //4
 84             while (low <= high)
 85             {
 86                 int middle = (low + high) / 2;          //2
 87                 if(insertValue < arr[middle])          //1.  21< 20  false     2. 21 < 33 true
 88                 {
 89                     high = middle - 1;                 //2. high =2
 90                 }
 91                 else                
 92                 {
 93                     low = middle + 1;                 //1.low = 3   high=4    2. low=3  high=2
 94                 }
 95             }
 96             for (int j = len -1; j > high+1; j--)       //1.j = 5  j  > 3  j--
 97             {
 98                 arr[j] = arr[j - 1];               //待插入位置后数据后移 
 99             }
100             arr[high + 1] = insertValue;
101         }
102     }
103 }