插入排序与归并排序

插入排序与归并排序

前言：

　　排序算法应该算是算法入门级的东西了，这里重新学习算法，先暂时归纳下个人对插入排序与归并排序两种算法的理解。

插入排序：

　　插入排序可以对应到现实生活中的排队去停车场停车的场景。假设某家饭店的饭菜十分好吃（流口水），导致来这里吃饭的人特别多，后面来吃饭准备停车的车排起了长队。每次只允许一辆车过去找位置，找到位置之后才允许下一辆车进入，依此类推，直到所有的车都停好。转换成专业的数学模型就是：现有一个无序数组 A[n],要想对其进行排序。我们先从一个数开始考虑，A0肯定是排好序的。现在假设有A1，那么这时候应该将A1和A0 进行比较排序。这时候假设再来A2，A2需要与前面排好队的A0、A1 再进行比较排序。这里需要注意的是在排序的过程中可能会产生数组的移动。下面是java代码实现的升序排列的整数版本：

public static void main(String[] args) {
        int[] arr = {2, 1, 23, 22, 15, 76, 43, 36};
        ascInsertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
   
    /**
    * 升序插入排列
    * @param arr 传入的数组
    */
    private static void ascInsertionSort(int[] arr) {
        int key = 0;
        for (int j=1; j<arr.length; j++) {                // 因为如果只有一个元素根本不需要排序，所以带插入的元素的下边从1开始
            key = arr[j];                                // 用key表示当前用来插入到已排序数组中的值
            int i = j-1;
            for (; i>=0; i--)
            {   
                // 如果已排完序的数组的最后一个数比当前待插入的数小，说明不需要移动，直接break，否则需要交换两个比较值的元素的位置
                if (arr[i] > arr[i+1])                   
                {
                    arr[i+1] = arr[i];
                    arr[i] = key;
                }
                else
                {
                    break;
                }
            }
        }
    }

AscInsertionSort

很容易算出该算法的耗时主要是两层for循环嵌套导致的，第一层for循环循环的次数为n次。第二层for循环每次运行的最坏的结果是需要把前面排序好的数组再全部循环一次，为：

1 + 2 + 3 + ... + (n-1) = (n2-1)/2。 我们知道对于n的多项式，随着n的增长，对多项式结果影响结果最大的其实是最高的次数的那个项。所以不难得到该算法的时间复杂度为：θ(n2)。

选择排序：

　　既然讲了插入排序，顺便讲讲选择排序。选择排序简而言之就是每次选最帅的，选到最不帅的终结排序。

　　java实现的代码如下：

/**
    * 升序选择排序
    *
    * @param arr
    */
    private static void ascSelectionSort(int[] arr) {
        int min;
        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            min = arr[i]; // 假设最小的元素是当前就在该位置的元素
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) // 如果有元素比最小的元素小，则将该元素的值作为最小元素的值，依次查找下去，最终找到最小元素所在的下表
                {
                    min = arr[j];
                    minIndex = j;
                }
            }

            // 循环完发现最小元素的位置不是当前在该位置的元素，则交换两个元素的位置
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

ascSelectionSort

可以发现一个很悲伤的事实，这个算法的时间复杂度也为：θ(n²)。

更多详情见请继续阅读下一页的精彩内容：