时间复杂度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<k;i++)
{
heap(arr,arr.Length-i-1);
int t=arr[0];res[i]=t;
arr[0]=arr[arr.Length-1-i];
arr[arr.Length-1-i]=t;
}
return res;
}
public void heap(int[] arr,int len)
{
if(len==0)
return;
for(int i=len/2-1+(len%2);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+2]&&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+2]<=arr[2*i+1]&&arr[i]>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<=0)
return 0;
int mid=(start+end)/2;
int res=sort(nums,start,mid,temp)+sort(nums,mid+1,end,temp);
for(int a=start;a<=end;a++)
temp[a]=nums[a];
int i=start,x=start,y=mid+1;
while(x<=mid&&y<=end)
{
if(temp[x]<=temp[y])
{
nums[i]=temp[x];
x++;
}
else
{
nums[i]=temp[y];
res+=mid-x+1;
y++;
}
i++;
}
if(x<=mid)
for(;x<=mid;x++)
nums[i++]=temp[x];
else
for(;y<=end;y++)
nums[i++]=temp[y];
return res;
}
}稳定性
希尔排序、堆排序、快速排序是不稳定的，归并排序是稳定的。