第一种:堆排序

最大堆进行升序排序,主要步骤是

1.初始化堆:将数列a[1...n]构造成最大堆。

2.交换数据:将a[1]和a[n]交换，使a[n]是a[1...n]中的最大值；然后将a[1...n-1]重新调整为最大堆。接着，将a[1]和a[n-1]交换，使a[n-1]是a[1...n-1]中的最大值；然后将a[1...n-2]重新调整为最大值。依次类推，直到整个数列都是有序的。

 1         static void Swap<T>(ref T t1, ref T t2) {
 2             T temp = t1;
 3             t1 = t2;
 4             t2 = temp;
 5         }
 6 
 7         static void Maxheap_Down(int[] arr, int start, int end) {
 8 
 9             int current = start;
10             int left = 2 * current + 1;
11             int temp = arr[current];
12 
13             for (; left <= end; current = left, left = 2 * left + 1) {
14                 if (left < end && arr[left] < arr[left + 1]) {
15                     left++;
16                 }
17                 if (temp >= arr[left])
18                     break;
19                 else {
20                     arr[current] = arr[left];
21                     arr[left] = temp;
22                 }
23             }
24         }
25 
26         static int Heap_Find_NumberK(int[] arr, int k) {
27             int n = arr.Length;
28             int i;
29 
30             for (i = n / 2 - 1; i >= 0; i--) {
31                 Maxheap_Down(arr, i, n - 1);
32             }
33 
34             for (i = n - 1; i >= k-1; i--) {
35                 Swap(ref arr[0], ref arr[i]);
36                 Maxheap_Down(arr, 0, i - 1);
37             }
38             return arr[k - 1];
39         }

堆排序时间复杂度
堆排序的时间复杂度是O(N*lgN)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？
堆排序是采用的二叉堆进行排序的，二叉堆就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。最多是多少呢？由于二叉堆是完全二叉树，因此，它的深度最多也不会超过lg(2N)。因此，遍历一趟的时间复杂度是O(N)，而遍历次数介于lg(N+1)和lg(2N)之间；因此得出它的时间复杂度是O(N*lgN)。

第二种:快速排序

利用快排划分出来的主元位置再递归寻找,这种方法叫作随机选择算法。它对任何输入都可以达到 $O (n)$

 1         static int RandPartition(int[] arr, int left, int right) {
 2             Random rd = new Random();
 3             int p = rd.Next(left, right + 1);
 4             Swap(ref arr[p], ref arr[left]);
 5             int temp = arr[left];
 6             while (left < right) {
 7                 while (left < right && arr[right] > temp) { right--; count++; }
 8                 arr[left] = arr[right];
 9                 while (left < right && arr[left] <= temp) { left++; count++; }
10                 arr[right] = arr[left];
11             }
12             arr[left] = temp;
13             return left;
14         }
15 
16         static int RandSelect(int[] arr, int left, int right, int k) {
17             if (left == right) {
18                 return arr[left];
19             }
20             int index = RandPartition(arr, left, right);
21             int M = index + 1;
22             if (M == k) {
23                 return arr[index];
24             }
25             int result = -1;
26             if (M < k) {
27                 result = RandSelect(arr, index + 1, right, k);
28             }
29             else if (M > k) {
30                 result = RandSelect(arr, left, index - 1, k);
31             }
32             return result;
33         }