认识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);
    }
}