一个人至少拥有一个梦想,有一个理由去坚强

心若没有栖息的地方,到哪里都是在流浪

排序——插入排序

引言:排序算法是学习算法设计和分析的极好例子。下面介绍几种常见的排序方法其中一个。

插入排序

插入排序是重复地将新的元素插入到一个排好序的子线性表中,直到整个线性表排好序。

对线性表int[]  list = {2,9,5,4,8,1,6}进行排序

算法可描述如下:

for(int i = 1; i < list.length; i++){
   //将list[i]插入已排好序的子线性表中,这样list[0....i]也是排好序的
}

为了将list[i]插入list[0….i-1],需要将list[i]存储在一个临时变量currentElement中。如果list[i – 1] > currentElement,就将list[i – 1]移到list[i],如果list[i – 2]大于currentElement,就将list[i – 2]移到list[i – 1],依次类推,知道list[i – k] <= currentElement或者k > i。也就是用当前的元素和排好序的线性表的元素一个个进行比较,直到排好序的数列的第一个元素。

《排序——插入排序》

下面是演示将4插入到{2, 5, 9}中步骤:

《排序——插入排序》

程序如下:

public class InsertionSort {
    public static void main(String[] args) {
        int[] list = {2,9,5,4,8,1,6};
        int[] sortList = insertionSort(list);
        for (int i : sortList) {
            System.out.print(i + " ");
        }

    }
    public static int[] insertionSort(int[] list){
        for (int i = 1; i < list.length; i++) {
            int currentElement = list[i];
            int k;
            for (k = i - 1; k >= 0 && list[k] > currentElement; k--) {
                list[k + 1] = list[k];
            }
            list[k + 1] = currentElement;
        }
        return list;
    }
}

程序运行如下:

《排序——插入排序》

使用T(n)表示插入排序的复杂度,c表示诸如每次迭代中的赋值和额外的比较的操作总数,则

T(n) = (2 + c) + (2 * 2 + c) + … + (2 * (n – 1) + c)

= 2(1 + 2 + … + n-1) + c(n – 1)

= 2(n – 1)^n /2 + (n – c)

= n^2 – n + cn – c

= o(n^2)

因此插入排序的时间复杂度为O(n^2)。插入排序和选择排序具有相同的时间复杂度。

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注