关于本周学习汇总
1起泡排序：
过程：首先将第一个记录的关键字和第二字的关键字进行比较，若为逆序，则将两个记录交换。
然后再比较第二个记录跟第三个记录关键字。
以此类推，直到第n-1个记录和第n个记录关键字进行比较为止。
这样做出了第一趟排序。
其结果是使得最大的数在第n的记录。
然后对前n-1的记录进行同样的操作。
结果得出次大的大在n-1记录上。
最后直到只有第1个和第2个记录进行比较后，完成所有的排序。
由此可以看出需要进行k（1<=k<n）趟排序。
其时间复杂度为O（n2）；
C程序：
#include<tdio.h>
void swap(int *,int *);
void bubble(int a[];int n);
int main(viod)
{
Int n ,a[8];
Int i;
Printf(“enter n(n<=8):”);
scanf(“%d”,&n);
printf(“enter a[%d]”,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
bubble(a,n);
printf(“after sorted,a[%d]=”,n)
for(i=0;i<n;i++)
printf(“%3d”,a[i])
return 0;
}
void bubble(int a[],int n)
{
int i ,j;
for(i=1;i<n;i++)
for(j=0;j<n-i;j++)
if(a[j]>a[j+1])
swap2(&a[j],&a[j+1]);
}
void swap2(int *px,int *py)
{
Int t;
t=*px;
px=*py;
py=t;
}
2.选择排序
对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。
然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推
一趟简单的选择排序操作为：通过n-i次关键字间的比较，从n-i+1的记录中选出关键字最小的记录作为有序序列中的第i个记录；
C程序实现
Include<stdio>
Int main(void)
{
int i,k,n,temp;
int a[10];
printf(“enter n”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
scanf(“%d”,a[i]);
//对n个数进行排序
for(k=0;k<n;k++){
for(i=k+1;i<n;i++)
if(a[k]<a[i])
temp=a[k];
a[k]=a[i]
a[i]=temp;
}
Printf(“after sorted:”)
for (i=0;i<n;i++)
pintf(“%d”,a[i]);
printf(“/n”)
return 0;
}
3.快速排序
快速排序的C语言代码实现
快速排序实质上是对“冒泡排序”的一种改进，整个排序过程可概括为：通过N 趟的排序将原本的排序数据分为若干块进行分块排序，而在每趟排序过程中，以指定的关键字将待排数据分别分为比关键字大的部分和比关键字小的部分，反复上述过程，将整个待排数列分散为若干个小数列而分别进行排序操作。
假设我们现对一列数进行快速排序，其C语言代码实现如下：
#include
Int partition（int*data,int low,int high）{
Int t=0;
t=data[low];while（low<high）{while（low<high&&data[high]>=t）
high--;
data[low]=data[high];
while（low<high&&data[low]<=t）low++;
data[high]=data[low];}
data[low]=t;returnlow;}
voidsort（int*data,intlow,inthigh）//快排每趟进行时的枢轴要重新确定，由此进//一步确定每个待排小记录的low及high的值
{
if（low>=high）
return;
intpivotloc=0;
pivotloc=partition（data,low,high）；
sort（data,low,pivotloc-1）；sort（data,pivotloc+1,high）；}
voidquick_sort（int*data,intn）//该函数进行sort过程的调用
{
sort（data,0,n-1）；}
int main（）{
int i;
int data[]={49,38,32,98,65,74,12,8};
quick_sort（data,sizeof（data）/sizeof（int））；
for（i=0;i<sizeof（data）/sizeof（int）；i++）
printf（“%d”,data[i]）；
printf（“\n”）；
return0;
}。