插入排序的主要思想是将一个待排序的一组数按照其关键码的大小插入到已经排好序的有序序列中，直到所有待排元素插入对应的序列中。下面给出维基百科上插入排序的定义：(https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F)
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。下面用一个GIF图形象的展示该过程：

下面主要介绍直接插入排序和希尔排序。
直接插入排序
直接插入排序是最简单的插入排序，往往实现该算法都是借助数组，思路就是扫描数组，把元素插入到有序的序列中。下面通过简单的给出代码：

				[cpp]view plaincopy
				
 print? 
			
				#include   
			
				using namespace std;   
			
				void straightSort(int *, int);   
			
				int j;　／／ｊ是全局变量   
			
				void straightSort(int *arry, int length) {   
			
				    int flag;   
			
				    for (int i = 0; i<length; i++) {  </length; i++) {  <> 
			
				        flag = arry[i];   
			
				        for (j = i - 1; j >= 0 && arry[j]>flag; j--) {   
			
				            arry[j + 1] = arry[j];   
			
				        }   
			
				        arry[j + 1] = flag;／／由于第二个for循环j自身减一退出循环，该处j需要自身加一   
			
				    }   
			
				}   
			
				int main(){   
			
				int arry[] = {11,5,2,1,10,4,6,8,7};   
			
				int length = sizeof(arry) / sizeof(int);   
			
				straightSort(arry,length);   
			
				for (int i = 0; i <length; i++) {  </length; i++) {  <> 
			
				    cout << arry[i] <<" ";   
			
				   }   
			
				    cout << endl;   
			
				}

希尔排序

希尔排序（Shell Sort）是对直接插入排序的一种改进，主要思想就是把待排序的序列分割成若干个子序列，在子序列中分别进行直接插入排序，待整个序列基本有序时，再对全体元素进行一次直接插入排序。

给出该过程的代码：

				[cpp]view plaincopy
				
 print? 
			
				#include   
			
				using namespace std;   
			
				void shellSort(int *, int);   
			
				void shellSort(int *arry, int length) {   
			
				    {   
			
				        int j, gap;   
			
				    //  for (gap = 3; gap > 0; gap--)   
			
				        for (gap = length / 2; gap > 0;gap/=2)   
			
				            for (j = gap; j < length; j++)   
			
				                if (arry[j] < arry[j - gap])   
			
				                {   
			
				                    int temp = arry[j];   
			
				                    int flag = j - gap;   
			
				                    while (flag >= 0 && arry[flag] > temp)   
			
				                    {   
			
				                        arry[flag + gap] = arry[flag];   
			
				                        flag -= gap;   
			
				                    }   
			
				                    arry[flag + gap] = temp;   
			
				                }   
			
				                 }   
			
				          }   
			
				void  main() {   
			
				    int arry[] = { 11,5,2,10,4,6,8 };   
			
				    int length = sizeof(arry) / sizeof(int);   
			
				    shellSort(arry, length);   
			
				    for (int i = 0; i < length; i++) {   
			
				        cout << arry[i] << " ";   
			
				    }   
			
				}  
			
				从上面可以看出希尔排序比直接插入排序相对复杂，但是如果排序思路清晰的话，该过程实现起来不是太难。如果感兴趣可以画出图解，比较直观。
			
				文章只是简单的介绍实现算法过程，由于本人水平有限，没有详细的分析上面两种种算法的O(f(n))。

ITPub博客

插入排序

最新文章