认识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++];elsetemp[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);}
}