冒泡排序与选择排序

一.Bubble Sort(冒泡排序）：相邻的两个数进行大小比较符合要求左右位置交换。

void bubble(int a[],int lengh) { int i=0,j=0,nflag=0; if(a==NULL||lengh<=0)return; while(i<lengh) { for(j;j<lengh-i-1;j++) { if(a[j]>a[j+1]) { a[j]=a[j]^a[j+1]; a[j+1]=a[j]^a[j+1]; a[j]=a[j]^a[j+1]; nflag=j+1; } } i=lengh-nflag; nflag=0; j=0; } } int main() { int i=0; int a[]={2,10,5,9,8,11,1}; bubble(a,sizeof(a)/sizeof(a[0])); for(i;i<sizeof(a)/sizeof(a[0]);i++)//遍历数组 { printf("%d ",a[i]); } return 0; } 不用中间变量实现两个相同类型的变量交换：1.int a13;int b=5;a=a+b;b=a-b;a=a-b. ^通过异或相同的值等于原来的值。a,b不能指向一个空间。 冒泡排序是対已全部排好序的数组排序最快的 判断当前排序是否稳定：两个键值（元素本身的值）相同的元素在排序前后相对位置没有发生改变称当前排序为稳定排序。 O(1)代表常量空间复杂度 排序名称    最好时间复杂    平均时间复杂度度    最坏时间复杂度    空间复杂度    是否稳定 Bubble        O(n)                              O(n^2)                    O(n^2)              O(1)               稳定 select(选择排序）： void select(int a[],int length) { int i,j,dex;//dex记住单次循环最小数的下标 if(a==NULL)return; for(i=0;i<length;i++) { dex=i; for(j=i;j<length;j++) { if(a[j]<a[dex])//判断dex后面的数是否有比a[dex]小的 { dex=j;//有,用dex记住坐标 } } if(dex!=i)//dex!=i说明i后面有比a[i]小的交换他们的值 { a[i]=a[dex]^a[i]; a[dex]=a[i]^a[dex]; a[i]=a[i]^a[dex]; } } }

 

排序名称    最好时间复杂    平均时间复杂度度    最坏时间复杂度    空间复杂度    是否稳定 Select            O(n^2)                       O(n^2)                    O(n^2)              O(1)               不稳定