直接插入排序

时间复杂度:

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

运行示例:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 堆排序

    构建堆的时间复杂度为O(n),而第I次调整堆的时间复杂度为O(logi),因此,无论什么情况下时间复杂度都为O(nlogn)。 算法思想:   首先,对数组从n...

    用户1154259
  • 简单选择排序

    选择排序时间复杂度也为O(n^2) 算法思想: 选择排序即每次length-i的长度内选择一个最小的元素,与第一个进行替换,这样大循环length次后,就可以得...

    用户1154259
  • 冒泡排序

    冒泡排序时间复杂度上为O(n^2) 冒泡排序三种方式,第一种也是最基本的排序: void bubbleSort1(int *arr,int length){ ...

    用户1154259
  • 堆排序

    构建堆的时间复杂度为O(n),而第I次调整堆的时间复杂度为O(logi),因此,无论什么情况下时间复杂度都为O(nlogn)。 算法思想:   首先,对数组从n...

    用户1154259
  • 简单选择排序

    选择排序时间复杂度也为O(n^2) 算法思想: 选择排序即每次length-i的长度内选择一个最小的元素,与第一个进行替换,这样大循环length次后,就可以得...

    用户1154259
  • C++函数退化修复

    编译器会视为:int getLen(int*),发生退化,导致产生的结果是2(64位操作系统结果),原因是退化之后取的是指针 8字节除以int 4字节,得到2,...

    公众号guangcity
  • 最大连续子数组

    题目: 给定一个数组 A[0,1..... ,n-1],求A的连续子数组,使得该子数组的和最大。

    梅花
  • 算法回顾--如何写递归?

    总之递归就是”装傻”的把原始的思路表现出来,不需要关心具体过程,只需要不停的缩小问题规模,然后答案自然就会被计算出来.

    屈定
  • 聊聊「插入排序」的正确姿势

    面试官最爱考察的是一个被试者对知识掌握的灵活程度和熟练程度,当一道题目可以同时考察到被试者多个知识点的掌握程度和思考能力时,面试官最爱这样的题目,而且对于插入排...

    五分钟学算法
  • 【C语言笔记】关于数组的一个陷阱!

    所以,&a[2] - &a[0]的结果是8?但是,事实不是这样的!!让我们把其结果打印出来:

    正念君

扫码关注云+社区

领取腾讯云代金券