<排序算法> 直接插入排序InsertSort

1.核心思想：
将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数+1的有序表。
2.代码实现：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 void PrintArr(int arr[],int len);
 5 void InsertSort(int arr[],int len)
 6 {
 7     if(arr == NULL || len <= 0)    return ;
 8     
 9     int yes = 0; //有序下标
10      int no = 1; //无序下标
11     int i,j;
12 
13     for(i=yes;i<len-1;i++)
14     {
15         if(arr[no] < arr[i])
16         {
17             int move = arr[no];
18             for(j=yes;j>=0;j--)
19             {
20                 if(arr[j] > move)
21                     arr[j+1] = arr[j];
22                 else 
23                     break;
24             }
25             arr[j+1] = move;
26         }
27         yes ++;
28         no ++;
29     }
30 
31     return ;
32 }
33 
34 void PrintArr(int arr[],int len)
35 {
36     for(int i=0;i<len;i++)
37         cout << arr[i] << " ";
38     cout << endl;
39 
40     return ;
41 }
42 
43 int main()
44 {
45     //int arr[10] = {9,8,7,6,5,4,3,2,1,0};
46     int arr[10] = {4,8,6,3,7,2,9,5,0,1};
47     InsertSort(arr,sizeof(arr)/sizeof(arr[0]));
48     PrintArr(arr,sizeof(arr)/sizeof(arr[0]));
49 
50     system("pause");
51     return 0;
52 }

3.复杂度分析：
直接插入排序在某些时候效率是很高的，如记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录的排序工作，此时直接插入很高效。还有就是记录数比较少的时候，直接插入的优势也比较明显。但满足这两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。
从空间上来看：只需要一个记录的空间。
从时间上来看：最好情况就是排序的表本身就是有序的为O(n)，最坏情况就是逆序情况。
因此，时间复杂度为O(n2)。
同样的时间复杂度，直接插入排序比冒泡和简单选择排序的性能要好一些。

<排序算法> 直接插入排序InsertSort

相关推荐