交换排序
基本思想：
两两比较，如果发生逆序则交换，直到所有记录都排好序为止。
两种方法：
起泡排序O(n*n)
快速排序O(nlog2n)
冒泡排序
基本思想：每趟不断将记录两两比较，并按“前小后大”规则交换
优点：
每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；
一旦下趟没有交换，还可以提前结束排序
int main(int argc, const char * argv[]) {
int a[11];
int i,j,t;
printf("\nInput 10 numbers:\n");
for (i=1; i<11; i++) {
scanf("%d",&a[i]);
}
printf("\n");
for (j=1; j<=9; j++) {
for (i=1; i<10-j; j++) {
if (a[i]>a[i+1]) {
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
for (i=1; i<11; i++) {
printf("%d",a[i]);
}
}
return 0;
}
对冒泡排序进行改进
加入一个标志性变量flag，用于标志某一趟排序过程中是否有数据交换，如果
进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。
void bubble_sort(SqList &L)
{
int m,i,j,flag=1;RedType x;
m=n-1;
while((m>0)&&(flag==1))
{
flag=0;
for(j=1;j<=m;j++)
if(L.r[j].key>L.r[j+1].key)
{
flag=1;
x=L.r[j];
L.r[j]=L.r[j+1];
L.r[j+1]=x;
}
m--;
}
}
算法分析
设对象个数为n
比较次数和移动次数与初始排序有关
最好情况下：
只需要1趟排序，比较次数为n-1，不移动
最坏情况下：
需要n-1趟排序，第i趟比较n-i趟，移动3（n-i）次
