八大算法总结之稳定性的比较及算法的选择

各种算法的稳定性、时间复杂度、空间间复杂度的分析：

1.稳定：冒泡排序、直接插入排序、二分插入排序、归并排序、基数排序和桶排序。

2.不稳定：直接选择排序、快速排序、希尔排序、堆排序。

3.O(n^2)：直接插入排序、简单选择排序、冒泡排序。

4.O(nlogn)：快速排序、归并排序、希尔排序、堆排序。

排序算法的选择：

1.数据规模较小

(1)序列基本有序，宜用直接插入排序。

(2)对稳定性不作要求，宜用简单选择排序，对稳定性有要求，宜用插入排序或冒泡排序。

2.数据规模一般

(1)序列杂乱无序，对稳定性没有要求，宜用快速排序。

(2)序列基本有序，对稳定性有要求，空间允许下，宜用归并排序。

3.数据规模较大

(1)对稳定性有求，宜用归并排序。

(2)对稳定性没要求，宜用堆排序。

4.序列初始基本有序(正序)

宜用直接插入，冒泡。

1、冒泡排序

算法步骤：

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

2)对每一对相邻元素重复第一步，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

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

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

冒泡排序示例：

代码示例：

void Bubble_Sort（int array[ ],int n）
{
    int i,j,temp;
    for(int i;i<n-1;i++)
    {
        for(j=0;j<n-1-i;j++)
            {
                  if(array[j]>array[j+1])
                   {
                          temp=array[j];
                          array[j]=array[j+1];
                          arrray[j+1]=temp;
                    }
             }
      }
}

冒泡算法的改进：<1>比如现在有一个 4 1 2 3 5 6 的数列，如果是按上面的排序算法排序的话，第一趟排序后数列已经排序好了，不用做无谓的工作了。所以第一种改进算法是设置一个标志性变量pose,用于记录每趟排序中最后一次进行交换的位置。由于pose位置之后的记录均已交换到位，所以在进行下一趟排序时，只要扫描到pose的位置即可；

改进后的算法：

void Bubble_Sort(int array[],int n)
{
    int j,temp;
    int i=n-1;
    while(i>0){
        int pose=0;
        for(j=0;j<i;j++)
        {
            if(array [j] > array[j+1])
            {
                pose=j;
                temp = array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
              }
            
        }
        i=pose;
    }
}

冒泡算法的改进：<2>传统的冒泡排序算法每一趟排序操作只能找到一个最大值或最小值，可以在每趟排序中进行正向和反向两遍冒泡的方法中一次得到最小值和最大值，从而使排序的趟数几乎减少一半

2、快速排序

算法步骤：

1)从数列中挑出一个元素，称为 “基准”（pivot）。

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

3)递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

二、插入类排序

1.直接插入排序

算法步骤：

1)将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2)从头到尾依次扫描待排序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2、二分插入排序

算法步骤：

1)将待排序序列第一个元素与有序序列最中间的元素比较，然后根据比较结果将待排序列折半。

2)重复第一步直到找到适当位置。

3、希尔排序

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤：

1)选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2)按增量序列个数k，对序列进行k 趟排序；

3)每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

三、选择类排序

1、简单选择排序

算法步骤：

1)首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

2)再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3)重复第二步，直到所有元素均排序完毕。

2、堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：

1)创建一个堆H[0..n-1]

2)把堆首（最小值）和堆尾互换

3)把堆的尺寸缩小1，目的是把新的数组顶端数据调整到相应位置

4) 重复步骤2，直到堆的尺寸为1

四、合并类排序

1、归并排序

算法步骤：

1)申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2)设定两个指针，最初位置分别为两个已经排序序列的起始位置

3)比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4)重复步骤3直到某一指针达到序列尾

5)将另一序列剩下的所有元素直接复制到合并序列尾

2、桶排序

桶排序 (Bucket sort)或所谓的箱排序，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（O（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

算法步骤：

1)首先，可以把桶设为大小为10的范围

2)将数据放到其对应的桶内

3)对每个桶中的元素排序

五、基数排序

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序时间复杂度： O(d(n+k)) n个d位数，每个数位有k种取值

算法步骤：

1)将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零.

2)从最低位开始, 依次进行一次排序.

这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.