直接插入排序
直接插入排序
用户1154259
发布于 2018-01-17 19:12:02
发布于 2018-01-17 19:12:02
时间复杂度:
如果排序的数组是正序的，那么时间复杂度相当于O(n)，
而如果排序是随机的，时间复杂度相当于O(n^2/4).
倒置的时间复杂度是最高的，O(n^2).
算法思想：
该算法是设置了一个中间存储，每次读到的数据存储到中间值。向前遍历，如果大于这个值，继续向前，每次向前遍历时，把数据向后移，最后空出的位置，就是他本身应该在的位置。因此，如果是一个正序的数组，就不会出现移动的情况，时间复杂度也就降低了。
主要代码：
void straightInsert(int *arr,int length){
int i,j,k;
for(i=1;i<length;i++){
if(arr[i] < arr[i-1]){
k = arr[i]; //作为中间值存储每次的记录值
for(j=i-1;arr[j] > k;j--){ //把大于该值的元素都向后移
arr[j+1] = arr[j];
}
arr[j+1] = k;
}
}
}全部代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int arrtest1[10] = {3,4,7,8,0,9,1,2,6,5};
int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9};
int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0};
void copy(int *from,int *arr,int length);
void print(int *arr,int length);
void straightInsert(int *arr,int length);
int main(){
clock_t start,end;
int Arr[10];
int i;
start = clock();
for(i=0;i<100000;i++){
copy(arrtest1,Arr,10);
//print(Arr,10);
straightInsert(Arr,10);
//print(Arr,10);
}
end = clock();
printf("first test:%d\n",end-start);
start = clock();
for(i=0;i<100000;i++){
copy(arrtest2,Arr,10);
//print(Arr,10);
straightInsert(Arr,10);
//print(Arr,10);
}
end = clock();
printf("first test:%d\n",end-start);
start = clock();
for(i=0;i<100000;i++){
copy(arrtest3,Arr,10);
//print(Arr,10);
straightInsert(Arr,10);
//print(Arr,10);
}
end = clock();
printf("first test:%d\n",end-start);
getchar();
return 0;
}
void straightInsert(int *arr,int length){
int i,j,k;
for(i=1;i<length;i++){
if(arr[i] < arr[i-1]){
k = arr[i]; //作为中间值存储每次的记录值
for(j=i-1;arr[j] > k;j--){ //把大于该值的元素都向后移
arr[j+1] = arr[j];
}
arr[j+1] = k;
}
}
}
void copy(int *from,int *arr,int length){
int i;
for(i=0;i<length;i++){
arr[i] = from[i];
}
}
void print(int *arr,int length){
int i;
for(i=0;i<length;i++){
printf("%d ",arr[i]);
}
printf("\n");
}运行示例：
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-04-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读