引言:直接插入排序作为一个日常生活中经常使用到的排序算法(例如打扑克时,整理手牌),虽然其算法效率并不高(最好的情况下O(N),本身有序的情况下,其他情况O(N^2)),但是为我们理解希尔排序有着重要作用,本篇文章用来介绍和使用插入排序。
先用图来理解下算法核心吧:
这就是基本思路,下面是代码实现
- void insertion_sort(int* arry, int size) {
- assert(arry);
- for (int i = 0; i < size - 1; i++) {
- int end=i;
- int tem = arry[end + 1];
- while (end >= 0) {
- if (tem < arry[end]) {
- arry[end + 1] = arry[end];
- end--;
- }
- else {
- break;
- }
- }
- arry[end + 1] = tem;
- }
- }
测试代码:
- void Printf(int* arry, int size) {
- for (int i = 0; i < size; i++) {
- printf("%d ", arry[i]);
- }
- printf("\n");
- return;
- }
- void test_insertion_sort(int *arry,int size) {
- Printf(arry, size);
- insertion_sort(arry, size);
- Printf(arry, size);
- }
- int main() {
- int arry[] = { 2,3,1,6,21,78,11,36,13,7,9 };
- int len = sizeof(arry) / sizeof(arry[0]);
- test_insertion_sort(arry, len);
- return 0;
- }