插入排序

1.插入排序的特点和方法：

　　1）构建有序序列和无序序列；无序序列插入到有序序列中

　　2）应用场景：序列基本有序，元素较少。

　　3）两步操作：符合要求的元素拿出来，随后符合条件的元素后移。

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<time.h>
 4 using namespace std;
 5 
 6 #define MAX 20
 7 //数组打印
 8 void PrintArray05(int arr[], int len)
 9 {
10     for (int i = 0; i < len; i++)
11     {
12         cout << arr[i] << " ";
13     }
14     cout << endl;
15 }
16 
17 //插入排序
18 void InsertFunc05(int* arr, int len)
19 {
20     for (int i = 1; i < len; i++)　　　　　　　　　　　　　　　　//要点1.
21     {
22         if (arr[i] < arr[i - 1])　　　　　　　　　　　　　　　　//要点2.
23         {
24             int temp = arr[i];        //把小的元素拿出来　　　　//要点3.
25             int j;
26             for (j = i - 1; j >= 0 && arr[j] > temp; j--)　　　//要点4.
27             {
28                 arr[j + 1] = arr[j];        //大的元素后移
29             }
30 
31             arr[j+1] = temp;　　　　　　　　　　　　　　　　　　　　//要点5.
32         }
33     }
34     cout << "插入排序第一种" << endl;
35 
36 }
37 //创建数组
38 void test05()
39 {
40     int arr[MAX];
41     srand((unsigned int)time(NULL));
42 
43     for (int i = 0; i < MAX; i++)
44     {
45         arr[i] = rand() % MAX;
46     }
47 
48     PrintArray05(arr, MAX);
49 
50     InsertFunc05(arr, MAX);
51     PrintArray05(arr, MAX);
52 
53 
54 }
55 int main()
56 {
57 
58     test05();
59 
60     system("pause");
61     return EXIT_SUCCESS;
62 }

1.主要思想：将无序序列插入有序序列中。

　　1）当循环刚开始时，把第一批符合判断的那些元素当作有序序列，其后的所有元素当作无序序列，将无序序列的第一个元素提取出来，将他与有序序列最后一个元素依次往前比较，符合条件的有序序列元素后移，直至不符合条件；此时将提取出来的元素插入到这个位置。

　　2）然后依次按照上述方法往后比较

2.第二中插入排序

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<time.h>
 4 using namespace std;
 5 
 6 #define MAX 20
 7 //数组打印
 8 void PrintArray06(int arr[], int len)
 9 {
10     for (int i = 0; i < len; i++)
11     {
12         cout << arr[i] << " ";
13     }
14     cout << endl;
15 }
16 
17 //插入排序
18 void InsertFunc06(int* arr, int len)
19 {
20     int temp, j, k;
21     for (int i = 1; i < len; i++)
22     {
23         k = i; 
24         temp = arr[k];
25         for (j = i - 1; j >= 0 && arr[j] > temp; j--)
26         {
27             arr[j + 1] = arr[j];
28             k = j;
29         }
30         arr[k] = temp;
31     }
32     cout << "第二种插入排序" << endl;
33 }
34 
35 
36 
37 //创建数组
38 void test06()
39 {
40     int arr[MAX];
41     srand((unsigned int)time(NULL));
42 
43     for (int i = 0; i < MAX; i++)
44     {
45         arr[i] = rand() % MAX;
46     }
47 
48     PrintArray06(arr, MAX);
49 
50     InsertFunc06(arr, MAX);
51     PrintArray06(arr, MAX);
52 
53 
54 }
55 int main()
56 {
57 
58     test06();
59 
60     system("pause");
61     return EXIT_SUCCESS;
62 }

这两种效率没有什么区别：只是第二种好理解一些。

但是第一种的代码可以少执行几行（因为当判断条件不符合时，就不会执行下面的赋值语句，）；而第二种则会执行。