冒泡排序
排序原理：
- 设置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次，因此时间复杂度为
二路归并排序是一种稳定的排序算法
网友评论