八大排序算法（一）

排序是算法中非常重要的一部分，无论考研还是工作面试中都会考到排序。今天起我们就来详解八大排序算法。

本文目录：
1.排序的基本概念
2.交换类排序法
       ✦冒泡排序   
       ✦快速排序
               ◇递归排序
               ◇迭代排序
               ◇C语音qsort（）函数
3.插入类排序法
       ✦直接插入排序 (Straight Insertion Sort)
       ✦希尔排序（Shell Sort）
4.选择类排序法
       ✦简单选择排序（Simple Selection Sort）
       ✦堆排序（Heap Sort）
5.归并排序法
       ✦迭代法
       ✦递归法
6.基数排序法

今天详细为大家详解“排序的基本概念”及“交换类排序法”两个章节。

排序的基本概念

排序是将一批(组)任意次序的记录重新排列成按关键字有序的记录序列的过程。

排序算法有许多，但就全面性能而言，还没有一种公认为最好的。每种算法都有其优点和缺点，分别适合不同的数据量和硬件配置。

        评价排序算法的标准有：执行时间和所需的辅助空间，其次是算法的稳定性。

若排序算法所需的辅助空间不依赖问题的规模n，即空间复杂度是O(1) ，则称排序方法是就地排序，否则是非就地排序。

排序的分类

    待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。

     1.待排序的记录数不太多：所有的记录都能存放在内存中进行排序，称为内部排序；

     2.待排序的记录数太多：所有的记录不可能存放在内存中， 排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。

内部排序的基本操作

    对内部排序而言，其基本操作有两种：

◆  比较两个关键字的大小；

◆ 存储位置的移动：从一个位置移到另一个位置。

   

第一种操作是必不可少的；而第二种操作却不是必须的，取决于记录的存储方式，具体情况是：

① 记录存储在一组连续地址的存储空间：记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现，记录的移动是必不可少的；

②  记录采用链式存储方式：记录之间的逻辑顺序关系是通过结点中的指针来体现，排序过程仅需修改结点的指针，而不需要移动记录；

③  记录存储在一组连续地址的存储空间：构造另一个辅助表来保存各个记录的存放地址(指针) ：排序过程不需要移动记录，而仅需修改辅助表中的指针，排序后视具体情况决定是否调整记录的存储位置。

①比较适合记录数较多的情况；而②、③则适合记录数较少的情况。

    为讨论方便，假设待排序的记录是以①的情况存储，且设排序是按升序排列的；关键字是一些可直接用比较运算符进行比较的类型。

交换类排序法

所谓交换排序法是指借助数据元素之间互相交换进行排序的方法。冒泡排序与快速排序法都属于交换类排序方法。

交换排序 — 冒泡排序：

基本思想：

1.    比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.    对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3.    针对所有的元素重复以上的步骤，除了最后一个。

4.    持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序1：

冒泡排序2：

设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。

冒泡排序3：

如果有100个数的数组，仅前10个无序，后面90个已经排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。

冒泡排序毕竟是一种效率低下的排序方法，数据规模很小时，可以采用。数据规模比较大的时候，最好用其他排序方法。

算法分析：

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数  和记录移动次数 均达到最小值：   

所以，冒泡排序最好的时间复杂度为

若初始文件是反序的，需要进行 趟排序。每趟排序要进行次关键字的比较(1≤i≤n1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为：

综上，因此冒泡排序总的平均时间复杂度为：

时间复杂度：           O(n²)

最优时间复杂度：   O(n²)

平均时间复杂度：   O(n²)

空间复杂度：           O(n)total  O(1) auxiliary(辅助空间)

交换排序— 快速排序：

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种排序算法，最早由东尼·霍尔提出。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

基本思想为：

1.     从数列中挑出一个元素，称为"基准"（pivot），

2.     重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3.     递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。

选择5为基准对序列分区

7    1    2    3    9    4    8    6    5（pivot）

left遇到right第一个小于基准的交换

4    1    2    3    8    7    9    6    5

然后将>=基准的分到一边 然后先对左递归，然后右递归

{4    1    2    3}    {5    7    9    6    8}

{2    1    4    3}    {5    7    6    9    8}

{2    1    3    4}    {5    7    6    8    9}

{2    1}   {3    4}   {5    7    6 }   {8    9}

{1    2}   {3    4}   {5    6    7 }   {8    9}

{1}    {2}   {3}    {4}   {5}    {6    7}   {8}    {9}

{1}    {2}   {3}    {4}   {5}    {6}   {7}   {8}    {9}

1    2    3    4    5    6    7    8    9

快速排序----递归排序

快速排序----迭代排序

快速排序----C语言qsort（）函数

头文件：

用 法：

参数：

1 待排序数组首地址

2 数组中待排序元素数量

3 各元素的占用空间大小

4 指向函数的指针，用于确定排序的顺序

算法分析：

快速排序的最直接竞争者是堆排序（Heapsort）。堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是O(n log n)。快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况性能的机会。

如果事先知道堆排序将会是需要使用的，那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点，仅使用固定额外的空间（堆排序是原地排序），而即使是最佳的快速排序变化版本也需要Θ(log n)的空间。然而，堆排序需要有效率的随机存取才能变成可行。

快速排序也与归并排序（Mergesort）竞争，这是另外一种递归排序算法，但有坏情况O(n log n)运行时间的优势。不像快速排序或堆排序，归并排序是一个稳定排序，且可以轻易地被采用在链表（linked list）和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在炼串列上，但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点，是在最佳情况下需要Ω(n)额外的空间。

时间复杂度：

从一开始快速排序平均需要花费O(n log n)时间的描述并不明显。但是不难观察到的是分区运算，数组的元素都会在每次循环中走访过一次，使用O(n)的时间。在使用结合（concatenation）的版本中，这项运算也是O(n)。

在最好的情况，每次我们运行一次分区，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。因此，在到达大小为一的数列前，我们只要作log n次嵌套的调用。这个意思就是调用树的深度是O(log n)。但是在同一层次结构的两个程序调用中，不会处理到原来数列的相同部分；因此，程序调用的每一层次结构总共全部仅需要O(n)的时间（每个调用有某些共同的额外耗费，但是因为在每一层次结构仅仅只有O(n)个调用，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。

另外一个方法是为T(n)设立一个递归关系式，也就是需要排序大小为n的数列所需要的时间。在最好的情况下，因为一个单独的快速排序调用牵涉了O(n)的工作，加上对n/2大小之数列的两个递归调用，这个关系式可以是：

T(n) = O(n) + 2T(n/2)

解决这种关系式型态的标准数学归纳法技巧告诉我们T(n) = O(n log n)。

事实上，并不需要把数列如此精确地分区；即使如果每个基准值将元素分开为99%在一边和1%在另一边，调用的深度仍然限制在100log n，所以全部运行时间依然是O(nlog n)。

然而，在最坏的情况是，两子数列拥有大各为1和n-1，且调用树（call tree）变成为一个n个嵌套（nested）调用的线性连串（chain）。第i次调用作了O(n-i)的工作量，且 递归关系式为：

T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)

这与插入排序和选择排序有相同的关系式，以及它被解为T(n) = O(n2)。

空间复杂度：

被快速排序所使用的空间，依照使用的版本而定。使用原地（in-place）分区的快速排序版本，在任何递归调用前，仅会使用固定的額外空間。然而，如果需要产生O(logn)嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(log n)次的嵌套递归调用，所以它需要O(log n)的空间。最坏情况下需要O(n)次嵌套递归调用，因此需要O(n)的空间。

然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列，我们必须要记住我们的变量像是left和right，不再被认为是占据固定的空间；也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量，实际上快速排序在最好跟平均的情况下，需要O(log2 n)空间的比特数，以及最坏情况下O(nlog n)的空间。然而，这并不会太可怕，因为如果一个数列大部分都是不同的元素，那么数列本身也会占据O(n log n)的空间字节。

非原地版本的快速排序，在它的任何递归调用前需要使用O(n)空间。在最好的情况下，它的空间仍然限制在O(n)，因为递归的每一阶中，使用与上一次所使用最多空间的一半，且它的最坏情况是很恐怖的，需要空间，远比数列本身还多。如果这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，如果数列元素的大部分都是不同的，每一个将会需要大约O(logn)为原来存储，导致最好情况是O(n log n)和最坏情况是O(n2 log n)的空间需求。

最坏时间复杂度：         O(n²)

最优时间复杂度：   O(nlogn)

平均时间复杂度：   O(nlogn)

空间复杂度：           根据实现的方式不同而不同

-完-