平方阶排序算法

基本概念

度量指标

时间复杂度
空间复杂度
排序算法的稳定性：Ri和Rj关键词相同，排序前顺序与排序后一致则稳定，否则不稳定

直接插入排序

把第i个元素插入到前n-1个元素中

void InsertionSort(int R[],int n)
{
    for(int i=2;i<=n;i++)
    {
        int k=R[i],j=i-1;
        while(j>=1 && R[j]>k)//左移，找第一个小于k的数
        {
            R[j+1]=R[j];//元素右移
            j--;
        }
        R[j+1]=k;
    }
}

时间复杂度分析
最好情况：O(n) 已经排好序，每次插入操作Ri只用与前面有序子数组的最后一个元素比较一次
最坏情况：O(n^2)初始为逆序，每次插入操作花费O(n)
平均情况：O（n^2）
稳定性：稳定

冒泡排序

稳定：前面元素大于后面元素才交换，等于不交换

初级冒泡排序算法 O(n^2)

void SimpleBubbleSort(int R[],int n)
{
    for(int bound=n;bound>=2;bound--)
    {
        for(int i=1;i<bound;i++)
        {
            if(R[i]>R[i+1])
                swap(R[i],R[i+1]);
        }
    }
}

void BubbleSort(int R[],int n)
{
    int bound=n;
    while(bound>0)
    {
        int t=0;
        for(int i=1;i<bound;i++)
        {
            if(R[i]>R[i+1])
            {
                swap(R[i],R[i+1]);
                t=i;
            }
        }
        bound=t;
    }
}

最好情况：O(n)
最坏情况：O(n^2)
稳定

直接选择排序

选最大的放后面

void SelectionSort(int R[],int n)
{
    for(int i=n;i>=1;i--)
    //i表示当前处理的子数组右边界
    //在子数组R[1]..R[i]中选择最大元素与R[i]交换
    {
        int max=1;
        for(int j=2;j<=i;j++)
        {
            if(R[j]>R[max]) 
                max=j;
        }
        swap(R[max],R[i]);
    }
}

时间复杂度
最好，最坏，平均 O(n^2);
不稳定

希尔排序

直接插入排序的改进（可以看作直接插入排序plus）
直接插入排序算法在”短文件“，”待排序文件基本有序“时速度快，希尔排序充分利用了这两个特性

希尔排序基本过程

将元素分为d组
对每组元素使用直接插入法排序
把d值减小，重复执行①②

增量d的一种简单选取方法（以n=10为例）
d1=n/2=5
d2=d1/2=2
d3=d2/2=1

开始时增量大，每组元素少，插入排序速度较快
随着增量逐渐减小，每组元素个数变多，但大多数元素已基本有序，而插入排序在元素接近有序时速度快
一般认为平均时间复杂度在O(n^2)和O(nlogn)之间，与d有很大关系
稳定性：不稳定

void ShellSort(int R[],int n)
{
    for(int d=n/2;d>0;d/=2)
    {
        for(int i=d+1;i<=n;i++)
        //...R[i-3d],R[i-2d],R[i-d] <-R[i]
        //第二个数的起始下标是R[i+d]
        {
            int k=R[i];
            int j=i-d;
            while(j>0 && R[j]>k)//向左移，找第一个小于k的
            {
                R[j+d]=R[j];
                j-=d;
            }
            R[j+d]=k;
        }
    }
}

数据结构12-平方阶排序算法