上一讲大概介绍了一个排序算法的概念与内存结构图，主要选自《算法精解》，各人认为，这本书写的还是不错的，大家可以直接下载epub版，然后在面度阅读APP上看，挺方便的！其实，学习，很简单！
排序是指将元素集合按照规定的顺序排列。通常有两种排序方法，升序排列和降序排列。例如，对整数集{5,2,7,1}进行升序排列，结果为{1,2,5,7}，对其进行降序排列结果为{7,5,2,1}。总的来说，排序的目的是使数据能够以更有意义的形式表现出来。虽然排序最显著的应用是排列数据以显示它，但它往往可以用来解决其他的问题，特别是作为某些已成型算法的一部分。
总的来说，排序算法分为两大类：比较排序和线性时间排序。比较排序依赖于比较和交换来将元素移动到正确的位置上。令人惊讶的是，并不是所有的排序算法都依赖于比较。对于那些确实依赖于比较来进行排序的算法来说，它们的运行时间往往不可能小于O（nlg n）。对于线性时间排序，从它的名字就可以看出，它的运行时间往往与它处理的数据元素个数成正比，即为O（n）。遗憾的是，线性时间排序依赖于数据集合中的某些特征，所以我们并不是在所有的场合都能够使用它。某些排序算法只使用数据本身的存储空间来处理和输出数据（这些称为就地排序），而有一些则需要额外的空间来处理和输出数据（虽然可能最终结果还是会拷贝到原始的内存空间中）。
/// <summary> /// 排序算法 /// 作者：仓储大叔 /// 代码来源：部分自写，部分网上摘录，都经过测试可以放心使用 /// </summary> public class SortHelper { #region Public Methods /// <summary> /// 插入排序 /// </summary> public static void InsertSort(List<int> list) { /* * 复杂度 O（n^2） * 插入排序从根本上来说，就是每次从未排序的数据集中取出一个元素，插入已排好序的数据集中。在以下所展示的实现中，两个数据集都存放在data中，data是一块连接的存储区域。最初，data包含size个无序元素。随着issort的运行，data逐渐被有序数据集所取代，直到issort返回（此时，data已经是一个有序数据集）。虽然实现插入排序用到连续的存储空间，但它也能用链表来实现（并不是所有的排序都可以使用链表来实现），并且效率不差。 */ for (int j = 1; j < list.Count; j++) { int i = j - 1; int currnet = list[j]; while (i >= 0 && currnet > list[i]) { list[i + 1] = list[i]; i--; } list[i + 1] = currnet; } } /// <summary> /// 快速排序 /// </summary> /// <param name="list">目标数组</param> /// <param name="left">子表的起始位置</param> /// <param name="right">子表的终止位置</param> public static void QuickSort(List<int> list, int left, int right) { /* * 复杂度 O（nlg^n） * 描述 利用快速排序将数组data中的元素进行排序。数组中的元素个数由size决定。而每个元素的大小由esize决定。参数i和k定义当前进行排序的两个部分，其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比较元素大小。其函数功能与issort中描述的一样。当qksort返回时，data包含已排序的元素 */ if (left < right) { int i = Division(list, left, right); //对枢轴的左边部分进行排序 QuickSort(list, i + 1, right); //对枢轴的右边部分进行排序 QuickSort(list, left, i - 1); } } /// <summary> /// 归并排序 /// </summary> /// <param name="array">目标数组</param> /// <param name="first">子表的起始位置</param> /// <param name="last">子表的终止位置</param> public static void MergeSortFunction(List<int> array, int first, int last) { /* * 复杂度 O（nlg^n） * 描述 利用归并排序将数组data中的元素进行排序。数组中的元素个数由size决定。而每个元素的大小由esize决定。参数i和k定义当前进行排序的两个部分，其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比较元素大小。其函数功能与issort中描述的一样。当mgsort返回时，data中包含已排序的元素。 */ if (first < last) //子表的长度大于1，则进入下面的递归处理 { int mid = (first + last) / 2; //子表划分的位置 MergeSortFunction(array, first, mid); //对划分出来的左侧子表进行递归划分 MergeSortFunction(array, mid + 1, last); //对划分出来的右侧子表进行递归划分 MergeSortCore(array, first, mid, last); //对左右子表进行有序的整合（归并排序的核心部分） } } /// <summary> /// 计数排序 /// </summary> /// <param name="arrayToSort">要排序的数组</param> /// <param name="maxValue">数组的最大值加一</param> /// <returns>计数排序后的结果</returns> public static List<int> CountingSort(List<int> arrayA, int arrange) { /* 复杂度 O（n+k），n为要排序的元素的个数，k为data中最大的整数加1。 * 计数排序是一种高效的线性排序，它通过计算一个集合中元素出现的次数来确定集合如何排列。不同于之前介绍的一些算法是基于比较的，计数排序不需要进行元素比较，而且它的运行效率要比效率为O（nlg n）比较排序高。 */ int[] arrayResult = new int[arrayA.Count]; int[] arrayTemp = new int[arrange + 1]; for (int i = 0; i <= arrange; i++) { arrayTemp[i] = 0; } for (int j = 0; j < arrayA.Count; j++) { arrayTemp[arrayA[j]] += 1; } for (int k = 1; k <= arrange; k++) { arrayTemp[k] += arrayTemp[k - 1]; } for (int m = arrayA.Count - 1; m >= 0; m--) { arrayResult[arrayTemp[arrayA[m]] - 1] = arrayA[m]; arrayTemp[arrayA[m]] -= 1; } return arrayResult.ToList(); } /// <summary> /// 冒泡排序 /// </summary> /// <param name="arr"></param> public void EbullitionSort(List<int> arr) { /* * 复杂度O(n^2) * 对1至n个记录，在第i趟排序中设置标志flag:=true，未排序的标志。从下往上扫描，以j作为内层循环变量，共做n-i次比较。在第j趟比较中，若r[j+1]<r[j]则交换，并至flag为false。在一趟排序结束后，若flag为true，则终止排序。 */ int i, j, temp; bool done = false; j = 1; while ((j < arr.Count) && (!done))//判断长度 { done = true; for (i = 0; i < arr.Count - j; i++) { if (arr[i] > arr[i + 1]) { done = false; temp = arr[i]; arr[i] = arr[i + 1];//交换数据 arr[i + 1] = temp; } } j++; } } #endregion #region Private Methods /// <summary> /// 归并排序的核心部分：将两个有序的左右子表（以mid区分），合并成一个有序的表 /// </summary> /// <param name="array"></param> /// <param name="first"></param> /// <param name="mid"></param> /// <param name="last"></param> private static void MergeSortCore(List<int> array, int first, int mid, int last) { int indexA = first; //左侧子表的起始位置 int indexB = mid + 1; //右侧子表的起始位置 int[] temp = new int[last + 1]; //声明数组（暂存左右子表的所有有序数列）：长度等于左右子表的长度之和。 int tempIndex = 0; while (indexA <= mid && indexB <= last) //进行左右子表的遍历，如果其中有一个子表遍历完，则跳出循环 { if (array[indexA] <= array[indexB]) //此时左子表的数 <= 右子表的数 { temp[tempIndex++] = array[indexA++]; //将左子表的数放入暂存数组中，遍历左子表下标++ } else//此时左子表的数 > 右子表的数 { temp[tempIndex++] = array[indexB++]; //将右子表的数放入暂存数组中，遍历右子表下标++ } } //有一侧子表遍历完后，跳出循环，将另外一侧子表剩下的数一次放入暂存数组中（有序） while (indexA <= mid) { temp[tempIndex++] = array[indexA++]; } while (indexB <= last) { temp[tempIndex++] = array[indexB++]; } //将暂存数组中有序的数列写入目标数组的制定位置，使进行归并的数组段有序 tempIndex = 0; for (int i = first; i <= last; i++) { array[i] = temp[tempIndex++]; } } /// <summary> /// 获取按枢轴值左右分流后枢轴的位置 /// </summary> /// <param name="list"></param> /// <param name="left"></param> /// <param name="right"></param> /// <returns></returns> private static int Division(List<int> list, int left, int right) { while (left < right) { int num = list[left]; //将首元素作为枢轴 if (num > list[left + 1]) { list[left] = list[left + 1]; list[left + 1] = num; left++; } else { int temp = list[right]; list[right] = list[left + 1]; list[left + 1] = temp; right--; } } return left; //指向的此时枢轴的位置 } #endregion }
对于算法与数据结构，我们还会继续，有理论，有实现，希望它可以不那么枯燥！
感谢咱们的阅读！
本文转自博客园张占岭（仓储大叔）的博客，原文链接：算法和数据结构～各位排序算法的介绍与实现(C#)，如需转载请自行联系原博主。
