感觉,好像比冒泡排序高级点?时间复杂度一样吗?
#include<stdio.h>
int main(){
int numbers[] = {7,3,4,2,9,3,4,8,9,10,23,6,5};
int l = sizeof(numbers)/sizeof(int);
int i,temp;
for(i=0;i<l-1;i++){ //i<l-1 是因为通过 numbers[i]与 numbers[i+1]来比较的话,i+1=l-1 就够了
while(numbers[i] > numbers[i+1] && i >= 0){
temp = numbers[i+1];
numbers[i+1] = numbers[i];
numbers[i] = temp;
i = i - 1;
/*
当 numbers[i] > numbers[i+1] 发生也就是说要交换位置时,无法得知 numbers[i+1]与 numbers[i-1]的大小如何
只知道 numbers[i-1]肯定是没 numbers[i]大,但现在 number[i+1]也没 number[i]大,从而不知道 number[i+1]和 number[i-1]谁大
因此还需要一次比较,由于交换,比较的下标是[i-1]和[i](下标[i]处的值已经是[i+1]处的值了)
因此 i-1,这样的话下一轮的比较就变成了 numbers[i-1]比较 numbers[i-1+1]=numbers[i],正合题意
如果这一轮再需要交换,那么又是同样的问题,同样的处理。如此直至都比完即 i=0;
*/
}
}
int k;
for(k=0;k<l;k++){
printf("%d\t",numbers[k]);
}
return 0;
}
1
lrxiao 2017-04-27 20:51:18 +08:00 1
n^2 插入排序
|
2
Bink10533 2017-04-27 23:16:30 +08:00 1
这个是插入排序的思想,而且 while 里不应该修改 i 的值,因为每次 for 循环后可以保证前 i+1 个元素是有序的。
|