七大排序之插入排序

2021-01-05 16:28

阅读：507

标签：第一步 rand 一个保存 bsp sig size signed 依次

做法;将无序序列插入到有序序列中；

结论：插入排序在什么情况下效率高：【1】如果序列基本有序的情况下【2】插入排序时候数据序列比较少。

例子： 3 1 4 2 5 共五个数字. length=5;

【1】第一步先将序列分为有序序列和无序序列

有序：3

无序：1 4 2 5

【2】将无序序列插入到有序序列中，所以外层循环变量i应该从下标为1的1开始到下标为4的值为5结束；

for (int i = 1; i

【3】将arr[i]与arr[i-1]比较，如果arr[i]

if (arr[i - 1] > arr[i]) {
            int temp = arr[i];

【4】定义内层循环k,k初始化为i的前一个值即：k=i-1,(k>=0),将保存下来的temp值与arr[k]比较，若temp值小，则将arr[k]（即arr[i]）的位置被arr[k]重写覆盖，此时k--,再比较arr[k]与temp的值，若temp小则将arr[k+1]=arr[k]，依次下去，直到arr[k]

1         if (arr[i - 1] > arr[i]) {
2             int temp = arr[i];
3             int k = i - 1;
4             for (; k >= 0 && arr[k] > temp; k--) {
5                 arr[k + 1] = arr[k];
6             }
7             arr[k + 1] = temp;
8         }

整体实现代码：

 1 #include 2 #include 3 #include 4 #include 5 using namespace std;
 6 const int Max = 10;
 7 
 8 void swap(int& a, int& b) {
 9     int temp = a;
10     a = b;
11     b = temp;
12 }
13 
14 long getSystemTime() {
15     struct timeb tb;
16     ftime(&tb);
17     return tb.time * 1000 + tb.millitm;
18 }
19 void Print(const int* arr, int length) {
20     for (int i = 0; i ) {
21         cout " ";
22     }
23 }
24 void InsertSort(int * arr,int length) {
25     for (int i = 1; i ) {        
26         if (arr[i - 1] > arr[i]) {
27             int temp = arr[i];
28             int k = i - 1;
29             for (; k >= 0 && arr[k] > temp; k--) {
30                 arr[k + 1] = arr[k];
31             }
32             arr[k + 1] = temp;
33         }        
34     }
35 }
36 int main() {
37     int arr[Max];
38     srand((unsigned)time(NULL));
39     for (int i = 0; i ) {
40         arr[i] = rand() % Max;
41     }
42     cout "排序前：\n";
43     Print(arr, Max);
44     long pt = getSystemTime();
45     InsertSort(arr, Max);
46     long at = getSystemTime();
47     cout "\n排序后：\n";
48     Print(arr, Max);
49 
50     cout "\ntime of sort:" "ms\n";
51 
52 
53     return 0;
54 }

七大排序之插入排序

标签：第一步 rand 一个保存 bsp sig size signed 依次

原文地址：https://www.cnblogs.com/jibisheng/p/12981125.html

上一篇：Java 抽象类

下一篇：python 动图gif 合成

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：七大排序之插入排序
文章链接：http://soscw.com/index.php/essay/40300.html

亲，登录后才可以留言！

七大排序之插入排序

评论

热门文章

推荐文章

最新文章

置顶文章