图解插入排序算法

深入研究插入排序的实现
服务器君一共花费了341.438 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i],则L[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程,共需要(a),(b),(c)三次插入。

图 对4个元素进行插入排序

在下面的插入排序算法中,为了写程序方便我们可以引入一个哨兵元素L[0],它小于L[1..n]中任一记录。所以,我们设元素的类型ElementType中有一个常量-∞,它比可能出现的任何记录都小。如果常量-∞不好事先确定,就必须在决定L[i]是否向前移动之前检查当前位置是否为1,若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时,就将L[i]放入L[0]中,这样也可以保证在适当的时候结束第i遍处理。

下面考虑算法Insertion_Sort的复杂性。对于确定的i,内while循环的次数为O(i),所以整个循环体内执行了∑O(i)=O(∑i),其中i从2到n。即比较次数为O(n2)。如果输入序列是从大到小排列的,那么内while循环次数为i-1次,所以整个循环体执行了∑(i-1)=n(n-1)/2次。由此可知,最坏情况下,Insertion_Sort要比较Ω(n2)次。

如果元素类型是一个很大的纪录,则算法第5行要消耗大量的时间,因此有必要分析移动元素的次数。经过分析可知,平均情况下第5行要执行n(n-1)/4次,分析方法与冒泡排序的分析相同。

如果移动元素要消耗大量的时间,则可以用链表来实现线性表。

插入排序法是一个原地置换排序法,也是一个稳定排序法。插入法虽然在最坏情况下复杂性为θ(n2),但是对于小规模输入来说,插入排序法是一个快速的原地置换排序法。许多复杂的排序法,在规模较小的情况下,都使用插入排序法来进行排序,比如快速排序和桶排序。

下面是C语言实现的一个插入排序例子:

#include <stdio.h>
#include <stdlib.h>
void PrintHeap(const char* strMsg,int array[],int nLength);
void InsertionSort1(int *items, int count) 
void InsertionSort2(int a[],int size);
void PrintArray(const char* strMsg,int array[],int nLength);
int main(int argc, char *argv[])
{
  int data[13]={8,5,4,6,13,7,1,9,12,11,3,10,2};
  InsertionSort1(data,13);
  PrintArray("Insertion Sort:",data,13);
  
  system("PAUSE");    
  return 0;
}
/*
插入排序思路:
    将数组分成两个区域:已排序区域和未排序区域。首先假设数组的第一个元素处于已排序区域,
    第一个元素之后的所有元素都处于未排序区域。
    排序时用到两层循环,第一层循环用于从未排序区域中取出待排序元素,并逐步缩小未排序区域,
    第二层循环用于从已排序区域中寻找插入位置(即不断地从已排序区域中寻找比待排序元素大的元素,
    然后将较大的已排序区的元素后移,后移的最终结果是已排序区元素的最后一个元素占据
    待排序元素原来的位置,而已排序区中间空出一个位置),最后将待排序元素插入元素后移后留下的空位。 
*/
void InsertionSort1(int *items, int count)              
{                                                  
    int x, y;                             
    int c;                                        
                                                   
    for ( x=1; x<count; ++x )                      
    {                                              
        c = items[x];                              
        for ( y=x-1; (y>=0) && (c<items[y]); y-- ) 
            items[y+1] = items[y];                 
                                                   
        items[y+1] = c;                            
    }                                              
}
void InsertionSort2(int a[],int size)
{
     int i,j,v;
     //initially,the first item is considered to be sorted
     //i divides a into a sorted region,x<i,and unsorted one,x>=i
     for(i=1;i<size;i++)
     {
        //select the item at the beginning of the as yet unsorted section
        v=a[i];
        //work backwards through the array,finding where v should go
        j=i;
        //if this element is greater than v,move it up one
        while(a[j-1]>v)
        {
           a[j]=a[j-1];
           j--;
           if(j<=0) break;
        }
        //stopped when a[j-1]<=v,put v at position
        a[j]=v;
     } 
}
void PrintArray(const char* strMsg,int array[],int nLength)
{
     int i;
     printf("%s",strMsg);
     for(i=0;i<nLength;i++)
     {
        printf("%d ",array[i]);
     }
     printf("\n");
}

本文地址:http://www.nowamagic.net/librarys/veda/detail/440,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/440

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

现代魔法研究协会欢迎你

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《JavaScript高级程序设计(第2版)》 尼古拉斯·泽卡斯(Nicholas C.Zakas) (作者), 李松峰 (译者), 曹力 (译者)

《JavaScript高级程序设计(第2版)》在上一版基础上进行了大幅度更新和修订,融入了近几年来JavaScript应用发展的最新成果,几乎涵盖了所有需要理解的重要概念和最新的JavaScript应用成果。从颇具深度的JavaScript语言基础到作用域(链),从引用类型到面向对象编程,从极其灵活的匿名函数到闭包的内部机制,从浏览器对象模型(BOM)、文档对象模型(DOM)到基于事件的Web脚本设计,从XML(E4X)到Ajax及JSON,从高级前端开发技术到前沿的客户端存储,从最佳编程实践到即将成为现实的API,直至JavaScript未来的发展,全景式地展示了JavaScript高级程序设计的方方面面。

更多计算机宝库...