【排序算法】插入排序、快速排序以及归并排序

一、插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。

Image-插入排序.png

算法思维

每次将一个待排序的记录，按其关键字大小插入到前面的已经排好的子表中的适当的位置。直到全部记录插入完成为止。

算法性能

• 时间复杂度为 O(n^2)。

类型

插入排序主要包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。

• 直接插入排序：

【解释】：直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

直接插入排序的算法思路：
（1） 设置监视哨r[0]，将待插入记录的值赋值给r[0]；
（2） 设置开始查找的位置j；
（3） 在数组中进行搜索，搜索中将第j个记录后移，直至r[0].key≥r[j].key为止；
（4） 将r[0]插入r[j+1]的位置上。

• 折半插入排序

【解释】：将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较，即可得到折半插入排序算法。

算法的基本过程(思路)：

（1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；

（2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；

（3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

• 希尔排序法

希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。

各组内的排序通常采用直接插入法。
由于开始时s的取值较大，每组内记录数较少，所以排序比较快。随着不断增大，每组内的记录数逐步增多，但由于已经按排好序，因此排序速度也比较快。

【Java_Code】语言解法如下：

import java.util.Scanner;

public class InsertionSort{
    public static void main(String[] array){
        int[] array_one = {23,34,567,78,56,423,99,11};
        int[] array_two = insertionSort(array_one);
        int[] array_three = insertionSort_2(array_one);

        printNumbers(array_two);
        printNumbers(array_three);

        // 技能点提升:给自定义的数组【插入排序】；
        System.out.println("请输入您要排序的数组：" +'\n');
        Scanner sc = new Scanner(System.in);
        String inputString = sc.nextLine();
        String stringArray[] = inputString.split(",");
        // 数组类型转换；
        int num[] = new int[stringArray.length];
        for (int i = 0; i < stringArray.length; i++) {
              num[i] = Integer.parseInt(stringArray[i]);
        }
        int[] array_four = insertionSort_2(num);
        printNumbers(array_four);

    }
    private static void printNumbers(int[] input) {
        System.out.println("正在排序中..." +'\n');
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
    }
    public static int[] insertionSort(int[] array){
        for (int i = 1;i < array.length; i++){
            for(int j = i; j > 0;j--){
                if(array[j] < array[j-1]){
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }
            }
        }
        return array;
    }
    // 【算法改进】： 因为insertionSort中每一次位置置换的时候需要定义一个temp，这这多浪费内存啊！
    //所以我的解决思路是，将所有要后移的元素全部都存在一个新开辟的内存空间中，然后再进行比较重排序。只定义了一个temp
    public static int[] insertionSort_2(int[] array){
        for(int i = 1;i < array.length;i++){
            int temp = array[i];
            int k;
            for (k = i;k > 0 && array[k-1] > temp;k--){
                array[k] = array[k-1];
            }
            array[k] = temp;
        }
        return array;
    }

}

Image-插入排序.png

【Python_Code】如下，寥寥几行就实现了。

import random
Range = 100
Length = 5
list = random.sample(range(Range),Length)    #在指定序列中随机获取指定长度片段
print('before sort:',list)
for i in range(1,Length):                   #默认第一个元素已经在有序序列中，从后面元素开始插入    
    for j in range(i,0,-1):                 #逆向遍历比较，交换位置实现插入        
        if list[j] < list[j-1]:            
            list[j],list[j-1] = list[j-1],list[j]
print('after sort:',list)

二、快速排序

算法思想：基于分治的思想，是冒泡排序的改进型。

首先在数组中选择一个基准点。基准点的选取可能会影响快速排序的效率。

算法的思维

然后分别从数组的两端扫描数组，设两个指示标志（low指向起始位置，high指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换low和high位置的值。

然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换low和high位置的值，如此往复循环，直到low>=high,然后把基准点的值放到high这个位置。

Image-快速排序.png

算法性能

• 理想的情况：算法的时间复杂度为 O(nlog2 n)

• 最坏的情况：排序算法的时间复杂度为 O(n^2)

• 快速排序的空间复杂度为O(log2n))；

【注释】：它是基于关键字比较的内部排序算法中速度最快的，快速排序亦因此而得名。

public class QuickSort {

    private int array[]; //定义一个数组
    private int length;  // 定义一个私有属性

    public void sort(int[] inputArr) {
        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    }
    // 快速排序算法
    private void quickSort(int lowerIndex, int higherIndex) {
        int i = lowerIndex;
        int j = higherIndex;
        
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // 分为两部分
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }
    // 元素置换
    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String a[]){
        QuickSort sorter = new QuickSort();
        int[] input = {11,88,9,99,66,77,333,678,345,123,101,100,90,55};
        sorter.sort(input);
        for(int i:input){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}

Image快速排序

三、归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

通过将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

GIF形象表示归时并

算法描述

• 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

• 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

• 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

算法地位

速度仅次于快速排序，为稳定排序算法。

归并原理.png

【Java_Code】语言解法如下：

public class MergeSort {

    private int[] array;
    private int[] tempMergArr;
    private int length;

    public static void main(String a[]){

        int[] inputArr = {11，88,9,99,66,77,333,678,345,123,101,100,90,55};
        MergeSort mms = new MergeSort();
        mms.sort(inputArr);
        for(int i:inputArr){
            System.out.print(i);
            System.out.print(" ");
        }
    }

    public void sort(int inputArr[]) {
        this.array = inputArr;
        this.length = inputArr.length;
        this.tempMergArr = new int[length];
        doMergeSort(0, length - 1);
    }

    private void doMergeSort(int lowerIndex, int higherIndex) {

        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            // Below step sorts the left side of the array
            doMergeSort(lowerIndex, middle);
            // Below step sorts the right side of the array
            doMergeSort(middle + 1, higherIndex);
            // Now merge both sides
            mergeParts(lowerIndex, middle, higherIndex);
        }
    }

    private void mergeParts(int lowerIndex, int middle, int higherIndex) {

        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
        }
    }
}

归并排序

【Python_Code】

def MergeSort(lists):
    if len(lists) <= 1:
        return lists
    num = int( len(lists) / 2 )
    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])
    return Merge(left, right)
def Merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += list(left[l:])
    result += list(right[r:])
    return result
print MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])