首页 / 软件开发 / 数据结构与算法 / 浅谈算法和数据结构 二 基本排序算法

浅谈算法和数据结构 二 基本排序算法2015-02-27本篇开始学习排序算法。排序与我们日常生活中息息相关，比如，我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按照出发时间或者时长排序、买东西会按照销量或者好评度排序、查找文件会按照修改时间排序等等。在计算机程序设计中，排序和查找也是最基本的算法，很多其他的算法都是以排序算法为基础，在一般的数据处理或分析中，通常第一步就是进行排序，比如说二分查找，首先要对数据进行排序。在Donald Knuth 的计算机程序设计的艺术这四卷书中，有一卷是专门介绍排序和查找的。

排序的算法有很多，在维基百科上有这么一个分类，另外大家有兴趣也可以直接上维基百科上看相关算法，本文也参考了上面的内容。

首先来看比较简单的选择排序（Selection sort），插入排序（Insertion sort），然后在分析插入排序的特征和缺点的基础上，介绍在插入排序基础上改进的希尔排序（Shell sort）。

一 选择排序

原理：

选择排序很简单，他的步骤如下：

从左至右遍历，找到最小（大）的元素，然后与第一个元素交换。

从剩余未排序元素中继续寻找最小（大）元素，然后与第二个元素进行交换。

以此类推，直到所有元素均排序完毕。

之所以称之为选择排序，是因为每一次遍历未排序的序列我们总是从中选择出最小的元素。下面是选择排序的动画演示：

实现：

算法实现起来也很简单，我们新建一个Sort泛型类，让该类型必须实现IComparable接口，然后我们定义SelectionSort方法，方法传入T数组，代码如下：

/// <summary>/// 排序算法泛型类，要求类型实现IComparable接口/// </summary>/// <typeparam name="T"></typeparam>public class Sort<T> where T : IComparable<T>{/// <summary>/// 选择排序/// </summary>/// <param name="array"></param>public static void SelectionSort（T[] array）{int n = array.Length;for （int i = 0; i < n; i++）{int min = i;//从第i+1个元素开始，找最小值for （int j = i + 1; j < n; j++）{if （array[min].CompareTo（array[j]） > 0）min = j;}//找到之后和第i个元素交换Swap（array, i, min）;}}/// <summary>/// 元素交换/// </summary>/// <param name="array"></param>/// <param name="i"></param>/// <param name="min"></param>private static void Swap（T[] array, int i, int min）{T temp = array[i];array[i] = array[min];array[min] = temp;}}