四种简单的排序算法.docVIP

1.插入排序 算法思想 插入排序使用了两层嵌套循环，逐个处理待排序的记录。每个记录与前面已经排好序的记录序列进行比较，并将其插入到合适的位置。假设数组长度为n，外层循环控制变量i由1至n-1依次递进，用于选择当前处理哪条记录；里层循环控制变量j，初始值为i，并由i至1递减，与上一记录进行对比，决定将该元素插入到哪一个位置。这里的关键思想是，当处理第i条记录时，前面i-1条记录已经是有序的了。需要注意的是，因为是将当前记录与相邻的上一记录相比较，所以循环控制变量的起始值为1（数组下标），如果为0的话，上一记录为-1，则数组越界。 现在我们考察一下第i条记录的处理情况：假设外层循环递进到第i条记录，设其关键码的值为X，那么此时有可能有两种情况： 如果上一记录比X大，那么就交换它们，直到上一记录的关键码比X小或者相等为止。 如果上一记录比X小或者相等，那么之前的所有记录一定是有序的，且都比X小，此时退出里层循环。外层循环向前递进，处理下一条记录。 算法实现(C#) public class SortAlgorithm {??? // 插入排序??? public static void InsertSortT, C(T[] array, C comparer)??????? where C:IComparerT??? {?????????? ??????? for (int i = 1; i = array.Length - 1; i++) {??????????? //Console.Write({0}: , i);??????????? int j = i;??????????? while (j=1 comparer.Compare(array[j], array[j - 1]) 0) {??????????????? swap(ref array[j], ref array[j-1]);??????????????? j--;??????????? }??????????? //Console.WriteLine();??????????? //AlgorithmHelper.PrintArray(array);??????? }??? }??? // 交换数组array中第i个元素和第j个元素??? private static void swapT(ref T x,ref T y) {??????? // Console.Write({0}--{1} , x, y);??????? T temp = x;??????? x = y;??????? y = temp;??? }} 上面Console.WriteLine()方法和AlgorithmHelper.PrintArray()方法仅仅是出于测试方便，PrintArray()方法依次打印了数组的内容。swapT()方法则用于交换数组中的两条记录，也对交换数进行了打印（这里我注释掉了，但在测试时可以取消对它们的注释）。外层for循环控制变量i表示当前处理第i条记录。 public class AlgorithmHelper {??? // 打印数组内容??? public static void PrintArrayT(T[] array) {??????? Console.Write(?? Array:);??????? foreach (T item in array) {??????????? Console.Write( {0}, item);??? ??? }??????? Console.WriteLine();??? }}// 获得Comparer，进行比较public class ComparerFactory {??? public static IComparerint GetIntComparer() {??????? return new IntComparer();??? }??? public class IntComparer : IComparerint {??????? public int Compare(int x, int y) {??????????? return x.CompareTo(y);??????? }??? }} 上面这段代码我们创建了一个ComparerFactory类，它用于获得一个IntComparer对象，这个对象实现了IComparerT接口，规定了两个int类型的关键码之间比较大小的规则。如果你有自定义的类型，比如叫MyType，只需要在ComparerFactory中再添加一个类，比如叫MyTypeCo