数据结构之插入排序

基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

插入排序是最简单的排序算法,插入排序最差的复杂度是O(n^2)效率比较低适合少量数据进行排序,但是实现起来比较简单。在一组无序元素中选取第二位插入排序的key值,并用key值与其前面临近的元素做比较,如果大于key值就将其值后移一下,继续上key值与前面的做比较并重复移动位置。如果key前面的值都小于key就将key值后面的元素值赋值给key重复上述动作。(其根本就是在一个最小的有序序列中不断的插入数据且使其保持有序)

算法步骤

1).从第一个元素开始,该元素可以认为已经被排序
2).取出下一个元素,在已经排序的元素序列中从后向前扫描
3).如果该元素(已排序)大于新元素,将该元素移到下一个位置
4).重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5).将新元素插入到该位置后
6).重复步骤2~5

算法实现(java):

public class InsertSort {
    public static void main(String[] args) {
        int[] a={5,2,9,61};
        insertSort(a);
        for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }
    public static void insertSort(int[] a){
        int i,j,key;
        for(j=1;j<a.length;j++){
            key=a[j]; //选第二个数为key,与前一个数比较
            i=j-1;
            while(i>=0 && a[i]>key){
                a[i+1]=a[i];
                i--;
            }
            a[i+1]=key;
        }
    }
}

算法分析:

时间复杂度:

在最好情况下,即要排序的数组本身就是有序的,则其时间复杂度为Θ(n);
在最坏的情况下,其时间复杂度为Θ(n2)。

空间复杂度:

很明显,其空间复杂度为Θ(1)。

稳定性:

冒泡排序是稳定的


  转载请注明: Hi 高虎 数据结构之插入排序

 上一篇
数据结构之选择排序 数据结构之选择排序
基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。 选择排序(Selection sort)也是一种简单直观的排序算法。 选择排
下一篇 
数据结构之冒泡排序 数据结构之冒泡排序
冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来
  目录