排序算法之插入排序、希尔排序、归并排序(C#)

插入排序

两次for循环，外层从数组第二位i=1开始，内层for循环由i向前进行判断，大于则将该位置与遍历位置交换。此时注意，不能按i的位置获取元素，应将该元素暂存，因为交换时对应i位置元素值会变换。 c#代码如下

/// <summary> /// 插入排序 /// </summary> /// <param name="array"></param> public int[] InsertSort(int[] array) { for (int i = 1; i < array.Length; i++) { int temp = array[i]; for (int j = i - 1; j >= 0; j--) { if (temp > array[j]) { array[j + 1] = array[j]; array[j] = temp; } else { break; } } } return array; }

希尔排序

希尔排序是插入的变种，插入排序比较的相邻两个元素，而希尔排序则是先将数组基本排序后，在进行相邻遍历。引用菜鸟教程的话是：

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

C#代码如下

/// <summary> /// 希尔排序 /// </summary> /// <param name="array"></param> /// <returns></returns> public int[] ShellSort(int[] array) { int gap = array.Length / 2; while (gap>=1) { for (int i = 0; i < array.Length; i++) { for (int j = i + gap; j < array.Length && array[i] > array[j]; j+= gap) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } gap /= 2; } return array; }

归并排序

（下方的代码执行效率很低，具体原因以及优化后的代码可以看我新写的文章排序算法之归并排序算法优化），学习归并排序就直接看这篇新文章吧 。 归并排序使用的是递归，将数组分成左右两个集合，递归直至左右集合只剩一个元素，将两个元素排序后向上返回。 C#代码如下 （下方代码效率低，学习归并请移步至新文章）排序算法之归并排序算法优化

/// <summary> /// 归并排序 /// </summary> /// <returns></returns> public int[] MergeSort(int[] array) { int length = array.Length; int half = length / 2; if (length <= 1) { return array; } //数组截取成左右两个 int[] left = array.Take(half).ToArray(); int[] right = array.Skip(half).ToArray(); //递归 直至分成 左右两个只含一个元素时 排序后 向上返回 left = MergeSort(left); right = MergeSort(right); return MergeSortDouble(left, right); } /// <summary> /// 对两个数组排序后合并成一个返回 /// </summary> /// <param name="left"></param> /// <param name="right"></param> /// <returns></returns> public int[] MergeSortDouble(int[] left, int[] right) { List<int> li = new List<int>(); int leftPositon = 0, rightPosition = 0; while (left.Count() > leftPositon && right.Count() > rightPosition) { if (left[leftPositon] > right[rightPosition]) { li.Add(right[rightPosition]); rightPosition++; } else { li.Add(left[leftPositon]); leftPositon++; } } while (left.Count() > leftPositon) { li.Add(left[leftPositon]); leftPositon++; } while (right.Count() > rightPosition) { li.Add(right[rightPosition]); rightPosition++; } return li.ToArray(); }