当前位置:首页 > 编程教程 > Java编程 > 简单插入排序(Insertion Sort)插入类排序法(Java实现)

简单插入排序(Insertion Sort)插入类排序法(Java实现)

2017-07-17 19:08:10[Java编程]点击数:作者:warmwine的博客来源: 网络
随机为您推荐的文章:几种简单的负载均衡算法及其Java代码实现

什么是负载均衡 负载均衡,英文名称为Load Balance,指由多台服务器以对称的方式组成一个服务器集合,每台服务器都具有等价的地位,都可以单独对外提供服务而无须其他服务器的辅

所谓插入排序,就是将无序序列中的各个元素插入到已经有序的线性表中。

在线性表中,只包含第一个元素的子表显然可以看作有序表。接下来,我们需要将第2个开始和以后的每一个元素插入到只包含第一个元素的子表中。我们假设将第j个元素进行插入,j-1之前的元素都已经有序。插入过程如下:

设temp = 第j个元素。从有序子表的最后一个元素(j-1)开始,依次向前(--)与temp进行比较,如果前者大于后者,将大于temp的元素都向后移动一个位置,直到不大于temp的元素位置。最后将temp插入到移出的空位上。这样线性表中的j长度就排序完毕了,同理进行下一个元素的插入排序。

*插入类排序法的效率与初始排序状态有关。
最坏情况下,简单插入排序需要比较n(n-1)/2次,最坏时间复杂度为O(n2)

简单插入排序(Insertion Sort)插入类排序法(Java实现)

public class SimpleInsertionSort {
    public static void main(String args[]){
        int arr[] = {10,5,6,7,1,2,4};
        simpleinsertsort(arr);
        for(int a : arr)
            System.out.print(a+",");
    }

    public static void simpleinsertsort(int arr[]){
        //从数组的第二个元素开始查找
        for(int i = 1 ; i < arr.length ; i++){
            int j;
            int temp = arr[i];
            //将元素与前一个元素进行比较,从后往前,将小的元素放在前面。
            for(j = i ; j > 0 && temp < arr[j-1] ; j--){ //注意比较条件的顺序。 用temp是因为,arr[i]在变化。
                arr[j] = arr[j-1];
            }
            arr[j] = temp; //将arr[i]按照顺序插入到j位置。
        }
    }

}
以上就是简单插入排序(Insertion Sort)插入类排序法(Java实现)的全文介绍,希望对您学习和使用java编程有所帮助.

这些内容可能对你也有帮助

更多Java编程可查看Java编程列表页。

TAGS: 简单   Insertion   Java