排序算法篇(插入排序)_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 排序算法篇(插入排序)

排序算法篇(插入排序)

 2014/11/30 21:26:18  superpeng1988  程序员俱乐部  我要评论(0)
  • 摘要:会打扑克的人对于插入算法就很好了解啦,每次扎入一张牌我是会对它排序的。插入排序包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。属于稳定排序的一种(通俗地讲,就是两个相等的数不会交换位置)。一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:⒈从第一个元素开始,该元素可以认为已经被排序⒉取出下一个元素,在已经排序的元素序列中从前往后(从后向前)扫描⒊如果该元素(已排序)大于新元素,将该元素移到下一位置⒋重复步骤3
  • 标签:算法
会打扑克的人对于插入算法就很好了解啦,每次扎入一张牌我是会对它排序的。
插入排序包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。属于稳定排序的一种(通俗地讲,就是两个相等的数不会交换位置)。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
⒈ 从第一个元素开始,该元素可以认为已经被排序
⒉ 取出下一个元素,在已经排序的元素序列中从前往后(从后向前)扫描
⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置
⒋ 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序
Java实现代码如下:
从前向后查找的插入排序:
/********************************************************
*函数名称:InsertSort
*参数说明:dataArray 无序数组;
*说明:    插入排序
*********************************************************/ 
public void InsertSort(int[] dataArray) 

    for (int i = 1; i < dataArray.length; i++)    //从第2个数据开始插入 
    { 
        int j = 0; 
        while (j < i && dataArray[j] <= dataArray[i])    //寻找插入的位置 
            j++; 
        if (j < i)    //i位置之前,有比dataArray[i]大的数,则进行挪动和插入 
        { 
            int k = i; 
            int temp = dataArray[i]; 
            while (k > j)    //挪动位置 
            { 
                dataArray[k] = dataArray[k-1]; 
                k--; 
            } 
           dataArray[k] = temp;    //插入 
        } 
    } 
}

从后向前查找的插入排序:
    /********************************************************
    *函数名称:InsertSort
    *参数说明:dataArray 无序数组
    *说明:    插入排序
    *********************************************************/ 
    void InsertSort(int[] dataArray) 
    { 
        for (int i = 1; i < dataArray.length; i++)    //从第2个数据开始插入 
        { 
            int j = i - 1; 
            int temp = dataArray[i];    //记录要插入的数据 
            while (j >= 0 && dataArray[j] > temp)    //从后向前,找到比其小的数的位置 
            { 
                dataArray[j+1] = dataArray[j];    //向后挪动 
                j--; 
            } 
     
            if (j != i - 1)    //存在比其小的数 
                dataArray[j+1] = temp; 
        } 
    } 
发表评论
用户名: 匿名