数据结构——排序（一）
（一）概述:
基本含义：排序就是将一组对象按照规定的次序重新排列的过程，排序往往是为了检索服务的。
特性：排序具有稳定性，但是该特性是排序方法本身的特性，与数据无关。换言之，一种排序方法如果是稳定的，那么对所有的数据序列都是稳定的，反过来如果数据上出现不稳定的现象，则说明该方法不是稳定的。
分类：排序可以分为两大类：内部排序和外部排序。内部排序的数据全部存放在计算机内存中，在计算机的内存中进行排序。而外部排序数据量很大，内存不能存储全部记录，需要对外存进行访问的排序过程，因此暂时不予考虑，文中所讲的都是内部排序，通过具体例子来理解相应的排序实现。
（二）插入排序： 1、直接插入排序；基本思想：直接插入排序时一种简单的排序方法，基本思想是一次奖每个记录插入到一个已拍好序列的的有序表中，从而得到一个新的，记录数增加１的有序表。
事例说明：对28 36 56 15 34 22 95 84 按照直接插入排序进行排，其实现过程如下：
第一次排序：用36＞28故将36插入到28右边，得到结果
［28 36］56 15 34 22 95 84
同理
第二次排序：［28 36 56］15 34 22 95 84
第三次排序：［15 28 36 56］34 22 95 84
第四次排序：［15 28 34 36 56］22 95 84
第五次排序：［15 22 28 34 36 56］95 84
第六次排序：［15 22 28 34 36 56 84］95
第七次排序：［15 22 28 34 36 56 84 95］
直接排序就是将序列第一个数据看做初始值，然后将序列中每个数据和上次的序列组进行对比，插入到相对应的位置即可。其时间复杂度和空间复杂度分别是：Ｏ（n2），O（1）
代码实现：
n-1个记录和第n个记录得键值比较交换为止。自己的理解就是：每进行一次冒泡，那么都会有一个最大的值到序列最后。
事例描述：对28 36 56 15 34 22 9584按照冒泡排序进行排，其实现过程如下：
第一次冒泡：28>36两者不交换，36<56,两者不交换，56>15，两者交换，（这时候56和15已经交换完毕），56>34,两者交换（28 36 15 3456 22 95 84） 56>22,两者再交换，56<95不用交换，95>84两者交换，所以经过第一次冒泡，得到结果：28 36 15 34 22 56 84 95
同理第二次冒泡得到排序结果：28 15 34 22 36 56 84 95
第三次冒泡结果：15 28 22 34 36 56 84 95
第四次排序结果：15 22 28 34 36 56 8495
观察得出：每次冒泡，在所进行的序列中，都会往最后冒出一个最大的值！，这是冒泡排序的典型特点。
代码实现：
namespace ConsoleApplication1{ class Program { static void Main(string[] args) { int[] arr = new int[10];//定义数组 Random rdm = new Random();//生成随机数 Console.WriteLine("排序前："); for (int i = 0; i < 10; i++) { arr[i] = rdm.Next(0, 100); Console.Write(arr[i] + " , "); } Console.WriteLine(""); Console.WriteLine("排序后："); Sort(arr);//调用冒泡排序方法 } /// <summary> /// 冒泡排序方法 /// </summary> /// <param name="arr">一个整型的数组</param> public static void Sort(int[] arr) { for (int j = 1; j < arr.Length; j++) {//外循环每次把参与排序的最大数排在最后 for (int i = 0; i < arr.Length - j; i++) { //内层循环负责对比相邻的两个数，并把最大的排在后面 if (arr[i] > arr[i + 1]) { //如果前 一个数大于后一个数，则交换两个数 int temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } } //用 一个循环访问数组里的元素并打印 for (int j = 0; j < arr.Length; j++) { Console.Write(arr[j] + " , "); } } }}
预告：这次实现的主要是直接插入排序和交换排序中的冒泡排序，下次继续的交换排序中的快速排序和选择排序中的直接选择排序
