首页 > 代码库 > 算法手记（5）初级排序算法
算法手记（5）初级排序算法
排序是将一组对象按照一定的规则重新排列的过程。即使目前完全可以使用标准库中的排序函数，学习排序算法仍然有着较大意义：
排序算法的学习可以帮助你全面了解比较算法性能的方法；
类似的技术上能有效解决其他类型的问题；
排序算法通常是我们解决问题的第一步；
更重要的是这些算法都很经典，优雅和高效。
排序在商业数据处理分析和现代科学中占有重要的地位，其中快速排序算法被誉为20世纪科学和工程领域十大算法之一。今天我们要看的就是相对简单但很经典的初级排序算法，包括选择排序，插入排序及Shell排序。
准备
开始之前，我们先约定好算法类模版形式，其中我们将排序代码放入sort（）方法中，less（）方法对元素进行比较返回bool值，exch（）方法用于元素位置交换，形式如下：
public class Example { public static void sort(IComparable[] a) { //排序代码 } private static void exch(IComparable[] a, int i, int j) { IComparable temp = a[i]; a[i] = a[j]; a[j] = temp; } private static bool less(IComparable v, IComparable w) { return v.CompareTo(w)<0; } private static void show(IComparable[] a) { //打印数据 } private static bool isSorted(IComparable[] a) { for(int i=1;i<a.Length;i++) { if(less(a[i], a[i-1])) return false; } return true; } }
这里我使用C#实现，less（）方法使用IComparable接口方法，适用于任何任何实现IComparable接口的数据类型进行排序，系统的Int， String等类型均实现了此接口。
选择排序
概述：
首先找到数组最小的元素，将它和数组第一个元素交换位置。再次，在剩下的元素中找出最小的元素，将它与第二个元素位置交换。如此往复，直到将整个数组排序。因为它不断地选择剩余元素之中的最小者，所以称为选择排序。
分析：
对于长度为N的数组，选择排序需要大约(N^2)/2次比较和N次交换。其增长数量级为平方级别，是一种很容易理解和实现的简单排序算法。它有两个鲜明的特点：
1.运行时间和输入无关。通过实验发现输入一个有序数组和输入一个随机数组所有排序时间竟然一样长。
2.数据移动是最少的。选择排序只有N次交换，这是其他排序算法无法做到的。
代码实现：
public class Selection { public static void sort(IComparable[] a) { //排序代码 for (int i = 0; i < a.Length; i++) { int min = i; for (int j = i + 1; j < a.Length; j++) { if (less(a[j], a[min])) min = j; } exch(a, min, i); } } private static void exch(IComparable[] a, int i, int j) { IComparable temp = a[i]; a[i] = a[j]; a[j] = temp; } private static bool less(IComparable v, IComparable w) { return v.CompareTo(w) < 0; } private static void show(IComparable[] a) { //打印数据 } private static bool isSorted(IComparable[] a) { for (int i = 1; i < a.Length; i++) { if (less(a[i], a[i - 1])) return false; } return true; } }
这里遵循我们约定的规则设计了Selection算法类，运行后，发现可以获得正确的排序结果。
分别执行大小为100，1000，10000，100000的数组后发现，选择排序在大规模排序时使用耗费的时间相当长，中小规模排序可以满足基本使用。
插入排序
概述：
如同日常整理纸牌一样，将每个元素插入到已有序的序列中适当位置，为了给插入的元素腾出空间，我们需要将其余所有元素在插入之前都右移一位。这种算法，我们称为插入排序。
分析：
和选择排序不同，插入排序的所需时间完全取决于输入中元素的初始位置。例如，对一个很大的有序数组进行排序将会比对随机顺序的数组或者逆序数组进行排序要快得多。
对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要~（N^2）/4次比较及~（N^2）/4次交换。最坏情况下需要~（N^2）/2次比较及~（N^2）/2次交换，最好情况下需要N-1次比较和0次交换。
实现：
public class Insertion { public static void sort(IComparable[] a) { //排序代码 int N = a.Length; for (int i = 1; i < N; i++) { for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) exch(a, j, j - 1); } } //优化交换次数 public static void fasterSort(IComparable[] a) { int N = a.Length; for (int i = 1; i < N; i++) { IComparable temp = a[i]; int j = i - 1; while (j > 0 && less(temp, a[j])) { a[j + 1] = a[j]; j--; } a[j + 1] = temp; } } private static void exch(IComparable[] a, int i, int j) { IComparable temp = a[i]; a[i] = a[j]; a[j] = temp; } private static bool less(IComparable v, IComparable w) { return v.CompareTo(w) < 0; } private static void show(IComparable[] a) { //打印数据 for (int i = 1; i < a.Length; i++) { Console.WriteLine(a[i]); } } private static bool isSorted(IComparable[] a) { for (int i = 1; i < a.Length; i++) { if (less(a[i], a[i - 1])) return false; } return true; }}
通过多次实验输入，发现插入排序在处理大规模数据时也相当慢。但是和选择排序不同，当输入为较大大规模有序数据（如大小100000时），速度要快的多，而选择排序则依旧需要漫长的排序时间，这点是优于选择排序的。
算法手记（5）初级排序算法