插入排序及希尔排序

插入排序：

字段定义：

排序：数据分为有序和无序，使数据从无序到有序这一过程为排序。用的策略称为排序算法。

时间复杂度：算法不存在特定的是时间单位，用O表示一个算法的上界（最坏情况）。

算法描述：

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



编程实现（java）：

public void Insertsort(int []a){
        int j = 0;
        for (int i = 1; i < a.length; i++){
            int temp = a[i];
            for (j = i; j > 0 && a[j-1] > temp; j--)
                a[j] = a[j-1];
            a[j] = temp;
        }
    }




Tips：一般认为通过交换相邻元素进行排序的算法时间复杂度都是O(N2)，所以插入排序自然也是。

希尔排序：

字段定义：

增量序列：序列h1,h2,h3……,hn,满足h1=1，1

算法背景：希尔排序的名称来源于它的发明者Donald Shell，这个算法是第一批突破排序时间复杂度O(N2)的杰出代表。它极大改善了常规插入排序的效率问题，因为常规插入排序每次只能将数据移动一位。

算法描述：

定义增量数列 根据增量数值对数据进行分块 比较a[i]和a[i+gap]的大小，并排序。 重复步骤3，直到完成增量数值为gap从i=gap到a.length的排序 重复步骤3,4，直到完成所有增量数值的排序，当最后一步数值为1即为标准的插入排序。

举例说明：


编程实现（java）：

public void shellSort(int []a){
        int j = 0;
        for (int gap = a.length >> 1; gap > 0; gap = gap >> 1){
           
            for (int i = gap; i < a.length; i++){
                int temp = a[i];
                for (j = i; j >= gap && a[j-gap] > temp; j = j - gap)
                    a[j] = a[j-gap];
                a[j] = temp;
            }
        }
    }




Tips：使用Hibbard的增量序列（1,3,7，…..，2k -1）实现希尔排序最坏运行时间为Θ(N3/2)。

效率对比：



Cpu：msm8930（dual core 1.5G）