认识O(N*logN)的排序（总结）
在总结之前看看下面这张表：
从表中可以看到归并排序、快速排序、堆排序的平均时间复杂度是 O(nlogn) 。我要总结的便是这三种排序算法，它们都适合于数据量比较大的排序运算中。
一. 归并排序：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数开始，谁小就先取谁。然后再进行比较，如果有数列比较完了，那直接将另一个数列的数据依次取出即可。
可以看出合并有序数列的效率是比较高的，可以达到O(n)。
解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归地分解数列，再合并数列就完成了归并排序。
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];//first+i不能丢掉first
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
//此处引用的是https://blog.csdn.net/morewindows/article/details/6678165#的代码
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
二. 快速排序：
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
对快速排序可以作进一步的说明：挖坑填数 + 分治法。
对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
//挖坑填数
int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
{
int i = l, j = r;
int x = s[l]; //s[l]即s[i]就是第一个坑
while (i < j)
{
// 从右向左找小于x的数来填s[i]
while(i < j && s[j] >= x)
j--;
if(i < j)
{
s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
i++;
}
// 从左向右找大于或等于x的数来填s[j]
while(i < j && s[i] < x)
i++;
if(i < j)
{
s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
j--;
}
}
//退出时，i等于j。将x填到这个坑中。
s[i] = x;
return i;
}
//分治
void quick_sort1(int s[], int l, int r)
{
if (l < r)
{
int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
quick_sort1(s, l, i - 1); // 递归调用
quick_sort1(s, i + 1, r);
}
}
//代码引用于https://blog.csdn.net/morewindows/article/details/6684558 三. 堆排序：
堆是一棵顺序存储的完全二叉树
堆排序的时间复杂度： O(nlogn)，属于不稳定排序。
| 大根堆 | 小根堆 |
|---|---|
每个节点的值大于等于孩子节点得堆 | 每个节点得值小于等于孩子节点得值 |
堆排序就是利用堆得性质堆数组进行排序，待排序元素存放在一个数组Arr[0 ……n] 中，将Arr用一颗完全二叉树来表示，数组第一个元素就是完全二叉树的根，后面依次按层从左至右为，左孩子，右孩子，任意节点Arr[ i ] 的左孩子是Arr[ 2i+1 ]，右孩子是 Arr[ 2i+2 ]，对这个二叉树进行调整。
通过大佬的图像来介绍一下：
1.构建初始堆：
2.完整的堆排序：
//通过传指针交换两个元素的位置
void Swap(int *num1, int *num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
//给定父节点的索引，得到左子节点的索引,跟的索引为0
#define LeftChild(i) (2*(i)+1)
//元素向下调整方法
void PercDown(int A[], int i, int N)
{
//子节点的索引号
int child;
//存储当前父节点元素的临时变量
//(注：每一个节点都可以看作是其子树的根节点)
int tmp;
for (tmp = A[i]; LeftChild(i)<N; i = child)
{
child = LeftChild(i); //左子节点索引
//挑选出左、右子节点中较大者
if (child != N - 1 && A[child + 1] > A[child])
{
child++;
}
//比较当前父节点与较大子节点
if (A[i]<A[child])
{
//交换当前父节点处的元素值与较大子节点的元素值
//此处也可以调用：Swap(A[i], A[child])
tmp = A[i];
A[i] = A[child];
A[child] = tmp;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int A[], int N)
{
int i;
//步骤一：根据A数组元素，创建大根堆
//从第 n/2 个记录开始进行建堆
for (i = N / 2; i >= 0; i--)
{
PercDown(A, i, N);
}
//步骤二：调整大根堆
for (i = N - 1; i > 0; i--)
{
//首尾交换
Swap(&A[0], &A[i]);
//将最后一个叶子节点与根节点进行交换，
//再根据堆性质进行调整
PercDown(A, 0, i);
}
}
