冒泡、快排、归并

冒泡排序

排序原理：

• 设置i代表交换趟数，设置j代表交换元素，设置交换标志done
• 将初始趟数i=1，交换标志done=1，代表已经交换。 接下来进入判断
• 当趟数小于记录个数并且已经发生过交换时：将交换标志归零；
• 从第一个元素开始，对相邻的两个元素进行比较，
  • 如果后一个元素小于前一个元素，则进行交换操作
  • 交换操作如下：
    • 暂时当前元素放置在哨兵位置
    • 将较小元素放置在当前元素的位置
    • 将哨兵元素放在较小元素的位置
      交换完毕后，将交换标志重置于1
• 进入下一趟循环

void bubblesort(table *tab)
{
    int i,j,done; 
//done=1代表已经交换过，done=0代表没有发生交换
    i=1;done=1; //从第一个元素开始
    while(i<tab->length&&done)
    {
        done=0;
        for(j=1;j<tab->length;j++)
        {
            if(tab->r[j+1].key<tab->r[j].key)
            {
                tab->r[0]=tab->r[j];
                tab->r[j]=tab->r[j+1];
                tab->r[j+1]=tab->r[0];
                done=1;
            }
        }
        i++;
    }
}

冒泡排序算法的时间复杂度为O(n²)
冒泡排序是一种稳定的排序算法

快速排序

排序原理：

• 设定左右两个下标，一个在头，一个在尾
  将第一个元素选为基元素
• 进行do…while判断：
  • 若最右边的元素的key大于基准元素的key，并且右下标元素大于左下标元素时，右下标左移。
  • 如果右下标元素大于左下标元素，将右下标元素的值放入左下标元素的位置，并且左下标右移。
  • 若最左边的元素的key小于基准元素的key，右下标左移
• 在左右下标重合时结束循环，并且将基准元素放入下标重合的位置。
• 然后将基准元素的左子列和右子列进行递归。

void quicksort(table *tab,int left,int right)
{   
    int i,j;
    if(left<right)
  {
    i=left,j=right;
    tab->r[0]=tab->r[i];//选第一个元素为基准元素
    do
    {                                               //从右端开始
        while(tab->r[j].key>tab->r[0].key&&i<j)j--;   //直至找到第一个右端不大于基值的元素
        if (i<j)                                      //找到了，并且在左右下标之间
        {
            tab->r[i].key=tab->r[j].key;          //将找到的右下标元素放入上一个元素的空位置
            i++;                                   //并且左端右移，准备从左端开始查找
        }
        while(tab->r[i].key<tab->r[0].key&&i<j)i++; //直至找到了第一个左端不小于基值的元素
        if (i<j)                                     //找到了，并且在左右下标之间
        {
            tab->r[j].key=tab->r[i].key;          //将找到的左下标元素放在上一个元素的空位置
            j--;                                   //并且右端左移，准备从右端开始查找
        }
    }while(i!=j)                                  //直至左下标与右下标重合，即为基值的序位
    tab->r[i]=tab->r[0];
    quicksort(tab,left,i-1);               //如此递归执行基值的左子列和右子列
    quicksort(tab,i+1,right);      
  }     
}

快速排序的时间复杂度为
快速排序是不稳定的排序算法

归并排序（要求掌握二路归并即可）

排序原理：

首先将一组无序表，拆分，直至拆分至单个记录，由于单个记录有序，从第一个起始地址开始，将长度相同相邻的两个段依次进行归并(一次归并)，并将起始地址作为下一次归并的起始地址，对于剩下长度不同，但含终点的有序段进行归并，归并后即完成了(一趟归并)，将有序段的长度翻倍后，循环归并，得到最后两段有序段，再将其做一次(一次归并)，即归并完成。

void merge(table *tabs,table *tabg,int u,int m,int v)//一次归并 
//归并两个有序段tabs[u,m] tabg[m+1,v]   
{
  int i,j,k,t; //i代表第一个段，j代表第二个段，k是第二段的起始地址
  i=u; //u是第一段的起始位置
  j=m+1;  //m+1是第二段的头
  k=u;  
  while(i<=m&&j<=v)     
  {                           /*将两段有序元素中元素值较小的元素依次放入目标tabg中*/
    if(tabs->r[i].key<=tabs->r[j])
    {
        tabg->r[k]=tabs->r[i];
        i++;
    }
    else
    {
        tabg->r[k]=tabs->r[j];
        j++;
    }
    k++;
  }
  if(i<=m)
    for(t=i;t<=m;t++)        /*将第1段剩余元素放入目标tabg中*/
        tabg->r[k+t-i]=tabs->r[t];
    else
    for(t=j;t<=v;t++)         /*将第2段剩余元素放入目标tabg中*/
        tabg->r[k+t-j]=tabs->r[t];
}

void mergepass(table *tabs,table *tabg,int length)//一趟归并
{
    int i,j,n;
    n=tabg->length=tabs->length;
    i=1;
    while(i<=n-2*length+1)      /*将以i为起点，长度为length的相邻两个有序段依次进行归并*/
    {
        merge(tabs,tabg,i,i+length-1,i+2*length-1)  /*一次归并*/
        i=i+2*length;                               /*置下一个一次归并的起始位置*/
    }
    if(i+length-1<n)     /*对剩下的1个长为len,另1个长度不足len，终点为n的两个有序段归并*/
        merge(tabs,tabg,i,i+length-1,n);
    else                        /*对剩下的1个长不超过len,终点为n的有序段进行处理*/
        for(j=i;j<=n;j++)
            tabg-r[j]=tabs->r[j];
}                               /*  本算法结束后tabg中的有序段的长度为2*len  */

void mergesort(table *tab)
{
    int length;
    table temp;                /*中间变量*/
    length=1;                    /*初始时有序段的长度为1*/
    while(length<tab->length)  /*有序段的长度小于待排序元素的个数，继续归并*/
    {
        mergepass(tab,&temp,length)  /*一趟归并，结果在temp中*/
        length=2*length;                   /*有序段的长度翻倍*/
        mergepass(&temp,tab,length)  /*一趟归并，结果在tab中*/
        length=2*length;                   /*有序段的长度翻倍*/
    }
}

对于二路归并排序而言，每一趟归并都会使有序子长度增长一倍，因此需要经过次一趟归并，才能产生长度为n的有序段，每一趟归并都需进行最少n-1次，因此时间复杂度为
二路归并排序是一种稳定的排序算法