插入排序和归并排序(渐进运行时间对比)

1、插入排序

假定有一个数组array = [a1,a2,a3,a4,a5....an];

使用插入排序代码如下(手敲代码,有可能无法运行,但是排序思想肯定是正确的)：

//第一个循环时间耗费c1*array.length
for(int i=1;i<array.length;i++){
     var temp =array[i];
     int j=i-1;
     //第二个循环时间耗费c2*array.length
     while(j>=0&&array[j]>temp){
           array[j+1]=array[j];
           j=j-1;
     }
     array[j+1]=temp;
}

所以插入排序的运行时间为c1*array.length *c2*array.length 若 array.length 是n的话 对于n平方这个数，c1.c2常量可忽略。所以插入排序的运行时间记作θ(n²)

2、归并排序

假定有一个数组array = [a1,a2,a3,a4,a5....an];

public void start(int[] array,int left,int right){
   if(left<right){
       int middle =(left+right)/2;
       start(array,0,middle-1);
       start(array,middle+1,right);
       merge(array,left,middle,right);
    }
}
public void merge(int []a,int left,int middle,int right){
        int[] tempArray = new int[a.length];
        int rightstart = middle+1;
        int temp = left;
        int third = left;
        while (left<=middle&&rightstart<right){
            //一个一个往新的数组里边放值，遍历被分开的两个数组；
            //比较两个小数组相应下标位置的数字大小，小的先放进新数组；
            if(a[left]<=a[rightstart]){
                //比较左边第一个和右边第一个，然后把小的那一个放进到新数组；再将下标往后移动一位，继续比较；
                tempArray[third++] = a[left++];
            }else{
                tempArray[third++] = a[rightstart++];
            }
        }
        //如果左边还有数据需要拷贝，把左边数组剩下的拷贝到新数组；
        while (left<=middle){
            tempArray[third++] = a[left++];
        }
        //如果右边还有数据需要拷贝，就把右边数组剩下的拷贝到新数组；
        while (rightstart<=right){
            tempArray[third++] = a[rightstart++];
        }
        while (temp<=right){
            a[temp] = tempArray[temp++];
        }
}

归并排序的运行时间需要借助递归树，所以这里直接列出结果为θ(nlgn)

所以归并排序随着n的增长，其运行时间是大大小于插入排序的。