直接插入排序

用户1154259

发布于 2018-01-17 11:12:02

50900

代码可运行

文章被收录于专栏：xingoo, 一个梦想做发明家的程序员xingoo, 一个梦想做发明家的程序员

运行总次数：0

代码可运行

时间复杂度:

如果排序的数组是正序的，那么时间复杂度相当于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");
}