1, 介绍.
直接插入排序是一种简单的插入排序法, 其基本思想是: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中, 直到所有的记录插入完为止, 得到一个新的有序序列. 例如, 已知待排序的一组记录是: 60,71,49,11,24,3,66. 假设在排序过程中, 前 3 个记录已按关键码值递增的次序重新排列, 构成一个有序序列: 49,60,71. 将待排序记录中的第 4 个记录 (即 11) 插入上述有序序列, 以得到一个新的含 4 个记录的有序序列. 首先, 应找到 11 的插入位置, 再进行插入. 可以将 11 放入数组的第一个单元 r[0]中, 这个单元称为监视哨, 然后从 71 起从右到左查找, 11 小于 71, 将 71 右移一个位置, 11 小于 60, 又将 60 右移一个位置, 11 小于 49, 又再将 49 右移一个位置, 这时再将 11 与 r[0]的值比较, 11≥r[0], 它的插入位置就是 r[1]. 假设 11 大于第一个值 r[1]. 它的插入位置应该在 r[1]和 r[2]之间, 由于 60 已经右移了, 留出来的位置正好留给 11. 后面的记录依照同样的方法逐个插入到该有序序列中. 若记录数 n, 续进行 n-1 趟排序, 才能完成.
直接插入排序是稳定排序, 不需要额外内存, 空间复杂度 O(1). 时间复杂度, 最佳情况: O(n) 最差情况: O(n^2) 平均情况: O(n^2).
2, 步骤.
(1)设置监视哨 r[0], 将待插入记录的值赋值给 r[0];
(2)设置开始查找的位置 j;
(3)在数组中进行搜索, 搜索中将第 j 个记录后移, 直至 r[0].key≥r[j].key 为止;
(4)将 r[0]插入 r[j+1]的位置上.
3, 代码.
- publicstaticvoidmain(String[] args){
- System.out.println("------ 开始 ------");
- // 生成生成两份一模一样的随机数组, 其中一组用系统自带的方法进行排序, 到时候进行验证.
- final int number = 100000;
- int[] sortArray = new int[number];
- int[] sortArrayCopy = new int[number];
- for (int i = 0; i <sortArray.length; i++) {
- sortArray[i] = (int) (Math.random() * number);
- }
- System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);// 数组复制
- Arrays.sort(sortArrayCopy);
- // 开始排序
- long startTime = System.currentTimeMillis();
- directInsertSort(sortArray);// 直接插入排序
- System.out.println("花费时间:" + (System.currentTimeMillis() - startTime));
- // 跟系统排序之后数组进行比较, 查看是否排序成功.
- if (Arrays.equals(sortArray, sortArrayCopy)) {
- System.out.println("排序成功");
- } else {
- System.out.println("排序失败");
- }
- System.out.println("------ 结束 ------");
- }
- // 直接插入排序 最佳情况: T(n) = O(n) 最坏情况: T(n) = O(n2) 平均情况: T(n) = O(n2)
- privatestaticvoiddirectInsertSort(int[] array){
- for (int i = 1; i < array.length; i++) {
- //n-1 轮 第一个无需排序
- int curIndex = i;
- while (curIndex> 0) {
- if (array[curIndex]> array[curIndex - 1]) {
- break;
- }
- int flag = array[curIndex];
- array[curIndex] = array[curIndex - 1];
- array[curIndex - 1] = flag;
- curIndex--;
- }
- }
- }
4, 结果.
二, 折半插入排序.
1, 介绍.
将直接插入排序中寻找 A[i]的插入位置的方法改为采用折半比较, 即可得到折半插入排序算法. 在处理 A[i]时, A[0]......A[i-1]已经按关键码值排好序. 所谓折半比较, 就是在插入 A[i]时, 取 A[i-1/2]的关键码值与 A[i]的关键码值进行比较, 如果 A[i]的关键码值小于 A[i-1/2]的关键码值, 则说明 A[i]只能插入 A[0]到 A[i-1/2]之间, 故可以在 A[0]到 A[i-1/2-1]之间继续使用折半比较; 否则只能插入 A[i-1/2]到 A[i-1]之间, 故可以在 A[i-1/2+1]到 A[i-1]之间继续使用折半比较. 如此担负, 直到最后能够确定插入的位置为止. 一般在 A[k]和 A[r]之间采用折半, 其中间结点为 A[k+r/2], 经过一次比较即可排除一半记录, 把可能插入的区间减小了一半, 故称为折半. 执行折半插入排序的前提是文件记录必须按顺序存储.
折半插入排序是稳定排序, 不需要额外内存, 空间复杂度 O(1). 时间复杂度, 最佳情况: O(n^2) 最差情况: O(n^2) 平均情况: O(n^2).
2, 步骤.
跟直接插入排序的步骤相似, 只不过查找插入点的方法不一样. 直接插入排序是从有序区的最后一个数依次向前找, 而折半插入排序是通过折半的方式进行查找.
(1)计算 0 ~ i-1 的中间点, 用 i 索引处的元素与中间值进行比较, 如果 i 索引处的元素大, 说明要插入的这个元素应该在中间值和刚加入 i 索引之间, 反之, 就是在刚开始的位置 到中间值的位置, 这样很简单的完成了折半;
(2)在相应的半个范围里面找插入的位置时, 不断的用 (1) 步骤缩小范围, 不停的折半, 范围依次缩小为 1/2 1/4 1/8 ....... 快速的确定出第 i 个元素要插在什么地方;
(3)确定位置之后, 将整个序列后移, 并将元素插入到相应位置.
3, 代码.
- publicstaticvoidmain(String[] args){
- System.out.println("------ 开始 ------");
- // 生成生成两份一模一样的随机数组, 其中一组用系统自带的方法进行排序, 到时候进行验证.
- final int number = 100000;
- int[] sortArray = new int[number];
- int[] sortArrayCopy = new int[number];
- for (int i = 0; i <sortArray.length; i++) {
- sortArray[i] = (int) (Math.random() * number);
- }
- System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);// 数组复制
- Arrays.sort(sortArrayCopy);
- // 开始排序
- long startTime = System.currentTimeMillis();
- halveInsertSort(sortArray);// 折半插入排序
- System.out.println("花费时间:" + (System.currentTimeMillis() - startTime));
- // 跟系统排序之后数组进行比较, 查看是否排序成功.
- if (Arrays.equals(sortArray, sortArrayCopy)) {
- System.out.println("排序成功");
- } else {
- System.out.println("排序失败");
- }
- System.out.println("------ 结束 ------");
- }
- // 折半插入排序 最佳情况: T(n) = O(n) 最坏情况: T(n) = O(n2) 平均情况: T(n) = O(n2)
- privatestaticvoidhalveInsertSort(int[] array){
- int flag;
- int low, middle, high;
- for (int i = 1; i < array.length; i++) {
- //n-1 轮
- flag = array[i];
- low = 0;
- high = i - 1;
- while (low <= high) {
- // 最后的情况就是 low==high==middle 的判断
- middle = (low + high) / 2;
- if (array[i]> array[middle]) {
- low = middle + 1;
- } else {
- high = middle - 1;
- }
- }
- for (int j = i; j> high + 1; j--) {
- array[j] = array[j - 1];
- }
- array[high + 1] = flag;
- }
- }
4, 结果.
三, 希尔排序.
1, 介绍.
希尔排序 (Shell's Sort) 是插入排序的一种又称" 缩小增量排序 "(Diminishing Increment Sort), 是直接插入排序算法的一种更高效的改进版本. 希尔排序是非稳定排序算法. 该方法因 D.L.Shell 于 1959 年提出而得名. 希尔排序是把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序; 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至 1 时, 整个文件恰被分成一组, 算法便终止.
希尔排序是不稳定排序, 不需要额外内存, 空间复杂度 O(1). 时间复杂度, 最佳情况: O(nlog^2n) 最差情况: O(nlog^2n) 平均情况: O(nlogn).
2, 步骤.
我们来看下希尔排序的基本步骤, 在此我们选择增量 gap=length/2, 缩小增量继续以 gap = gap/2 的方式, 这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2...1}, 称为增量序列. 希尔排序的增量序列的选择与证明是个数学难题, 我们选择的这个增量序列是比较常用的, 也是希尔建议的增量, 称为希尔增量, 但其实这个增量序列不是最优的. 此处我们做示例使用希尔增量. 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序, 具体算法描述: 选择一个增量序列 t1,t2,...,tk, 其中 ti>tj,tk=1; 按增量序列个数 k, 对序列进行 k 趟排序; 每趟排序, 根据对应的增量 ti, 将待排序列分割成若干长度为 m 的子序列, 分别对各子表进行直接插入排序. 仅增量因子为 1 时, 整个序列作为一个表来处理, 表长度即为整个序列的长度.
3, 代码.
- publicstaticvoidmain(String[] args){
- System.out.println("------ 开始 ------");
- // 生成生成两份一模一样的随机数组, 其中一组用系统自带的方法进行排序, 到时候进行验证.
- final int number = 100000;
- int[] sortArray = new int[number];
- int[] sortArrayCopy = new int[number];
- for (int i = 0; i <sortArray.length; i++) {
- sortArray[i] = (int) (Math.random() * number);
- }
- System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);// 数组复制
- Arrays.sort(sortArrayCopy);
- // 开始排序
- long startTime = System.currentTimeMillis();
- shellInsertSort(sortArray);// 希尔插入排序
- System.out.println("花费时间:" + (System.currentTimeMillis() - startTime));
- // 跟系统排序之后数组进行比较, 查看是否排序成功.
- if (Arrays.equals(sortArray, sortArrayCopy)) {
- System.out.println("排序成功");
- } else {
- System.out.println("排序失败");
- }
- System.out.println("------ 结束 ------");
- }
- // 希尔插入排序 最佳情况: T(n) = O(nlog2 n) 最坏情况: T(n) = O(nlog2 n) 平均情况: T(n) =O(nlog2n)
- privatestaticvoidshellInsertSort(int[] array){
- int groups = array.length / 2;// 增量, 一共的组数
- while (groups> 0) {
- // 将 groups 看作 1, 就会跟直接插入排序的算法一模一样
- for (int i = groups; i <array.length; i++) {
- //n-1 轮 第一个无需排序
- int curIndex = i;
- while (curIndex> groups - 1) {
- if (array[curIndex]> array[curIndex - groups]) {
- break;
- }
- int flag = array[curIndex];
- array[curIndex] = array[curIndex - groups];
- array[curIndex - groups] = flag;
- curIndex -= groups;
- }
- }
- groups /= 2;
- }
- }
4, 结果.
来源: http://www.bubuko.com/infodetail-3257897.html