排序算法1

简单的排序算法

公用部分

#define MAXSIZE 10
typedef struct {
    int r[MAXSIZE+1];//r[0]用作哨兵或临时变量
    int length;
}SqList;

void swap(SqList *L,int i,int j)
{
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;
}

冒泡排序

每次循环都将最小的数移动到前面，并且在循环过程中也有部分较小的数位置被前移

void BubbleSort(SqList *L)
{
    int i,j;
    for(i=1;i < L->length;i++)
    {
        for(j=L->length-1;j>=i;j--)
        {
            if(L->r[j] > L->r[i])
                swap(L,j,j+1);
        }
    }
}

优化

当经过一次外层循环时，若没有发生交换，则说明已经排序完成，可以结束

void BubbleSort2(SqList *L)
{
    int i,j;
    int flag = 1;
    for(i=1;i<L->length-1 && flag;i++)
    {
        flag = 0;
        for(j=L->length;j>=i;j--)
        {
            if(L->r[j] > L->r[i])
            {
                swap(L,j,j+1);
                flag = 1;
            }

        }
    }
}

简单选择排序

每经过一次外层循环，找到最小的数字，进行交换

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;//更改最小值下表
        }
        if(i!= min)
        {
            swap(L,i,min);//若不相等，进行交换
        }
    }
}

直接插入排序

将一个记录插入到已经排好序的有序列表中，从而得到一个新的有序表

void InsertSort(SqList *L)
{
    int i,j;
    for(i=2;i<=L->length;i++)
    {
        if(L->r[i] < L->r[i-1])
        {
            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];
        }
    }
}

希尔排序

将原有的序列切割成若干个小的子序列，在子序列中进行直接插入排序，在对全体进行一次直接插入排序

void ShellSort(SqList *L)
{
    int i,j;
    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[0] = L->r[i];
                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];
            }
        }
    }while(increment>1);
}
10 Feb 2020