首页 > 编程语言 > 详细

排序算法之——插入排序

时间:2016-02-04 18:13:43      阅读:297      评论:0      收藏:0      [点我收藏+]

一、排序思想

  我们可以假想出两个容器,一个容器中是待排序的元素,一个是空容器。每次从容器中取出一个元素(一般是第一个),然后插入空容器中,而插入空容器时必须按大小顺序,找到合适位置,这个过程就是插入排序。

  当我用c方式实现时,发现插入排序居然与冒泡排序神奇般的相似,这是我始料未及的。而且他们的时间复杂度都是O(n^2)。老子说:“此二者同出而异名”,莫非它们背后的排序思想竟是一致的么?

  又或者如《系辞传》所说:“天下同归而殊途,一致而百虑。”两种排序算法,到最后竟走上殊途同归的道路,恰如“西下夕阳东上月,一般花影有寒温”,花影还是那个花影,只是一个是太阳照出来的,一个是月亮照出来的,一个觉得寒一些,一个觉得暖一些吧。

二、插入图示

  技术分享

三、代码示例

c版本

技术分享
 1 void swap(int * a, int * b)
 2 {
 3     int tmp = *a;
 4     *a = *b;
 5      *b = tmp;
 6 }
 7 
 8 void insertSort(int * a, int len)
 9 {    //from begin to end, find a number in order and insert it to the right place
10      //sorted number is added, unsored number is decreased
11     for(int i = 0; i < len - 1;  ++i)
12     {
13          for(int j = i; j >= 0; --j)
14          {
15               if(*(a+j) > *(a + j + 1))
16               {
17                    swap(a + j, a + j + 1);
18               }
19          }  
20     }      
21 }       
View Code

c++ 版

技术分享
 1 template<typename T>
 2 inline void InsertSort(std::list<T> & source)
 3 {
 4    //should push at least one element
 5    //the we can compare elements between two list
 6     std::list<T> tmp;
 7     tmp.push_back(*source.begin());
 8     while()
 9     {
10          auto it = tmp.begin();
11          for(; it  != tmp.end(); ++it)
12          {
13              if(*source.begin() <= *it)
14              {
15                    tmp.insert(it, *source.begin());
16                    source.pop_front();
17                    break;
18              }
19          }
20         //the insert motion will not invalid this iterator
21         //this condition happens when *source.begin() is the largest element
22          if(it == tmp.end())
23          {
24                 tmp.push_back(*source.begin());
25                 source.pop_front();
26          }
27     }  
28     source.assign(tmp.begin(), tmp.end());
29 }
View Code

四、算法结语

    子夏说:“虽小道,必有可观者焉”。这个排序算法只是浩如烟海的算法系统中的极小部分,然而仔细揣摩,也必然会有所收获。插入排序体现了一种打破旧体制,实现新秩序的思想,正所谓不破不立,推而演之,难道不能用在治家、治国等大的方面吗?

    他接着说:“致远恐泥,是以君子不为也。”写代码终究属于小技能吧,希望自己能够走得更高更远,不要只是陷在代码中间!

                                                          丙申年立春笔

 

排序算法之——插入排序

原文:http://www.cnblogs.com/renzhenxuexi/p/5175964.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!