C笔记 - 算法：插入排序

插入排序

1 - 插入排序（Insertion-Sort）是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对未排序数据在已排序序列中从后向前扫描，找到相应位置并插入（不明白的话就想想打扑克时如何整理的顺子，对，就是插入排序）

2 - 具体算法描述

① 从第一个元素开始，该元素可以认为已经被排序

② 取出下一个元素，在已经排序的元素序列中从后向前扫描

③ 如果该元素（已排序）大于新元素，将该元素移到下一位置

④ 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置

⑤ 将新元素插入到该位置后

⑥ 重复步骤 2 - 5，最终完成排序

3 - 代码示例 

 1     // 数组
 2     int array[] = {12,91,21,10,13,88,66};
 3     int length = sizeof(array)/sizeof(array[0]);
 4     
 5     // 记录前一个元素索引
 6     int preIndex = 0;
 7     // 记录当前需要排列的元素
 8     int currentNumber = 0;
 9     
10     // 外层控制轮数，共需 length - 1 次
11     // 从 1 开始，能姣好地记录数组的首个元素 array[0]
12     for (int i = 1; i < length; i ++) {
13        
14         preIndex = i - 1;
15         currentNumber = array[i];
16         
17         // 内层排序：如果前一个元素比需要排列的元素大，那么就把 currentNumber 不断的向前移动
18         for (; preIndex >= 0 && array[preIndex] > currentNumber; preIndex--) {
19             array[preIndex + 1] = array[preIndex];
20         }
21 
22         // 注意：插入的索引是 preIndex +1
23         array[preIndex + 1] = currentNumber;
24         
25         
26         printf("-------第 %d 轮排序------\n\n",i);
27         for (int i = 0; i < length -1; i ++) {
28             printf("%d  ",array[i]);
29         }
30         
31         if (length == 6) {
32             printf("\n\n");
33             return 1;
34         }
35         printf("\n\n");
36 
37     }

日志打印