算法Demo源码(C#)：http://pan.baidu.com/s/1c0m8N4W

        虽然以前上大学的时候就知道算法很重要，但是从没花时间去理一理，所以今天闲来无事，特意花了将近一个下午的时间理了下排序算法，以下就是我对几个算法的简单总结啦！没有写的很详细，权当自己对知识点的一个总结。另外，其中一些代码是从网络上Copy过来的。

1.插入排序

举例说明：

这里我把它理解为给扑克牌排序，好比一叠扑克牌，从牌顶一张张的抽出来然后按顺序排好。

算法思想

1、插入排序算法使用了两层嵌套循环，外层循环用于选择当前处理哪条记录，里层循环控制将记录插入到哪一个位置。需要注意的是：当处理第n条记录时，前面的n-1条记录已经是有序的了（这里我把它理解为给扑克牌排序）。
2、从第一条记录开始，第n条与第n-1条记录比较，最大比较次数为n-1次(需要与队列中已排好序的记录进行逐一比较)。
3、当队列基本有序的时候，插入排序的效率比较高。

算法实现(C#)

public class SortAlgorithm {
   // 插入排序
   public static void InsertSort<T, C>(T[] array, C comparer)
       where C:IComparer<T>
   {          
       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 swap<T>(ref T x,ref T y) {
       // Console.Write("{0}<-->{1} ", x, y);
       T temp = x;
       x = y;
       y = temp;
   }
}

public class AlgorithmHelper {
   // 打印数组内容
   public static void PrintArray<T>(T[] array) {
       Console.Write("   Array:");
       foreach (T item in array) {
           Console.Write(" {0}", item);
       }
       Console.WriteLine();
   }
}

// 获得Comparer，进行比较
public class ComparerFactory {
   public static IComparer<int> GetIntComparer() {
       return new IntComparer();
   }

   public class IntComparer : IComparer<int> {
       public int Compare(int x, int y) {
           return x.CompareTo(y);
       }
   }
}

输出演示(C#)

接下来我们看一下客户端代码和输出：

static void Main(string[] args) {
   int[] array = {42,20,17,13,28,14,23,15};
   //int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
   AlgorithmHelper.PrintArray(array);

   SortAlgorithm.InsertSort
       (array, ComparerFactory.GetIntComparer());
}

算法实现(C++)

// 对int类型进行排序
class IntComparer{
   public:
       static bool Smaller(int x, int y){
           return x<y;
       }
       static bool Equal(int x, int y){
           return x==y;
       }
       static bool Larger(int x, int y){
           return x>y;
       }
};

// 插入排序
template <class T, class C>
void InsertSort(T a[], int length){
   for(int i=1;i<=length-1;i++){
       int j = i;
       while(j>=1 && C::Smaller(a[j], a[j-1])){
           swap(a[j], a[j-1]);
           j--;
       }
   }
}

2.冒泡排序

举例说明：

这里我把它理解为在进行多趟的传递交接棒游戏(一趟完毕才能进行下一趟)，例如我是队伍的最后一名选手，那么我要手持交接棒一个个寻找比我要小的选手，如果找到了就把交接棒给他，让他寻找比他更小的选手，而我则站在他的位置上，直到交接棒传递到队伍的第一个位置，这一趟才算完毕。根据此规则，第二趟传递到第二的位置，第三趟传递到第三的位置，如此循环反复。。。

算法思想

1、冒泡排序算法也含有两层循环，外层循环控制比较的趟数(可以理解为有n条记录，就要比较n-1趟)，里层循环控制记录位置的交换。
2、从队列最后一条记录开始，第1趟比较完毕后，队列中最小的记录一定是在首位，第2趟队列中第二小的记录一定在次位，以此类推，直到完成n-1趟比较，此时由于前面的n-1条记录已排好序，那么第n条记录，也就是最大的那条记录已经排在最后一个位置，所以队列排序完毕。

算法实现(C#)

// 泡沫排序
public static void BubbleSort<T, C>(T[] array, C comparer)
   where C : IComparer<T>
{
   int length = array.Length;

   for (int i = 0; i <= length - 2; i++) {
       //Console.Write("{0}: ", i + 1);
       for (int j = length - 1; j >= 1; j--) {
           if (comparer.Compare(array[j], array[j - 1]) < 0) {
               swap(ref array[j], ref array[j - 1]);
           }
       }
       //Console.WriteLine();
       //AlgorithmHelper.PrintArray(array);
   }
}

输出演示(C#)

static voidMain(string[] args) {
   int[] array = {42,20,17,13,28,14,23,15};
   AlgorithmHelper.PrintArray(array);

   SortAlgorithm.BubbleSort
       (array, ComparerFactory.GetIntComparer());
}

算法实现(C++)

// 冒泡排序
template <class T, class C>
void BubbleSort(T a[], int length){
   for(int i=0;i<=length-2;i++){
       for(int j=length-1; j>=1; j--){
           if(C::Smaller(a[j], a[j-1]))
               swap(a[j], a[j-1]);
       }
   }
}

3.选择排序

举例说明：

这里我也把它理解学校里老师给学生按身高排位，低的在前，高的在后。。。

算法思想

选择排序算法是对冒泡排序算法的一个改进，不同的是，它并不是从末尾一条记录开始，而是搜索整个队列中最小的一个数字，然后放置在队列的首位，而剩下的数字则形成一个新的队列，然后重复以上操作。。。

算法实现(C#)

public static void SelectionSort<T, C>(T[] array, C comparer)
   where C : IComparer<T>
{
   int length = array.Length;
   for (int i = 0; i <= length - 2; i++) {
       Console.Write("{0}: ", i+1);
       int lowestIndex = i;        // 最小记录的数组索引
       for (int j = length - 1; j > i; j--) {
           if (comparer.Compare(array[j], array[lowestIndex]) < 0)
               lowestIndex = j;
       }
       swap(ref array[i], ref array[lowestIndex]);
       AlgorithmHelper.PrintArray(array);
   }
}

输出演示(C#)

static voidMain(string[] args) {
   int[] array = {42,20,17,13,28,14,23,15};
   AlgorithmHelper.PrintArray(array);

   SortAlgorithm.SelectionSort
       (array, ComparerFactory.GetIntComparer());
}

算法实现(C++)

// 选择排序
template <class T, class C>
void SelectionSort(T a[], int length) {
   for(int i = 0; i <= length-2; i++){
       int lowestIndex = i;
       for(int j = length-1; j>i; j--){
           if(C::Smaller(a[j], a[lowestIndex]))
               lowestIndex = j;
       }
       swap(a[i], a[lowestIndex]);
   }
}

4.希尔排序

举例说明：

由于它是利用了插入排序算法的一个特点，故我也把它理解给扑克牌排序，不过不同的是，它是将扑克牌分组按一定规则进行分组，然后对每组应用插入排序算法排序。直到最后所有分组合并成一组再应用插入排序算法后，排序完毕。

算法思想：

        希尔排序算法利用插入排序算法的一个特点来优化算法，即：当队列基本有序的时候，插入排序的效率比较高。而希尔排序的总体想法就是先让数组基本有序，最后再应用插入排序。具体过程如下：假设有数组int a[] = {42,20,17,13,28,14,23,15}，不失一般性，我们设其长度为length。

        第一趟时，步长step = length/2 = 4，将数组分为4组，每组2个记录，则下标分别为(0,4)(1,5)(2,6)(3,7)；转换为数值，则为{42,28}, {20,14}, {17,23}, {13,15}。然后对每个分组进行插入排序，之后分组数值为{28,42}, {14,20}, {17,23}, {13,15}，而实际的原数组的值就变成了{28,14,17,13,42,20,23,15}。这里要注意的是分组中记录在原数组中的位置，以第2个分组{14,20}来说，它的下标是(1,5)，所以这两个记录在原数组的下标分别为a[1]=14;a[5]=20。

        第二趟时，步长 step = step/2 = 2，将数组分为2组，每组4个记录，则下标分别为(0,2,4,6)(1,3,5,7)；转换为数值，则为{28,17,42,23}, {14,13,20,15}，然后对每个分组进行插入排序，得到{17,23,28,42}{13,14,15,20}。此时数组就成了{17,13,23,14,28,15,42,20}，已经基本有序。

        第三趟时，步长 step=step/2 = 1，此时相当进行一次完整的插入排序，得到最终结果{13,14,15,17,20,23,28,42}。

算法实现(C#)

// 希尔排序
public static void ShellSort<T, C>(T[] array, C comparer)
   where C : IComparer<T>
{
   for (int i = array.Length / 2; i >= 1; i = i / 2) {
       Console.Write("{0}: ", i);
       for (int j = 0; j < i; j++) {
           InsertSort(array, j, i, comparer);
       }
       Console.WriteLine();
       AlgorithmHelper.PrintArray(array);
   }
}

// 用于希尔排序的插入排序
private static void InsertSort<T, C>
   (T[] array, int startIndex, int step, C comparer)
   where C : IComparer<T>
{
   for (int i = startIndex + step; i <= array.Length - 1; i += step) {
       int j = i;
       while(j>= step && comparer.Compare(array[j], array[j - step]) <0 ){
           swap(ref array[j], ref array[j - step]);
           j -= step;
       }
   }
}

注意这里插入排序InsertSort()方法的参数，startIndex是分组的起始索引，step是步长，可以看出，前面的插入排序只是此处step=1,startindex=0的一个特例。

输出演示(C#)

static voidMain(string[] args) {
   int[] array = {42,20,17,13,28,14,23,15};
   AlgorithmHelper.PrintArray(array);

   SortAlgorithm.ShellSort
       (array, ComparerFactory.GetIntComparer());
}

算法实现(C++)

// 希尔排序
template<class T, class C>
void ShellSort(T a[], int length){
   for(int i = length/2; i >= 1; i = i/2 ){
       for(int j = 0; j<i; j++){
           InsertSort<T, C>(&a[j], length-1, i);
       }
   }
}

// 用于希尔排序的插入排序
template<class T, class C>
void InsertSort(T a[], int length, int step){
   for(int i = step; i<length; i+= step){
       int j = i;
       while(j>=step && C::Smaller(a[j], a[j-step])){
           swap(a[j], a[j-step]);
           j-=step;
       }
   }
}

来源：时间去哪儿了博客（微信/QQ号：903918446），转载请保留出处和链接！

本文链接：http://timegowhere.com/post/SortAlg.html