插入排序

采用的是以“玩桥牌者”的方法为基础的。即在考察记录Ri之前，设以前的所有记录R1, R2,…., Ri-1已排好序，然后将Ri插入到已排好序的诸记录的适当位置。

最基本的插入排序是直接插入排序(Straight Insertion Sort)。

1.直接插入排序

1.1 排序思想

将待排序的记录Ri，插入到已排好序的记录表R1, R2,…., Ri-1中，得到一个新的、记录数增加1的有序表。直到所有的记录都插入完为止。

设待排序的记录顺序存放在数组R[1…n]中，在排序的某一时刻，将记录序列分成两部分：

◆R[1…i-1]：已排好序的有序部分；

◆R[i…n]：未排好序的无序部分。

显然，在刚开始排序时，R[1]是已经排好序的。

1.2 举例

1.3 实现代码:

#include 
  
   
#include 
   
     #define SIZE 10 void InsertionSort(int *a,int len) { int i,j,t,h; for (i=0; i
    
     =0 && t
     
      
 运行结果:
       
      
  
       
  
      
  
      2. 希尔排序 
       
      
 <  http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ICAgICAgICDPo7b7xcXQ8ihTaGVsbCBTb3J0o6zT1rPGy/XQodT2wb+3qCnKx9K71ta31tfpsuXI68XF0PK3vbeooaM8L3A+CjxwPjIuMSDFxdDyy7zP6zwvcD4KPHA+PGJyPgo8L3A+CjxwPiAgICAgICAgotkgIM/IyKHSu7j21f3V+8r9ZDEoZDE8binX986qtdrSu7j21PbBv6OsvavIq7K/brj2vMfCvLfWs8lkMdfpo6yw0cv509DP4Lj0ZDG1xLzHwry3xdTa0rvX6dbQo6y8tLbU09rDv7j2ayhrPTEsMiwgIKGtZDEpo6xSW2tdLFJbZDEmIzQzO2tdLFJbMmQxJiM0MztrXSAsoa231tTazazSu9fp1tCjrNTauPfX6cTavfjQ0NaxvdOy5cjrxcXQ8qGj1eLR+dK7tM631tfpus3FxdDyuf2zzLPGzqrSu8zLz6O2+8XF0PKjuzwvcD4KPHA+ICAgICAgICCi2iAgyKHQwrXE1PbBv2QyPGQxo6zW2Li0otm1xLfW1+m6zcXF0PKy2df3o7vWsdbBy/nIobXE1PbBv2RpPTHOqta5o6y8tMv509C8x8K8t8W9+NK7uPbX6dbQxcXQ8s6q1rmhozwvcD4KPGJyPgoyLjIgvtnA/Qo8cD48YnI+CjwvcD4KPHA+PGltZyBzcmM9"https://www.cppentry.com/upload_files/article/49/1_bcsxi__.jpg" alt="\">
  
      
  
      2.3 实现代码: 
      
      #include 
       
        
#include 
        
          #define SIZE 10 void ShellSort(int *a,int len) { int i,j,h; int r,temp; int x = 0; for (r = len/2; r>=1; r/=2) { for (i = r; i
         
          =0 && temp < a[j]) { a[j+r] = a[j]; j-=r; } a[j+r] = temp; } x++; printf("第%d步行排序结果:",x); for (h = 0; h < len; h++) { printf(" %d",a[h]); } printf("\n"); } } int main(int argc, const char * argv[]) { int shuzu[SIZE],i; srand(time(NULL)); for (i=0; i
          
           
 运行结果:
            
           
  
            
  
           
  
            参考书籍:《C/C++常用算法手册》 《数据结构-清华大学严蔚敏》

c/c++常用算法(11) -- 基本排序算法(插入排序)

插入排序

1.直接插入排序

2. 希尔排序