说起插入排序,其实它的工作原理十分简单,举例来说一下,按照从小到大顺序排列下面的一组数:
9 5 7 3 4
从第二个数起,把它之后的部分看成是未排列的部分,第一个元素是已排序的部分,然后依次把未排序的部分的第一个元素取出,插入到已排好的部分的正确位置,于是已排好部分的元素个数加一,未排好部分元素个数减一。一直到未排好部分元素的个数为零时结束。于是上述的例子的排序过程如下:
9 5 7 3 4
5 9 7 3 4
5 7 9 3 4
3 5 7 9 4
3 4 5 7 9
在一些传统的教科书里面中一般这样来作插入工作:如果要把X[i]从X[0]插入到X[i-1]这一个已经排好的段落之中,令X[i]与X[i-1],X[i-2],...,X[1],X[0]相比较,如果X[j]>=X[i](0<=j<=i-1),就把X[j]向后移一位,直到X[j]小于X[i],X[i]就放在X[j+1]处。C语言的代码如下:
- void sort(int input[], int n)
- {
- int current;
- int x;
- int i;
- for(current=1; current
- {
- x = input[current];
- i = current - 1;
- while(x=0)
- {
- input[i+1] = input[i];
- i--;
- }
- input[i+1] = x;
- }
- }
在最坏的情况下,每一个X[i]都比较i次,也就是于每一个X[i-1],X[i-2],...,X[1],X[0]都比较过,然后才找到正确的位置,于是总比较次数是:1+2+3+...+(n-1)=n(n-1)/2,也就是说这是个O(n^2)的算法。在平均情况下,如果用数学推倒还是与n^2成正比的,所以它的速度是很慢的,但是这是可以加快的。但是需要解决两个问题:
第一. 如何把数据插到已排好的一串数据中
第二. 如何加快数据移动的速度
对于第一个问题,我们可以用到二分查找法(Binary Search),其实在一组已经排好的数据中找数据,或者是找位置,如果不用很特殊的数据结构,那么二分查找法(Binary Search)就一定可以用的上。通过数学推倒可以得出通过二分查找法(Binary Search)后比较次数与nlogn成正比的,是小于n^2的。
那么第一个问题解决了,对于第二个问题,我们可以用到<string.h></string.h>的函数:
void*memmove(void*dest,const void*src,int count);
这表示从src指出的地方起,移动count个char到dest所指出的地方去,一般而言,好的编译程序的链接库多半会用汇编语言来写这个函数,而不会用C写,因此效率会比高级语言好,更重要的是,很多机器硬件都有一个移动一个区域的(block move)指令,因此就更快了。所以可以把X[j+1]的地址给src,把X[j+2]的地址给dest,把要移动的数组个数给count,于是使用memmove()一次就可以完成移动,效率是相当高的。C代码如下:
- #include <string.h></string.h>
- #include <stdio.h></stdio.h>
- #include <stdlib.h></stdlib.h>
- #define SIZE sizeof(int)/sizeof(char)
-
- void sort(int input[], int n)
- {
- int current, pos;
- int low, high, mid;
- int x;
- for (current = 1; current < n; current++)
- {
- x = input[current];
- pos = -1;
- if (x < input[0])
- pos = 0;
- else if (x <= input[current-1])
- {
- low = 0;
- high = current - 1;
- while (high - low > 1)
- {
- mid = (low + high) / 2;
- if (x >= input[mid])
- ow = mid;
- else
- high = mid;
- }
- pos = low + 1;
- }
- if (pos >= 0)
- {
- memmove((void *) &input[pos+1], (void *) &input[pos],
- SIZE*(current-pos));
- input[pos] = x;
- }
- }
- }
好了说了大半天,终于把我当时学习数据结构时的插入排序法改进的还算完美,很可惜当时老师没有鼓励我们改进书上的算法,直到今天我才回头来重新研究这个算法,也许我曾经太相信大学的教育,相信老师,可是慢慢发现自己很失望,但失去的不会再回来,“不要为洒掉的牛奶而哭泣”。每天靠自己的努力来充实生活吧。对了,最后还要补充一下,插入排序具有稳定性的......
分享到:
相关推荐
插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序...
**插入排序**是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。这种算法对大数据量的处理效率较低,但对于小规模数据或者部分有序的...
插入排序是一种基础且直观的排序算法,它的工作原理可以类比于整理扑克牌。在实际应用中,插入排序对于小规模数据或者部分有序的数据表现优秀,但对于大规模无序数据,其效率相对较低。以下是关于插入排序的详细知识...
本主题将详细探讨四种常见的排序算法:选择排序、插入排序、快速排序以及冒泡排序,它们都是用C语言实现的。以下是这些排序算法的详细解析: 1. **选择排序(Selection Sort)** - 选择排序是一种简单直观的排序...
交换排序 选择排序 冒泡排序 插入排序
本资源包含三个经典的排序算法的源代码:插入排序、选择排序和冒泡排序,这些都是初级到中级程序员常学习和使用的算法。下面将详细介绍这三个排序算法的工作原理、特点以及代码实现。 1. **插入排序(Insertion ...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
Java排序算法 - 插入排序 插入排序(Insertion Sort)是一种简单的排序算法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 1 的有序表。该算法的实现非常简单,但其时间复杂度...
直接插入排序是一种基础且简单的排序算法,它的工作原理可以形象地比喻为扑克牌的洗牌过程。在实际应用中,虽然对于大规模数据的排序效率不如更高级的算法,如快速排序、归并排序等,但它的实现简单,适合小规模或...
### C经典算法之Shell排序法 - 改良的插入排序 #### 描述 在计算机科学领域,排序算法一直是研究的重点之一。插入排序是一种简单的排序方法,其基本思想是从待排序序列中依次取出元素与已排序的部分进行比较并插入...
插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从序列中间插入一个元素的复杂度为O(n)。 #### 实现细节 在Java代码中,`insertSort`方法通过两层循环实现:外层循环遍历每个...
该资源提供了Java中实现插入排序的全面指南。文档中涵盖了插入排序的基本概念,包括如何对数组进行排序以及如何在Java中实现插入排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现插入排序,包括详细的...
**插入排序(Insertion Sort)**是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
理解插入排序算法-讲解
直接插入排序是一种基础且常用的排序算法,它的工作原理可以直观地理解为手动整理扑克牌的过程。在本篇文章中,我们将深入探讨直接插入排序的细节,包括它的基本思想、步骤、时间复杂度以及适用场景。 一、基本思想...
排序-按键精灵-冒泡排序
2路插入排序是对传统插入排序的改进,将待插入元素分为较小和较大两部分,分别处理,降低了元素交换的频率。它在处理部分有序数据时性能提升,但总体时间复杂度仍为O(n^2)。 8. 树形选择排序 (Tree Selection Sort)...
《插入排序与右连接查询》 插入排序是一种基础但实用的排序算法,广泛应用于计算机科学领域,尤其是在数据结构和算法的学习中。它的工作原理可以形象地比喻为将一个乱序的数组逐步“插入”到已排序的部分,最终形成...