八大排序算法代码实现

tip

本文所有排序算法均为升序排序

基本数据结构

typedef int dataType;
//这里主要针对整型数据进行排序
typedef struct
{
    vector<dataType> key;  //顺序表关键字
    int length;  //顺序表长度
}List;

一、插入排序

原始版本

void InsertSort_0(List &L)//对顺序表L进行插入排序
{
    int i,j;
    dataType temp;
    for(i=1;i<L.length;i++)
    {
        //将i号数据插入0到i-1的有序序列中
        temp = L.key[i];
        for(j=i-1;j>=0;j--)//向前寻找应该插入该数据的位置
        {
            if(L.key[j]>temp)
                L.key[j+1] = L.key[j];
            else
                break;
        }
        L.key[j+1] = temp;
    }
}

改进版本1

将顺序表的0号位置清空，作为哨兵位，在1到length的位置放置数据，可以省去循环出口判断的时间,也无需额外的变量来临时储存插入的数据

void InsertSort_1(List &L)
{
    int i,j;
    for(i=2;i<=L.length;i++)//注意这里开始和结束的位置和之前有所不同
    {
        L.key[0] = L.key[i];//将要插入的数据放到哨兵位上
        for(j=i-1;;j--)
        {
            if(L.key[j]>L.key[0])
                L.key[j+1]=L.key[j];
            else
                break;
        }
        L.key[j+1] = L.key[0];
    }
}

改进版本2

在寻找插入数据应该插入的位置时本质上是在做一个顺序查找，我们可以用二分查找取而代之，能够更大程度地减小复杂度

void InsertSort_2(List &L)
{
    int i,j,k;
    int low,high,mid;
    for(i=2;i<=L.length;i++)
    {
        L.key[0] = L.key[i];
        low = 1;    //查找区间下界
        high = i-1; //查找区间上界
        while(low<=high)
        {
            mid = (low+high)/2;
            if(L.key[mid]>L.key[0])
                high = mid-1;   //在前一段区间查找
            else
                low = mid+1;    //在后一段区间查找
        }
        //最后插入点一定是在L.key[mid]左或右，比较大小确定插入位置
        if(L.key[0]>=L.key[mid])
            k = mid+1;
        else
            k = mid;
        //将有序部分插入位置后面的所有点后移一位
        for(j=i-1;j>=k;j--)
            L.key[j+1] = L.key[j];
        L.key[k] = L.key[0];
    }
}

本文持续更新中，如有错误或不足之处，欢迎批评指正。