插入排序很简单，就像打扑克。手里有个牌4，再来一张牌5就本能的放到第一个牌的右边。如果来了个3就从右往左扫描，只要左边的比这个待插入数字大就交换。

插入排序是一种稳定的排序方法，时间复杂度O(n*n),空间复杂度O(1),最好的情况下时间复杂度为O(1).即本来就是一个有序或者相等的数组，则只需比较n-1次即可。下为源码，只需三行代码即可。

//============================================================================
// Name        : QuikSort.cpp
// Author      : YanZi
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include 
  
   
#include 
   
     using namespace std; void swap1(int a, int b); void printArray(int* in, int n); void quickSort1(int* x, int l, int r);//双边扫描，快速排序 void quickSort2(int x[], int l, int r);//单边扫描，快速排序 void swap2(int &a,int &b); //交换，在MinGW上必须采用此方法，swap1无效 #define N 8 //数组的长度 int main() { int* input = NULL; input = (int*)malloc(N * sizeof(int)); if(input == NULL){ cout<<"内存溢出"<
    
     = key){ j--; } if(i < j){ x[i++] = x[j]; } while(i < j && x[i] <= key){ i++; } if(i < j){ x[j--] = x[i]; } } cout<<"i = " <
      
        
      
 
      
 
      
 
       

        <script type="text/java script">BAIDU_CLB_fillSlot("771048");
       
 
      
 
      
 
       

        点击复制链接 与好友分享!
        回本站首页
       
 
       <script> 
		function copyToClipBoard(){ 
		var clipBoardContent=document.title + '\r\n' + document.location; 
		clipBoardContent+='\r\n'; 
		window.clipboardData.setData("Text",clipBoardContent); 
		alert("恭喜您！复制成功"); 
		} 
		 
       
 
        

         
         
         
         
         
         
         
        
 
        <script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];