〇、排序算法简介

排序：将一组数据依照指定的程序进行排列的过程。

排序的分类：

• 外部排序：将须要解决的所有数据加载到内存中进行排序。
• 内部排序：因为数据量过大无奈全副加载到内存中，须要借助外存进行排序。

咱们钻研的排序算法次要是外部排序算法。其中外部排序又能够分为冒泡排序、简略抉择排序（简称为抉择排序）、间接插入排序（简称为插入排序）、希尔排序、疾速排序、归并排序、基数排序、堆排序八大排序算法：

本篇将介绍冒泡排序、抉择排序、插入排序、疾速排序。下篇将介绍希尔排序、归并排序、基数排序、堆排序。

一、冒泡排序

根本思维：看待排序序列从前向后，顺次比拟相邻元素的值，若发现逆序则替换，使值较大的元素逐步从前移向后部，就象水底下的气泡一样逐步向上冒。

对于待排序数组[3, 9, -1, 10, 20]，冒泡排序算法的图解过程如下：

由此能够写出冒泡排序算法的代码：

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

该代码能够优化：

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int temp;
        boolean flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (!flag) { //优化
            break;
        }
    }
}

二、抉择排序

根本思维：从待排序的数据中，按指定的规定选出某一元素，再依规定替换地位，达到排序。

对于待排序数组[3, 9, -1, 10, 20]，抉择排序算法的图解过程如下：

由此能够写出抉择排序算法的代码：

public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

三、插入排序

根本思维：对于待排序的元素，以插入的形式寻找该元素的适当地位，达到排序。

对于待排序数组[3, 9, -1, 10, 20]，插入排序算法的图解过程如下：

由此能够写出插入排序算法的代码：

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int insert = arr[i];
        int j;
        for (j = i - 1; j >= 0; j--) {
            if (insert < arr[j]) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = insert;
    }
}

该代码能够优化：

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int insertVal = arr[i];
        int insertIndex = i - 1;
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        if (insertIndex + 1 == i) { //优化
            arr[insertIndex + 1] = insertVal;
        }
    }
}

四、疾速排序

根本思维：首先设定一个分界值（主元），通过一趟排序（划分函数），将待排序数组宰割成两局部，其中一部分的所有元素都比另外一部分的所有元素要小，而后再按此办法对这两局部数据别离进行疾速排序，整个排序过程能够递归进行，以此达到整个数据变成有序序列。

主元的选取：主元能够抉择首元素、尾元素、两头元素、随机选取、三点中值法、相对中值法等。抉择首元素作为主元往往是不通过充分考虑的。但为了不便起见，本篇选取首元素作为主元。

划分函数的选取：划分函数能够抉择单向扫描分区法、双向扫描分区法等。本篇选取双向扫描分区法：选定主元后，确定左右“指针”扫描待排序数组；保障左指针在右指针的右边，当左指针元素不大于主元时一直向右推动，当右指针元素不小于主元时一直向左推动；直到左右指针相交，即为主元的地位。

由此能够写出疾速排序算法的代码：

public static void quickSort(int[] arr, int left, int right) {
    int l = left;
    int r = right;
    int pivot = arr[left];
    while (l <= r) {
        while (l <= r && arr[l] <= pivot) l++; //左指针元素不大于主元时一直向右推动
        while (l <= r && arr[r] >= pivot) r--; //右指针元素不小于主元时一直向左推动
        if (l <= r) {
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
    }
    arr[left] = arr[r]; //arr[r]即为主元的地位
    arr[r] = pivot;
    if (left < r) quickSort(arr, left, r);
    if (right > l) quickSort(arr, l, right);
}