常见算法实例

摘要：这个版本和上一版对比很有趣，乍看上去多了嵌套了一个循环，可是大多情况却比第一个快，有人可能会说这个根本不是插入排序，而我却觉得，只不过上一个是针对于元素本身的数据进行插入，问我这个是针对于位置的插入，就我而言其实这个才更像插入排序。

冒泡排序就是每次量量比较相邻的元素，进行判断大小然后进行值的交换，如果把数组中的待比较的元素当做在水中的混乱的元素的话，那么这个排序过程就像是一个个水泡在往上冒出来，这也是冒泡排序的名字来由，不多说，见代码示例：

public void bubbleSort(Integer[] array) {
        BigDecimal timeStart = new BigDecimal(System.currentTimeMillis());
        BigDecimal spendTime = null;
        System.out.println("-----bubbleSort-----");
        // System.out.println("排序前: " + Arrays.asList(array));
        Integer temp = null;
        boolean exchanged = false;
        for (int i = 1; i < array.length; i++) {
            for (int j = 0; j < array.length - i; j++) {

                if (array[j].intValue() > array[j + 1].intValue()) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    exchanged = true;
                }
            }
            // 如果没有交换过说明顺序是本来就正确的 不需要排序 直接跳出
            if (!exchanged)
                break;
        }
        spendTime = new BigDecimal(System.currentTimeMillis()).subtract(timeStart);
        // System.out.println("排序后: " + Arrays.asList(array));
        System.out.println("排序时间: " + spendTime);
    }

值得注意的是常见的冒泡排序很多人是仅仅追求了自己实现冒泡排序的正确性，而没有考虑过是否可以优化，本文中，其中利用的exchanged标志就是优化的方案，可以发现这短短几句代码对于时间上有了很大的提升，效果见下:

//这里使用JUnit进行测试
    @Test
    public void testSort() {
    //这里利用大一点的Integer对象数组更加可以体现时间的差异性
        Integer[] array = new Integer[50000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(999999);
        }
        bubbleSort(array);
    }

这是没有设置flag的情况：

这是设置了flag的情况

（此数据在本台计算机结果是这样，不同时间也可能不同，与计算机环境有关，但是大多情况是设置这样一个标志的方式会对性能进行一定的提升）

那么，为什么会出现这样一个差别呢？
设立标志exchanged的时候，我们可以这样想：如果当前的两个发生了交换，说明了之前的是已经交换好了的，因此不需要做多余的判断与交换。

选择排序就是假定数组第一个位置为最小的值的位置，然后与剩下的进行一个一个对比，找到最小的元素的位置，然后进行交换，接着假设第二个位置作为最小数据的位置，重复以上步骤。看看实现吧：

    public void selectSort(Integer[] array) {
        BigDecimal timeStart = new BigDecimal(System.currentTimeMillis());
        BigDecimal spendTime = null;
        System.out.println("-----selectSort-----");
        System.out.println("排序前: " + Arrays.asList(array));
        int minIndex;
        Integer temp = null;

        for (int i = 0; i < array.length - 1; i++) {

            minIndex = i;

            for (int j = i + 1; j < array.length; j++) {

                if (array[minIndex].intValue() > array[j].intValue()) {
                    minIndex = j;
                }
            }

//以下的判断其实不是必须的，但是可以减少对空间的占用，减少交换的操作。
            if (minIndex != i) {
                temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
        spendTime = new BigDecimal(System.currentTimeMillis()).subtract(timeStart);
        System.out.println("排序后: " + Arrays.asList(array));
        System.out.println("排序时间: " + spendTime);

    }

插入排序通过对没有排序的元素进行适当的插入作为排序思想，大概流程如下：

首先对前连个数据进行比较，小一点的元素入到大一点的数据后边

接着用以第三个数据与前两个元素进行比较 插入到合适位置 （注意：这里的比较应该是从当前位置向前比较，而不是从第一个元素进行比较）

然后第四个元素进行同样的做法进行插入，直到最后一个元素

于是乎......

version 1.0 插入排序：大众普遍版

public void insertionSort(Integer[] array) {
       BigDecimal timeStart = new BigDecimal(System.currentTimeMillis());
       BigDecimal spendTime = null;
       Integer temp = null;
       int position;
       System.out.println("-----insertionSort-----");
       // System.out.println("排序前: " + Arrays.asList(array));
       for (int i = 1; i < array.length; i++) {

           temp = array[i];
           position = i - 1;

           while (position >= 0 && temp < array[position]) {
               array[position + 1] = array[position];
               position--;
           }
           array[position + 1] = temp;

       }
       spendTime = new BigDecimal(System.currentTimeMillis()).subtract(timeStart);
       // System.out.println("排序后: " + Arrays.asList(array));
       System.out.println("排序时间: " + spendTime);
   }

version 2.0 插入排序：就如该函数名字一样，ByFindingPosition 这个思路是先找到最合适（即最终需要插入的位置）的位置，记录下位置，然后根据记录下的位置进行元素的插入，偏移。2.0这个版本和上一版对比很有趣，乍看上去多了嵌套了一个循环，可是大多情况却比第一个快，有人可能会说这个根本不是插入排序，而我却觉得，只不过上一个是针对于元素本身的数据进行插入，问我这个是针对于位置的插入，就我而言 其实这个才更像插入排序。

public void insertionSortByFindingPosition(Integer[] array) {
        BigDecimal timeStart = new BigDecimal(System.currentTimeMillis());
        BigDecimal spendTime = null;
        Integer temp = null;
        int position;
        System.out.println("-----insertionSortByFindingPosition-----");
        System.out.println("排序前: " + Arrays.asList(array));
        for (int i = 1; i < array.length; i++) {

            position = i;

            // 找到position即往前挪的位置
            while (position > 0 && array[i] < array[position - 1]) {
                position--;
            }
            // 找到位置之後需要进行移位 然后把array[i]放在position位置
            temp = array[i];
            for (int j = i; j > position; j--) {
                array[j] = array[j - 1];
            }
            array[position] = temp;

        }
        spendTime = new BigDecimal(System.currentTimeMillis()).subtract(timeStart);
        System.out.println("排序后: " + Arrays.asList(array));
        System.out.println("排序时间: " + spendTime);
    }