算法—插入排序

插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 {displaystyle O(1)} {displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后

挪位，为最新元素提供插入空间。

如：int arr[10] = { 22,34,3,32,82,55,89,50,37,5 };

第一趟：arr[0]和arr[1]比较，因为arr[0]<arr[1]；故arr[0] = 22,arr[1] = 34;

第二趟：arr[1]和arr[2]比较，因为arr[1]>arr[2]； 故arr[1] = 3,arr[2] = 23;接着再拿arr[1]和arr[0]比较，因为arr[0]>arr[1]；故arr[0] = 3,arr[1] = 22;

这样子arr[0] arr[1] arr[2] 目前是排好了顺序为 3 22 34 .....

第三趟：arr[3]和arr[4]比较，因为arr[3]<arr[4]；故arr[3] = 32,arr[4] = 82不变.

.........

当进行到最后一趟：arr[8]和arr[9]比较，因为arr[8]>arr[9]；故arr[8] = 5,arr[9] = 37;arr[8]和arr[7]比较，因为arr[7]>arr[8]，故arr[7]和arr[8]对换。

最后就完成了排序。总的来说就是每进行一次排序，前面的顺序都是从小到大拍好的。若有不懂，请看下面的视频。

过程演示：

 1 #include <stdio.h>
 2 
 3 void insertion_sort(int arr[],int len){
 4      i,j,temp;
 5     for (i=1;i<len;i++){
 6             temp = arr[i];
 7             for (j=i;j>0 && arr[j-1]>temp;j--)
 8                     arr[j] = arr[j-1];
 9             arr[j] = temp;
10     }
11 }
12 
13 
14  main() {
15     int arr[] = { 22,34,1)">3,1)">32,1)">82,1)">55,1)">89,1)">50,1)">37,1)">5,1)">64,1)">35,1)">9,1)">70 };
16     int len = (int) sizeof(arr) / sizeof(*arr);
17      i;
18     insertion_sort(arr,len);
19   
20     for (i = 0; i < len; i++21         printf("%d ",arr[i]);
22     return 0;
23 }

?

如果实在是不理解，那么观看下面这个视频应该会有所理解了。这个视频还是挺有意思的，请认真看完，如果不行就加速看也行。第一次看不懂就多看几遍然后和代码联系上。

若有视频侵权，请联系本人。本人删除

?

（编辑：湘西站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!