时间复杂度O(nlogn)的排序算法有四种，分别是希尔排序，堆排序，快速排序和归并排序。这四个排序都非常重要。
希尔排序希尔排序本质上是插入排序的优化，先对间隔较大的元素进行插入排序，完成宏观调控，然后逐步缩小间隔，最后一轮一定是间隔为 1 的排序，也就是插入排序。间隔在希尔排序中被称为「增量」，增量序列不同，希尔排序的效率也不同。
堆排序堆排序的关键在于建堆，堆分为大顶堆和小顶堆，大顶堆中最大的元素在堆顶，小顶堆同理。
堆实际上是一颗完全二叉树，不过为了方便我们把它用数组的形式储存，储存的顺序为层次遍历的顺序。这种情况下，对于一个非叶子节点i，它的左子索引为2i+1，右子为2i+2。若数组长度为n，则堆中最后一个非叶子节点的索引为n/2+(n%2)-1.
假如现在有一个长度为n的无序数组，将他看做一颗完全二叉树，建大顶堆的过程：找到最后一个非叶子节点，比较它与它的两个子节点，若三者中最大的是某一子节点，则将他与父节点交换。然后向上遍历每一个非叶子节点，对他们都做一遍这样的比较交换操作，直到根节点。这样最后数组中的第一个就是最大的元素了。接下来把它与最后一个元素(n-1)交换，再对0到n-2的部分进行建堆，如此循环。
最小的 k 个数 public class Solution { public int[] GetLeastNumbers(int[] arr, int k) { if(k==arr.Length) return arr; int[] res=new int[k]; for(int i=0;i=0;i--) exchange(arr,i,len); } public void exchange(int[] arr,int i,int len) { if(i*2+2>len) { if(arr[i]>arr[2*i+1]) { int t=arr[i]; arr[i]=arr[2*i+1]; arr[2*i+1]=t; } } else { if(arr[2*i+1]arr[2*i+1]) { int t=arr[i]; arr[i]=arr[2*i+1]; arr[2*i+1]=t; } else if(arr[2*i+2]arr[2*i+2]) { int t=arr[i]; arr[i]=arr[2*i+2]; arr[2*i+2]=t; } } }} 快速排序快速排序算法的基本步骤是：从数组中取出一个数，称之为基数（pivot），一般取第一个数作为基数，设两个指针L,R分别指向数组的最左和最右，R指针在大于L的情况下向左遍历寻找比基数小的数，找到以后将L位置赋值为这个数，L在小于R的情况下向右遍历寻找比基数大的数，找到以后将R位置赋值为这个数，重复上述循环，直到L=R。这时候将基数放在这个位置，对基数左边的部分和右边的部分分别进行上述循环。
快速排序实际上每次循环都把基数放在了最终排序里的位置。
归并排序假设一个数组可以分为0~mid和mid+1~length-1两个有序的子数组，那么可以做如下排序，拷贝一个数组t，设两个指针i，j分别指向两个子数组的开头，比较两个指针指向的元素，将比较小的那个放入原数组，对应指针后移一位，继续比较，直到一个指针走到子数组的结尾。将剩下的一个子数组全部放入原数组。这样就完成了整个数组的排序。
通过上述的思想就可以完成一个递归的算法，因为当子数组细分到只有各元素时自然就是有序的了。
数组中的逆序对在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
假设一个数组可以分为两个有序子数组AB，对它做归并排序，则如果将B数组的元素放入原数组，此时A中的为未放入的元素都比它大，这些元素的数目即为它构成的逆序对的数目。只要计算这些数目的和就可以了。
public class Solution { public int ReversePairs(int[] nums) { int[] temp=new int[nums.Length]; return sort(nums,0,nums.Length-1,temp); } public int sort(int[] nums,int start,int end,int[] temp) { if(end-start