插入排序及希尔排序

 

插入排序：

字段定义：

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

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

算法描述：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤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(N²)，所以插入排序自然也是。

 

希尔排序：

字段定义：

增量序列：序列h1,h2,h3……,hn,满足h1=1，1<h(n)<h(n+1)就可以用来作为希尔排序的增量序列，但存在某些递增的序列，它们可以对该算法的运行时间给出重要的改进。

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

算法描述：

1. 定义增量数列
2. 根据增量数值对数据进行分块
3. 比较a[i]和a[i+gap]的大小，并排序。
4. 重复步骤3，直到完成增量数值为gap从i=gap到a.length的排序
5. 重复步骤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：1.使用Hibbard的增量序列（1,3,7，…..，2k -1）实现希尔排序最坏运行时间为Θ(N3/2)。

          2.插入排序的核心是将一个数插入到一个已经有序的序列里。

效率对比：

 

Cpu：msm8930（dual core 1.5G）