黑马程序员--C#有关的排序算法

1、冒泡排序

（1）概念

　　是一种计算机科学领域比较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成；

　　冒泡排序最好的时间复杂度为冒泡排序最好的时间复杂度为；冒泡排序的最坏时间复杂度为 $O(n^{2})$ ；综上，冒泡排序总的平均时间复杂度为；

（2）程序实现（有涉及到数据交换）

 1         static void Main(string[] args)
 2         {
 3             int[] nums = { 0, 5, 1, 3, 9, 6, 4, 8, 2, 7 };
 4             for (int i = 0; i < nums.Length-1; i++)
 5             {
 6                 for (int j = 0; j < nums.Length - i - 1; j++)
 7                 {
 8                     if (nums[j] > nums[j+1])
 9                     {
10                         int temp = nums[j];
11                         nums[j] = nums[j+1];
12                         nums[j+1] = temp;
13                     }
14                 }
15             }
16             string str = string.Empty;
17             foreach(int i in nums)
18             {
19                 str += Convert.ToString(i) + ",";
20             }
21             Console.WriteLine("排序后的数据为：
{0}
",str.Substring(0,str.Length-1));
22             Console.ReadLine();
23         }

2、选择排序法

（1）概念

　　选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录；包含简单选择排序、树型选择排序和堆排序等；

（2）程序实现

 1        #region 选择排序
 2        static void Main(string[] args)
 3         { 
 4             int[] list = { 1, 6, 8, 9, 5, 7, 4, 0, 2 };
 5             int min;
 6             for(int i=0;i<list.Length-1;i++)
 7             {
 8                 min=i;
 9                 for(int j=i+1;j<list.Length;j++)
10                 {
11                     if(list[j]<list[min])
12                     min=j;
13                 }
14                 int t=list[min];
15                 list[min]=list[i];
16                 list[i]=t;
17             }
18             string str = string.Empty;
19             foreach (int temp in list)
20             {
21                 str += Convert.ToString(temp) + ",";
22             }
23             Console.WriteLine(str.Substring(0,str.Length-1));
24             Console.ReadLine();
25 
26         }
27         #endregion

3、插入排序法

（1）概念

　　输入一个元素，检查数组列表中的每个元素，将其插入到一个已经排好序的数列中的适当位置，使数列依然有序，当最后一个元素放入合适位置时，该数组排序完毕。

　　思想：把欲插入的数与数组中各数逐个比较，当找到第一个比插入数大的元素i时，该元素之前即为插入位置。然后从数组最后一个元素开始到该元素为止，逐个后移一个单元。最后把插入数赋予元素a[i]即可。如果被插入数比所有的元素值都小则插入最前位置。

（2）程序实现

       #region 插入排序
        static void Main(string[] args)
        {
            int[] list = { 1, 6, 8, 9, 5, 7, 4, 0, 2 };
            for (int i = 0; i < list.Length; i++)
            {
                int t = list[i];
                int j = i;
                while (j > 0 && list[j - 1] < t)
                {
                    list[j] = list[j - 1];
                    --j;
                }
                list[j] = t;
            }
            string str = string.Empty;
            foreach (int temp in list)
            {
                str += Convert.ToString(temp) + ",";
            }
            Console.WriteLine(str.Substring(0, str.Length - 1));
            Console.ReadLine();
        }
        #endregion

4、希尔排序法

（1）概念

　　希尔排序法(缩小增量法) 属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

（2）程序实现

 1         #region 希尔排序法
 2         static void Main(string[] args)
 3         {
 4             int[] list = { 1, 6, 8, 9, 5, 7, 4, 0, 2 };
 5             int inc;
 6             for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
 7             for (; inc > 0; inc /= 3)
 8             {
 9                 for (int i = inc + 1; i <= list.Length; i += inc)
10                 {
11                     int t = list[i - 1];
12                     int j = i;
13                     while (j > inc && list[j - inc - 1] > t)
14                     {
15                         list[j - 1] = list[j - inc - 1];
16                         j -= inc;
17                     }
18                     list[j - 1] = t;
19                 }
20             }
21             string str = string.Empty;
22             foreach (int temp in list)
23             {
24                 str += Convert.ToString(temp) + ",";
25             }
26             Console.WriteLine(str.Substring(0, str.Length - 1));
27             Console.ReadLine();
28         }
29         #endregion

实然做到有关冒泡排序的东西，就想着把涉及到的排序算法都整理到一下地方，从网上先搜的这几种排序方法，后面三种还需要进一步理解；