学习了插入排序

2019-08-16 08:00:46来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

学习了插入排序

简单的理解,插入排序,就是原队列中不断的出列一个值,与已经出列的所有值进行一一比较,找到自己的位置进行插队。

下面是学习的来的插入排序以及自己对一些代码的注释;另外,在此基础上将其中的插队代码,单独做成了一个函数。

下面是插入排序的c++代码:

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 template<class T>
 6 void InsertionSort(T *p, int len);
 7 
 8 int main()
 9 {
10     int q[] = {8,5,7,4,0,9,6,2,3,1};
11     InsertionSort(q, 10);
12     for(int i=0; i<10; i++)
13     {
14         cout << q[i] << ' ';
15     }
16     cout << endl;
17     return 0;
18 }
19 
20 template<class T>
21 void InsertionSort(T *p, int len)
22 {
23     int line_up, wait;//line_up表示出列排队的总个数
24                     //wait表示等待出列的索引位置
25     for(wait=1; wait<len; wait++)
26     {
27         T tem = p[wait];
28         line_up = wait;//表示出列排队的最后位置
29                        //开始插入已经排好队的队列中(有line_up个值)
30         while(line_up>0 && p[line_up-1]>=tem)
31         {
32             p[line_up] = p[line_up-1];//将原来的值向后移动
33             line_up--;// 再看看下一个位置可不可以放tem
34         }
35         p[line_up] = tem;//索引位置选好后就可以插队了
36     }
37 }

改动的c++代码

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 template<class T>
 6 void InsertionSort(T *p, int len);
 7 
 8 template<class T>
 9 void Insert(const T& m, T *b, int j);
10 
11 int main()
12 {
13     int q[] = {8,5,7,4,0,9,6,2,3,1};
14     InsertionSort(q, 10);
15     for(int i=0; i<10; i++)
16     {
17         cout << q[i] << ' ';
18     }
19     cout << endl;
20     return 0;
21 }
22 
23 template<class T>
24 void InsertionSort(T *p, int len)
25 {
26     int line_up, wait;
27     for(wait=1; wait<len; wait++)
28     {
29         T tem = p[wait];
30         Insert(tem, p, wait);
31     }
32 }
33 
34 template<class T>
35 void Insert(const T& m, T *b, int j)
36 {
37     int i = j;
38     while(i>0 && b[i-1]>=m)
39     {
40         b[i] = b[i-1];
41         i--;
42     }
43     b[i] = m;
44 }

 


原文链接:https://www.cnblogs.com/yang901112/p/11330900.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Qt开源编辑器qsciscintilla的一些用法

下一篇:Ural 1029 Ministry 题解