七大排序算法总结

小顶堆

我们先看一个大数据top-K示例：

例子：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

首先，我们知道这是一个典型的top-K问题。

针对大数据问题进行统计首先应该想到的就是Hash_map。所以第一步就是先遍历全部的1千万Query，构建出一个大小为3百万的Hash_map，其中的key值为某条Query，对应的value值为该条Query的查询次数。

建好Hash_map以后，我们接下来的问题就是如何在3百万的Query中找出10个最热门的Query，也就是要用到排序算法。排序算法中效率最高的时间复杂度为O(n*log(n))，

这是最简单粗暴的方法，也是最直接的方法。或者我们进一步优化，该题目是要求寻找top-K问题，那么我们可以直接去前K个Query构建一个数组，然后

对其进行排序。遍历剩余的全部Query，如果某条Query的查询次数大于数组中最小的一个，将数组中最小的Query剔除，加入这条新的Query。

接着调整数组顺序，依次进行遍历，这样的最坏情况下的复杂度为O(n*K)。

但是还可以继续优化寻找top-K的操作，那就是借助小根堆来实现。基于以上的分析，我们想想，有没有一种既能快速查找，又能快速移动元素的数据结构呢？回答是肯定的，那就是堆。

具体过程是，堆顶存放的是整个堆中最小的数，现在遍历N个数，把最先遍历到的k个数存放到最小堆中，并假设它们就是我们要找的最大的k个数，X1>X2...Xmin(堆顶)，而后遍历后续的(n-K)个数，一一与堆顶元素进行比较，如果遍历到的Xi大于堆顶元素Xmin，则把Xi放入堆中，而后更新整个堆，更新的时间复杂度为logK，如果Xi

一个有关小根堆解决top-K问题的小动画，请点击这个链接。

思想与上述算法二一致，只是算法在算法三，我们采用了最小堆这种数据结构代替数组，把查找目标元素的时间复杂度有O(K)降到了O(logK)。那么这样，采用堆数据结构，算法三，最终的时间复杂度就降到了O(n*logK)，和算法二相比，又有了比较大的改进。

六、归并排序------O(nlogn)-------稳定

1. 归并排序：是将两个（或者两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列都是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例

2. C++实现代码

//merge两个有序数列为一个有序数列

void MergeArr(int a[], int first, int mid, int last, int temp[])

{

int i = first, j = mid + 1;

int m = mid, n = last;

int k = 0;

//通过比较，归并数列a和b

while (i <= m && j <= n)

{

         if(a[i]<a[j])

                  temp[k++]=a[i++];

          else

                  temp[k++]=a[j++];

 }

//将数列a或者b剩余的元素直接插入到新数列后边

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];

}

//归并排序

void MSort(int a[], int first, int last, int temp[])

{

          if (first<last)

          {

                     int mid=(first+last)/2;

                    MSort(a, first, mid, temp);

                    MSort(a, mid + 1, last, temp);

                     MergeArr(a, first, mid, last, temp);

          }

void MergeSort(int a[], int len)//为了调用方便封装了一个函数接口

{

       int *temp = new int[len];

      MSort(a, 0, len - 1, temp);

      delete temp;

}

归并排序

归并排序算法

合并两个有序序列

主函数调用

七、快速排序------O(nlogn)-------不稳定

              1. 快速排序：是通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

基本思想

2.C++实现代码

//快速排序

void QSort(int a[], int L, int R)

{

         if (L<R)

        {

                   int low = L, high = R, pivotkey = a[low];// pivotkey：枢轴

                  while (low<high)

                 {//从右向左找小于基准值a[i]的元素

                              while (low<high&& a[high]>=pivotkey)

                                                     high--;

                                if(low<high)

                                       a[low++] = a[high];

                              //从左向右找大于基准值a[i]的元素

                              while (low<high&& a[high]<pivotkey)

                                           low++;

                             if(low<high)

                                          a[high--] = a[low];

                 }

                 //将基准值填入最后的坑中

                  a[low] = pivotkey;

                 //递归调用，分治法的思想

                 QSort(a, L, low - 1);

                QSort(a, low + 1, R);

         }

}

void QuickSort(int a[], int len)  //封装函数接口

{

               QSort(a, 0, len - 1);

}

快速排序

主函数调用

后记：

1.

（1）当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

（2）而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n^2）；

（3）原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

2.

稳定性：排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。

稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另

一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会

改变的。另外，如果排序算法稳定，可以避免多余的比较。

稳定的排序算法：冒泡排序、插入排序、归并排序、选择排序。

不是稳定的排序算法：快速排序、希尔排序、堆排序。

3.

选择排序算法准则：

每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。

选择排序算法的依据：

影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：

（1）待排序的记录数目n的大小；

（2）记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；

（3）关键字的结构及其分布情况；

（4）对排序稳定性的要求。

4.

设待排序元素的个数为n.

（1）当n较大，则应采用时间复杂度为O(n*logn)的排序方法：快速排序、堆排序或归并排序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

堆排序：如果内存空间允许且要求稳定性的；

归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

（2）当n较大，内存空间允许，且要求稳定性：归并排序

（3）当n较小，可采用直接插入或直接选择排序。

直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。

直接选择排序：当元素分布有序，如果不要求稳定性，选择直接选择排序。

（4）一般不使用或不直接使用传统的冒泡排序。