首页 > 代码库 > 排序算法 -- 插入

排序算法 -- 插入

排序算法 -- 目录

设有一组关键字{K1, K2,…, Kn};排序开始就认为 K1 是一个有序序列;让 K2 插入上述表长为 1 的有序序列,使之成为一个表长为 2 的有序序列;然后让 K3 插入上述表长为 2 的有序序列,使之成为一个表长为 3 的有序序列;依次类推,最后让 Kn 插入上述表长为 n-1 的有序序列,得一个表长为 n 的有序序列。

具体算法描述如下:

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

如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序

二分查找法,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

  Class : 

package limeMianShi;

import java.util.Arrays;

/**
 * 设有一组关键字{K1, K2,…, Kn};
 * 
 * 排序开始就认为 K1 是一个有序序列;让 K2 插入上述表长为 1 的有序序列,使之成为一个表长为 2的有序序列;
 * 
 * 然后让 K3 插入上述表长为 2 的有序序列,使之成为一个表长为 3 的有序序列;
 * 
 * 依次类推,最后让 Kn 插入上述表长为 n-1的有序序列,得一个表长为 n 的有序序列。
 * 
 * 具体算法描述如下:
 * 
 * 1.从第一个元素开始,该元素可以认为已经被排序
 * 
 * 2.取出下一个元素,在已经排序的元素序列中从后向前扫描
 * 
 * 3.如果该元素(已排序)大于新元素,将该元素移到下一位置
 * 
 * 4.重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
 * 
 * 5.将新元素插入到该位置后
 * 
 * 6.重复步骤 2~5
 * 
 * @author lime
 *
 */
public class Insertion_Sort {

    public static void main(String[] args) {
        int[] insertion = new int[10];
        for (int i = 0; i < insertion.length; i++) {
            insertion[i] = (int) (Math.random() * 100);
        }
        System.out.println(Arrays.toString(insertion) + " 原始数据");
        // BaseDo(insertion);
        minusTimesDo(insertion);
        System.out.println(Arrays.toString(insertion) + " 序列数据");
    }

    private static void minusTimesDo(int[] insertion) {
        int times = insertion.length;
        for (int i = 1; i < times; i++) {
            int temp = insertion[i];
            for (int j = i; j >= 0; j--) {
                System.out.println(Arrays.toString(insertion) + " i = " + i + " j = " + j);
                if(j == 0){
                    insertion[j] = temp;
                    break;
                }
                if (insertion[j - 1] > temp) {
                    insertion[j] = insertion[j - 1];
                } else {
                    insertion[j] = temp;
                    break;
                }
            }
            System.out.println("---");
        }
    }

    private static void BaseDo(int[] insertion) {
        int times = insertion.length;
        for (int i = 1; i < times; i++) {
            for (int j = i; j > 0; j--) {
                System.out.println(Arrays.toString(insertion) + " i = " + i + " j = " + j);
                if (insertion[j - 1] > insertion[j]) {
                    ArrayUtil.swap(insertion, j - 1, j);
                } else {
                    break;
                }
            }
            System.out.println("---");
        }
    }
}

啦啦啦

排序算法 -- 插入