
感觉,好像比冒泡排序高级点?时间复杂度一样吗?
#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 n^2 插入排序 |
2 Bink10533 2017-04-27 23:16:30 +08:00 这个是插入排序的思想,而且 while 里不应该修改 i 的值,因为每次 for 循环后可以保证前 i+1 个元素是有序的。 |