插入排序的算法分析

原创
2014/08/05 17:23
阅读数 245

插入排序的算法分析


插入排序:对于少量元素的排序,他是一个有效的算法。

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序

  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描

  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置

  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

  5. 将新元素插入到该位置后

  6. 重复步骤2~5


插入排序使用C实现:

//插入排序
#include<stdio.h>
int main(){
    int array[8]={1,9,76,21,6,13,24,35};
    int j;

    /*
    下标j指出正被插入到手中的当前牌。
    在for循环(循环变量为j)每次迭代的开始
    array[1..j-1]为当前已经排好序的牌,剩余的子数组array[j+1..n]对应于仍在桌子上的牌堆
    */

    for(j=2;j<8;j++){
        int key = array[j];
        int i = j-1;
        while(i>0 && array[i]>key){
            array[i+1] = array[i];
            i=i-1;
        }
        array[i+1] = key;
    }

    int n;
    for(n = 0;n<8;n++){
        printf("%d\n",array[n]);
    }
}

示意图:


插入排序使用Java泛型实现

package aop;

public class InsertSort {

    public static <T extends Comparable<? super T>> void sort(T[] array) {
        for (int j = 2; j < array.length; j++) {
            //insert array[j] into the sorted sequence
            T key = array[j];
            int i = j - 1;
            while (i > 0 && array[i].compareTo(key) > 0) {
                array[j] = array[i];
                i--;
            }
            array[i + 1] = key;
        }
    }

    public static void main(String args[]) {
        String[] arrs = {"asd", "dsa", "cse", "sa", "eeww", "oiuu"};
        System.out.println(arrs.length);
        InsertSort.sort(arrs);
        for (String s : arrs) {
            System.out.println(s);
        }
    }
}


插入排序算法的分析

输入规模:待排序数组的规模为n

运行时间:执行的基本操作数或步数

最坏情况运行时间:对于规模为n的任何输入,算法的最长运行时间

时间复杂度:如果插入排序的输入规模为n,则时间复杂度为Tn = Θ(n^2)


算法的渐近时间复杂度

定义一:Θ(g(n))={f(n) | 如果存在正常数c1、c2和正整数n0,使得当n>=n0时,0<c1g(n)<=f(n)<=c2g(n)恒成立}

定义二:Ο(g(n))={f(n) | 如果存在正常数c和正整数n0,使得当n>=n0时,0<=f(n)<=cg(n)恒成立}

定义三:Ω(g(n))={f(n) | 如果存在正常数c和正整数n0,使得当n>=n0时,0<=cg(n)<=f(n)恒成立}


定义一:Θ记号渐近地给出了一个函数的上界和下界。

定义二:O记号只给出了一个渐近上界。

定义三:Ω记号提供了渐近下界。


====END====




展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部