排序算法总结(一)

作者: veaxen 分类: 数据结构与算法 发布时间: 2017-04-20 21:37

1、排序算法的分类

在本文的开始,我们先来看看排序是如何分类的。

1.1、稳定排序和非稳定排序

在待排序的记录中,如果存在多个关键码相同的记录,经过排序后,这些记录的相对次序依然保持不变,即排序后这两个相同的对象具有与排序前相同的顺序,那么就称相应的排序算法是稳定的,否则就是不稳定的。

1.2、内排序和外排序

所谓的内排序是指所有的数据已经读入内存,在内存中进行排序的算法。排序过程中不需要对磁盘进行读写。同时,内排序也一般假定所有用到的辅助空间也可以直接存在于内存中。与之对应地,另一类排序称作外排序,即内存中无法保存全部数据,需要进行磁盘访问,每次读入部分数据到内存进行排序。

本文介绍的排序算法仅限于内排序。

2、插入排序

2.1、直接插入排序

直接插入排序的基本操作就是:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数量增1的有序表。

代码如下:

/**直接插入排序*/
int insertSort(int array[],int len)
{
    int i,j,insertNum;
    for(i=1;i<len;i++){
        insertNum = array[i];//待插入的数据
        for(j=i-1;j>=0;j--){
            if(insertNum < array[j]){
                array[j+1] = array[j];
            }else{
                break;
            }
        }
        array[j+1] = insertNum;
    }
}

在最坏的情况下,直接插入排序算法的时间效率为O(n^2),对于n很小的数组,插入排序简单易行,对于n较大的数组,直接插入排序效率过低,不宜采用。

直接插入排序是稳定排序

2.2、二分插入排序

二分插入排序又叫折半插入排序,它同直接插入排序一样,是每次将一个数据对象插入已经排好的顺序表中。设在顺序表中有对象序列V[0],V[1],V[2],…,V[n-1],其中,V[0],V[1],V[2],…,V[i-1]是排好序的对象。二分插入排序是用折半查找法寻找V[i]的插入位置,然后插入这个对象。同样需要n-1趟比较。折半查找法的使用是二分插入排序和直接插入排序的区别。

代码如下:

void BinaryInsertSort(int array[],int len)
{
    int i,mid,low,high,insertNum;

    for(i=1;i<len;i++){
        insertNum = array[i];
        low = 0;
        high = i-1;
        while(low<=high){
            mid = (low+high)/2;
            if(insertNum > array[mid]){
                low = mid+1;
            }else{
                high = mid-1;
            }
        }
        for(int j=i;j>low;j--){
            array[j] = array[j-1];
        }
        array[low] = insertNum;
    }
}

二分插入排序的关键字比较的时间复杂度比直接插入排序要快,但是两者的对象移动次数是一样的,所以二分插入排序的时间复杂度还是跟直接插入排序一样,在最坏的情况下时间效率也为O(n^2)。

二分插入排序是稳定排序

2.3、希尔排序

希尔排序是对直接插入排序的优化,直接插入排序的性能与初始化序列的排序情况有直接关系,在最坏的情况下(初始化序列完全逆序),直接插入排序的时间复杂度为O(n^2),但是当初始化序列的大致有序时,直接插入排序的性能会有所提高,至于提高多少要看序列的初始化排序情况,希尔排序就是先对初始化序列先进行大致排序。

希尔排序的基本思想:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,并使整个序列中的记录基本有序,再对全体记录进行一次排序。

为了可以更好的理解希尔排序,下面举例子说明一下,比如有一个数组[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为gap=5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序(此时就是简单的直接插入排序了)。

下面是希尔排序的代码如下:

void ShellSort(int array[],int len)
{
    int i,j,insertNum;
    int gap = len/2;//获得步长
    while(gap){
        for(i=gap;i<len;i++){
            insertNum = array[i];
            for(j=i;j>=gap;j-=gap){
                if(insertNum<array[j-gap]){
                    array[j] = array[j-gap];
                }else{
                    break;
                }   
            }
            array[j] = insertNum;
        }
        gap /= 2;//缩小步长
    }
}

分析希尔排序的时间复杂度是一件十分困难的事情,特别在间隔选取方式发生变化时的情况下,尚不能给出一个定量的结果,但是希尔排序从实践中已经可以知道是比直接插入排序要快许多。

希尔排序是一个不稳定的排序方法

选择排序

选择排序的基本思想是:在排序的时候每次选择最小或最大项,将其放入合适的位置,依此类推。

直接选择排序

直接选择排序是最简单的选择排序方法,它的基本步骤是(以升序排列为例):首先在一组数据对象中选择具有最小关键码的对象,若它不是对象序列的第一个对象,则将它与这组对象中的第一个对象对调位置,然后在这组对象中剔除具有最小关键码的对象。重复上述步骤,得到有序序列。

代码如下:

void SelectSort(int array[],int len)
{
    int minIndex;
    for(int i=0;i<len;i++){
        minIndex = i;
        for(int j=i+1;j<len;j++){
            if(array[minIndex]>array[j])
                minIndex = j;
        }

        //交换位置
        //注意当采用异或进行交换时,要避免i和minIndex相等,否则计算结果为0; 
        if(i!=minIndex){
            array[i] ^= array[minIndex];
            array[minIndex] ^= array[i];
            array[i] ^= array[minIndex];
        }
        /*
        int tmp;
        tmp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = tmp;
        */
    }
}

我在写上面代码的时候发现了一个问题,我顺便在这里提一下,不能使用异或运算来交换同一个变量,也就是说,为了说明清楚这个问题,我们来看看
假设:
i == minIndex;
array[minIndex] = 0b00;

array[i] ^= array[minIndex]; ——————– array[i] = 0b00
array[minIndex] ^= array[i]; ——————– array[minIndex] = 0b00
array[i] ^= array[minIndex]; ——————– array[i] = 0b00

一开始没有考虑到这个问题,导致程序不能正常排序,注意到这个问题之后,修改程序就可以了,如果是C++,可以考虑C++库自带的swap(T &a,T &b)函数。

关于选择排序还有几个需要注意的,选择排序的性能不依赖数据的初始化排列,这与前面的插入排序不同,但简单的选择排序的时间复杂度O(n^2)的增率很大,因此算法只适合较小的n。该算法需要O(n^2)次比较操作,而仅需要O(n)次移动操作,所以当数据移动成本高时,选择排序优于其它排序算法

直接选择排序是不稳定排序算法


今天就先写到这里,由于篇幅可能会很长,所以分成几篇博文来写吧,其它排序算法等我有空了再来总结。

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据