//算法分析:平均时间复杂度o(n2),空间复杂度o(n),正序时时间复杂度为o(n),反序时为o(n2),是稳定性的算法(相同记录的相对位置不会改变)
void insert_sort(int* buf, int len) {
int compare_count = 0;
int move_count = 0;
for(int i=1; i int now = buf[i];
compare_count++;
if(now > buf[i-1])continue;
//引入哨兵
int temp = buf[-1];
buf[-1] = now;
int j=i-1;
do {
compare_count++;
move_count++;
buf[j+1] = buf[j];
j--;
} while(now < buf[j]);
move_count++;
buf[j+1] = now;
//恢复哨兵
buf[-1] = temp;
}
printf("compare_count:%d\nmove_count:%d\n", compare_count, move_count);
}
int main() {
int arr[10];
int len = sizeof(arr)/4;
for(int i=0; i arr[i] = 10-i;
}
// quick_sort(arr, len);
insert_sort(arr, len);
for(int i=0; i printf("%d\t", arr[i]);
}
printf("\n");
getchar();
return 0;
}
阅读(1138) | 评论(0) | 转发(0) |