排序算法

1、概念

image.png

2、内排序与外排序

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。
排序算法的性能主要受3哥方面影响：
1、时间性能 2、辅助空间 3、算法的复杂性

简单选择排序算法
就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之

/* 对顺序表L作简单选择排序 */
void SelectSort(SqList *L)
{
    int i,j,min;
    for(i=1;i<L->length;i++)
    { 
        min = i;                        /* 将当前下标定义为最小值下标 */
        for (j = i+1;j<=L->length;j++)/* 循环之后的数据 */
        {
            if (L->r[min]>L->r[j])  /* 如果有小于当前最小值的关键字 */
                min = j;                /* 将此关键字的下标赋值给min */
        }
        if(i!=min)                      /* 若min不等于i，说明找到最小值，交换 */
            swap(L,i,min);              /* 交换L->r[i]与L->r[min]的值 */
    }
}

简单选择排序复杂度O(n^2)
直接插入排序
直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

/* 对顺序表L作直接插入排序 */
void InsertSort(SqList *L)
{ 
    int i,j;
    for(i=2;i<=L->length;i++)
    {
        if (L->r[i]<L->r[i-1]) /* 需将L->r[i]插入有序子表 */
        {
            L->r[0]=L->r[i]; /* 设置哨兵 */
            for(j=i-1;L->r[j]>L->r[0];j--)
                L->r[j+1]=L->r[j]; /* 记录后移 */
            L->r[j+1]=L->r[0]; /* 插入到正确位置 */
        }
    }
}

直接插入排序法的时间复杂度为O(n^2)，同样的时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些。

希尔排序

/* 对顺序表L作希尔排序 */
void ShellSort(SqList *L)
{
    int i,j,k=0;
    int increment=L->length;
    do
    {
        increment=increment/3+1;/* 增量序列 */
        for(i=increment+1;i<=L->length;i++)
        {
            if (L->r[i]<L->r[i-increment])/*  需将L->r[i]插入有序增量子表 */ 
            { 
                L->r[0]=L->r[i]; /*  暂存在L->r[0] */
                for(j=i-increment;j>0 && L->r[0]<L->r[j];j-=increment)
                    L->r[j+increment]=L->r[j]; /*  记录后移，查找插入位置 */
                L->r[j+increment]=L->r[0]; /*  插入 */
            }
        }
        printf("    第%d趟排序结果: ",++k);
        print(*L);
    }
    while(increment>1);

}