数学结构

image.png

冒泡排序

一趟排序后，一定把表中最大或最小元素放在其最终位置。

若采用冒泡排序法对序列（10,41,52,18,26,29）按从大到小进行排序，则排序过程中需要进行的元素之间的比较次数是___。
提取n个中最大（小）的元素放到最后，然后n-1个元素在取最大（小）的放在滴n-1个位置。
在一趟排序中前后两个元素对比，相反则交换位置。

image.png

5+4+3=12

插入排序法

从第二个元素开始，和前面的比大小，只要比前面的小就往前插入，直到比前面的大停止。然后第三个

void INSERTSORT(keytype K[],int n)
{
    int i,j;
    keytype temp;
    for(i=2;i<=n;i++){
        temp=K[i];
        j=i-1;
        while(j>0&&temp<K[j])   //将temp与K[j]循环比较
            K[j+1]=K[j--];      //如果temp比前面的小，前面的元素后移
        K[j+1]=temp;            //temp插入当前位置
    }
}

选择排序法

希尔排序法

快速排序

#include <stdio.h>
int qusort(int s[],int start,int end)    //自定义函数 qusort()
{
    int i,j;    //定义变量为基本整型
    i=start;    //将每组首个元素赋给i
    j = end;    //将每组末尾元素赋给j
    s[0]=s[start];    //设置基准值
    while(i<j)
    {
        while(i<j&&s[0]<s[j])
        j--;    //位置左移
        if(i<j)
        {
            s[i]=s[j];    //将s[j]放到s[i]的位置上
            i++;    //位置右移
        }
        while(i<j&&s[i]<=s[0])
            i++;    //位置左移
        if(i<j)
        {
            s[j]=s[i];    //将大于基准值的s[j]放到s[i]位置
            j--;    //位置左移
        }
    }
    s[i]=s[0];    //将基准值放入指定位置
    if (start<i)
        qusort(s,start,j-1);    //对分割出的部分递归调用qusort()函数
    if (i<end)
        qusort(s,j+1,end);
    return 0;
}

int main()
{
    int i,a[] = {11,99,45,12,36,69,22,62,796,4,696};//定义数组及变量为基本整型
    qusort(a,1,10);    //调用qusort()函数进行排序
    printf("排序后的顺序是：\n");
    for(i=1;i<=10;i++)
        printf("%5d",a[i]);    //输出排好序的数组
    printf("\n");
    return 0;
}

排序后的顺序是：
    4   12   22   36   45   62   69   99  696  796

递归快排
void QUICK(keytype K[],int s,int t)
{
    int i,j;
    if(s<t){
        i=s;
        j=t+1;
        while(1){
            do i++;
            while(!(K[s]<=K[i] || i==t));
            do j--;
            while(!(K[s]>=K[j] || j==s));
            if(i<j)
                SWAP(K[i],K[j]);  /*交换K[i]与K[j]的位置*/
            else
                break;
        }
        SWAP(K[s],K[j]);  /*交换K[s]与K[j]的位置*/
        QUICK(K,s,j-1);   /*对前一部分排序*/
        QUICK(K,j+1,t);   /*对后一部分排序*/
    }
}

取第一个元素，正序从第二个开始，找比第一个元素大的，倒序从第n个元素开始找比第一个元素小的，然后相互交换位置，循环重复。

image.png