数据结构——排序（一）

（一）概述:

　　基本含义：排序就是将一组对象按照规定的次序重新排列的过程，排序往往是为了检索服务的。

特性：排序具有稳定性，但是该特性是排序方法本身的特性，与数据无关。换言之，一种排序方法如果是稳定的，那么对所有的数据序列都是稳定的，反过来如果数据上出现不稳定的现象，则说明该方法不是稳定的。

分类：排序可以分为两大类：内部排序和外部排序。内部排序的数据全部存放在计算机内存中，在计算机的内存中进行排序。而外部排序数据量很大，内存不能存储全部记录，需要对外存进行访问的排序过程，因此暂时不予考虑，文中所讲的都是内部排序，通过具体例子来理解相应的排序实现。

（二）插入排序：

　　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］

直接排序就是将序列第一个数据看做初始值，然后将序列中每个数据和上次的序列组进行对比，插入到相对应的位置即可。其时间复杂度和空间复杂度分别是：Ｏ（n²），O（1）

代码实现：

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("排序后：");

            //调用直接排序方法
            InsertSortionFunction(arr);
        }
        /// <summary>
        /// 直接排序方法
        /// </summary>
        /// <param name="array">参数是整型数组</param>
        private static void InsertSortionFunction(int[] array)
        {
            try
            {
                int temp = 0;   //临时变量，存储待排的数值
                //将无序的所有数值依次插入到有序数组中，注：下标从1开始，因为操作的是同一个数组
                for (int i = 1; i < array.Length; i++) 
                {
                    temp = array[i];    //记录待插入前面有序数组的数值
                    int index = i - 1;  //记录前方有序数组的末尾位置

                    //循环遍历前面的有序数组，并且从大到小依次与待排数值进行比较
                    while (index >= 0 && array[index] > temp)
                    {
                        //如果index>=0并且此时的值大于待排数值，将此处的值向后移动一位
                        array[index + 1] = array[index];    
                        index--;    //index--向前遍历有序数组
                    }
                    array[index + 1] = temp;    //由于前面的index--，所以temp插入的位置是index+1
                }
                //用 一个循环访问数组里的元素并打印		           
                for (int j = 0; j < array.Length; j++)
                {
                    Console.Write(array[j] + " , ");
                }
            }
            catch (Exception ex)
            { }
        }
    }
}

ＰＳ：代码是随机生成的数字，而示例是为了方便随便举得用来说明的。

（三）交换排序

　　基本思想：比较两个记录键值的大小，如果这两个记录键值的大小出现逆序，则交换这两个记录，这样可以将较小的记录向前推移，较大的记录向后移动。

　　１、冒泡排序：

实现思路：将第一个记录的键值和第二个记录的键值进行比较，若为逆序，则交换这个量记录交换。然后继续比较第二个和第三个记录的键值。以此类推，知道完成第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] + " , ");
	            }
	        }
	    }
	}

　　

预告：这次实现的主要是直接插入排序和交换排序中的冒泡排序，下次继续的交换排序中的快速排序和选择排序中的直接选择排序