数据结构-插入排序-直接插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

#include<stdio.h>
//插入排序 
void insert_sort(int *,int);

int main(){
    int i;
    int a[10]={1,5,66,4,89,6,7,3,1,9};
    insert_sort(a,10);
    for(i=0;i<10;i++){


        printf("%d",a[i]);
        printf("\n");
    }
    return 0;

}




void insert_sort(int *a,int n){


    int i,j,key;
    for(j=1;j<n;j++){

        key=a[j];
        //先保存第二个的数值 
        i=j-1;
        while(i>=0&&a[i]>key){
            // 然后此时的数和临时储存的数字进行比较

            a[i+1]=a[i];
            // 如果此时字比临时储存的大 的话  那么此时的数字 进行前移到下一个个位置 
            i--;
        }
        //否则此时的数字进行不变   临时变量保存到下一个数字的位置
        a[i+1]=key;
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

文章来源: hiszm.blog.csdn.net，作者：孙中明，版权归原作者所有，如需转载，请联系作者。

原文链接：hiszm.blog.csdn.net/article/details/78455686