用 Java 实现的八种经常使用排序算法

八种排序算法能够按照如图分类java

交换排序

所谓交换，就是序列中任意两个元素进行比较，根据比较结果来交换各自在序列中的位置，以此达到排序的目的。算法

1. 冒泡排序

冒泡排序是一种简单的交换排序算法，以升序排序为例，其核心思想是：shell

1. 从第一个元素开始，比较相邻的两个元素。若是第一个比第二个大，则进行交换。
2. 轮到下一组相邻元素，执行一样的比较操做，再找下一组，直到没有相邻元素可比较为止，此时最后的元素应是最大的数。
3. 除了每次排序获得的最后一个元素，对剩余元素重复以上步骤，直到没有任何一对元素须要比较为止。

用 Java 实现的冒泡排序以下数组

public void bubbleSortOpt(int[] arr) {

    if(arr == null) {
        throw new NullPoniterException();
    }
    if(arr.length < 2) {
        return;
    }
    int temp = 0;
    for(int i = 0; i < arr.length - 1; i++) {
        for(int j = 0; j < arr.length - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. 冒泡排序优化

如今有个问题，假如待排序数组是 二、一、三、四、5 这样的状况，按照上述代码实现，第一次循环便可得出正确结果。但循环并不会中止，而是继续执行，直到结束为止。显然，以后的循环遍历是没有必要的。优化

为了解决这个问题，咱们能够设置一个标志位，用来表示当前次循环是否有交换，若是没有，则说明当前数组已经彻底排序。ui

public static int bubbleSortOpt2(int[] arr) {

    if (arr == null) {
        throw new NullPointerException();
    } else if (arr.length < 2) {
        return 0;
    }

    int temp;
    int count = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        int flag = 1;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = 0;
            }
            count++;
        }
        // 没有发生交换，排序已经完成
        if (flag == 1) {
            return count;
        }
    }
    return count;
}

算法还能够再优化，好比 三、四、二、一、六、七、8 这个数组，第一次循环后，变为 三、二、一、四、六、七、8 的顺序，咱们发现，1 以后的 4 、六、七、8 已经有序了，第二次循环就不必对后面这段再遍历比较。spa

假设一次循环后数组第 i 个元素后全部元素已经有序，优化目标就是下次循环再也不花费时间遍历已经有序的部分。关键在于如何定位 i 这个分界点，其实并不难，能够想象，因为 i 以前的元素是无序的，因此必定有交换发生，而 i 以后的元素已经有序，不会发生交换，最后发生交换的地点，就是咱们要找的分界点。3d

public static int bubbleSortOpt3(int[] arr) {

    if (arr == null) {
        throw new RuntimeException();
    } else if (arr.length < 2) {
        return 0;
    }

    int temp;
    int count = 0;
    int len = arr.length - 1;
    for (int i = 0; i < len; i++) {
        // 记录最后一次交换位置
        int lastChange = 0;
        for (int j = 0; j < len; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // 每交换一次更新一次
                lastChange = j;
            }
            count++;
        }
        // 没有发生交换，排序已经完成
        if (lastChange == 0) {
            return count;
        }
        len = lastChange;
    }
    return count;
}

3. 快速排序

快速排序的思想很简单，就是先把待排序的数组拆成左右两个区间，左边都比中间的基准数小，右边都比基准数大。接着左右两边各自再作一样的操做，完成后再拆分再继续，一直到各区间只有一个数为止。指针

举个例子，如今我要排序 四、九、五、一、二、6 这个数组。通常取首位的 4 为基准数，第一次排序的结果是：code

二、一、四、五、九、6

可能有人以为奇怪，2 和 1 交换下位置也能知足条件，为何 2 在首位？这其实由实际的代码实现来决定，并不影响以后的操做。以 4 为分界点，对 二、一、4 和 五、九、6 各自排序，获得：

一、二、四、五、九、6

不用管左边的 一、二、4 了，将 五、九、6 拆成 5 和 九、6，再排序，至此结果为：

一、二、四、五、六、9

为何把快排划到交换排序的范畴呢？由于元素的移动也是靠交换位置来实现的。算法的实现须要用到递归（拆分区间以后再对每一个区间做一样的操做）

用 Java 实现的快速排序以下

public void quicksort(int[] arr, int start, int end) {

    if(start < end) {
        // 把数组中的首位数字做为基准数
        int stard = arr[start];
        // 记录须要排序的下标
        int low = start;
        int high = end;
        // 循环找到比基准数大的数和比基准数小的数
        while(low < high) {
            // 右边的数字比基准数大
            while(low < high && arr[high] >= stard) {
                high--;
            }
            // 使用右边的数替换左边的数
            arr[low] = arr[high];
            // 左边的数字比基准数小
            while(low < high && arr[low] <= stard) {
                low++;
            }
            // 使用左边的数替换右边的数
            arr[high] = arr[low];
        }
        // 把标准值赋给下标重合的位置
        arr[low] = stard;
        // 处理全部小的数字
        quickSort(arr, start, low);
        // 处理全部大的数字
        quickSort(arr, low + 1, end);
    }
}

插入排序

插入排序是一种简单的排序方法，其基本思想是将一个记录插入到已经排好序的有序表中，使得被插入数的序列一样是有序的。按照此法对全部元素进行插入，直到整个序列排为有序的过程。

1. 直接插入排序

直接插入排序就是插入排序的粗暴实现。对于一个序列，选定一个下标，认为在这个下标以前的元素都是有序的。将下标所在的元素插入到其以前的序列中。接着再选取这个下标的后一个元素，继续重复操做。直到最后一个元素完成插入为止。咱们通常从序列的第二个元素开始操做。

用 Java 实现的算法以下：

public void insertSort(int[] arr) {
    // 遍历全部数字
    for(int i = 1; i < arr.length - 1; i++) {
        // 当前数字比前一个数字小
        if(arr[i] < arr[i - 1]) {
            int j;
            // 把当前遍历的数字保存起来
            int temp = arr[i];
            for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
                // 前一个数字赋给后一个数字
                arr[j + 1] = arr[j];
            }
            // 把临时变量赋给不知足条件的后一个元素
            arr[j + 1] = temp;
        }
    }
}

2. 希尔排序

某些状况下直接插入排序的效率极低。好比一个已经有序的升序数组，这时再插入一个比最小值还要小的数，也就意味着被插入的数要和数组全部元素比较一次。咱们须要对直接插入排序进行改进。

怎么改进呢？前面提过，插入排序对已经排好序的数组操做时，效率很高。所以咱们能够试着先将数组变为一个相对有序的数组，而后再作插入排序。

希尔排序能实现这个目的。希尔排序把序列按下标的必定增量（步长）分组，对每组分别使用插入排序。随着增量（步长）减小，一直到一，算法结束，整个序列变为有序。所以希尔排序又称缩小增量排序。

通常来讲，初次取序列的一半为增量，之后每次减半，直到增量为一。

用 Java 实现的算法以下：

public void shellSort(int[] arr) {
    // gap 为步长，每次减为原来的一半。
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 对每一组都执行直接插入排序
        for (int i = 0 ;i < gap; i++) {
            // 对本组数据执行直接插入排序
            for (int j = i + gap; j < arr.length; j += gap) {
                // 若是 a[j] < a[j-gap]，则寻找 a[j] 位置，并将后面数据的位置都后移
                if (arr[j] < arr[j - gap]) {
                    int k;
                    int temp = arr[j];
                    for (k = j - gap; k >= 0 && arr[k] > temp; k -= gap) {
                        arr[k + gap] = arr[k];
                    }
                    arr[k + gap] = temp;
                }
            }
        }
    }
}

选择排序

选择排序是一种简单直观的排序算法，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，而后，再从剩余未排序元素中继续寻找最小（大）元素，而后放到已排序序列的末尾。以此类推，直到全部元素均排序完毕。

1. 简单选择排序

选择排序思想的暴力实现，每一趟从未排序的区间找到一个最小元素，并放到第一位，直到所有区间有序为止。

用 Java 实现的算法以下：

public void selectSort(int[] arr) {
    // 遍历全部的数
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        // 把当前遍历的数和后面全部的数进行比较，并记录下最小的数的下标
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                // 记录最小的数的下标
                minIndex = j;
            }
        }
        // 若是最小的数和当前遍历的下标不一致，则交换
        if (i != minIndex) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

2. 堆排序

咱们知道，对于任何一个数组均可以当作一颗彻底二叉树。堆是具备如下性质的彻底二叉树：每一个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每一个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。以下图：

像上图的大顶堆，映射为数组，就是 [50, 45, 40, 20, 25, 35, 30, 10, 15]。能够发现第一个下标的元素就是最大值，将其与末尾元素交换，则末尾元素就是最大值。因此堆排序的思想能够概括为如下两步：

1. 根据初始数组构造堆
2. 每次交换第一个和最后一个元素，而后将除最后一个元素之外的其余元素从新调整为大顶堆

重复以上两个步骤，直到没有元素可操做，就完成排序了。

咱们须要把一个普通数组转换为大顶堆，调整的起始点是最后一个非叶子结点，而后从左至右，从下至上，继续调整其余非叶子结点，直到根结点为止。

/**
 * 转化为大顶堆
 * @param arr 待转化的数组
 * @param size 待调整的区间长度
 * @param index 结点下标
 */
public void maxHeap(int[] arr, int size, int index) {
    // 左子结点
    int leftNode = 2 * index + 1;
    // 右子结点
    int rightNode = 2 * index + 2;
    int max = index;
    // 和两个子结点分别对比，找出最大的结点
    if (leftNode < size && arr[leftNode] > arr[max]) {
        max = leftNode;
    }
    if (rightNode < size && arr[rightNode] > arr[max]) {
        max = rightNode;
    }
    // 交换位置
    if (max != index) {
        int temp = arr[index];
        arr[index] = arr[max];
        arr[max] = temp;
        // 由于交换位置后有可能使子树不知足大顶堆条件，因此要对子树进行调整
        maxHeap(arr, size, max);
    }
}

/**
 * 堆排序
 * @param arr 待排序的整型数组
 */
public static void heapSort(int[] arr) {
    // 开始位置是最后一个非叶子结点，即最后一个结点的父结点
    int start = (arr.length - 1) / 2;
    // 调整为大顶堆
    for (int i = start; i >= 0; i--) {
        SortTools.maxHeap(arr, arr.length, i);
    }
    // 先把数组中第 0 个位置的数和堆中最后一个数交换位置，再把前面的处理为大顶堆
    for (int i = arr.length - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        maxHeap(arr, i, 0);
    }
}

归并排序

归并排序是创建在归并操做上的一种有效，稳定的排序算法。该算法采用分治法的思想，是一个很是典型的应用。归并排序的思路以下：

1. 将 n 个元素分红两个各含 n/2 个元素的子序列
2. 借助递归，两个子序列分别继续进行第一步操做，直到不可再分为止
3. 此时每一层递归都有两个子序列，再将其合并，做为一个有序的子序列返回上一层，再继续合并，所有完成以后获得的就是一个有序的序列

关键在于两个子序列应该如何合并。假设两个子序列各自都是有序的，那么合并步骤就是：

1. 建立一个用于存放结果的临时数组，其长度是两个子序列合并后的长度
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入临时数组，并移动指针到下一位置
4. 重复步骤 3 直到某一指针达到序列尾
5. 将另外一序列剩下的全部元素直接复制到合并序列尾

用 Java 实现的归并排序以下：

/**
 * 合并数组
 */
public static void merge(int[] arr, int low, int middle, int high) {
    // 用于存储归并后的临时数组
    int[] temp = new int[high - low + 1];
    // 记录第一个数组中须要遍历的下标
    int i = low;
    // 记录第二个数组中须要遍历的下标
    int j = middle + 1;
    // 记录在临时数组中存放的下标
    int index = 0;
    // 遍历两个数组，取出小的数字，放入临时数组中
    while (i <= middle && j <= high) {
        // 第一个数组的数据更小
        if (arr[i] <= arr[j]) {
            // 把更小的数据放入临时数组中
            temp[index] = arr[i];
            // 下标向后移动一位
            i++;
        } else {
            temp[index] = arr[j];
            j++;
        }
        index++;
    }
    // 处理剩余未比较的数据
    while (i <= middle) {
        temp[index] = arr[i];
        i++;
        index++;
    }
    while (j <= high) {
        temp[index] = arr[j];
        j++;
        index++;
    }
    // 把临时数组中的数据从新放入原数组
    for (int k = 0; k < temp.length; k++) {
        arr[k + low] = temp[k];
    }
}

/**
 * 归并排序
 */
public static void mergeSort(int[] arr, int low, int high) {
    int middle = (high + low) / 2;
    if (low < high) {
        // 处理左边数组
        mergeSort(arr, low, middle);
        // 处理右边数组
        mergeSort(arr, middle + 1, high);
        // 归并
        merge(arr, low, middle, high);
    }
}

基数排序

基数排序的原理是将整数按位数切割成不一样的数字，而后按每一个位数分别比较。为此须要将全部待比较的数值统一为一样的数位长度，数位不足的数在高位补零。

使用 Java 实现的基数排序：

/**
 * 基数排序
 */
public static void radixSort(int[] arr) {
    // 存放数组中的最大数字
    int max = Integer.MIN_VALUE;
    for (int value : arr) {
        if (value > max) {
            max = value;
        }
    }
    // 计算最大数字是几位数
    int maxLength = (max + "").length();
    // 用于临时存储数据
    int[][] temp = new int[10][arr.length];
    // 用于记录在 temp 中相应的下标存放数字的数量
    int[] counts = new int[10];
    // 根据最大长度的数决定比较次数
    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        // 每个数字分别计算余数
        for (int j = 0; j < arr.length; j++) {
            // 计算余数
            int remainder = arr[j] / n % 10;
            // 把当前遍历的数据放到指定的数组中
            temp[remainder][counts[remainder]] = arr[j];
            // 记录数量
            counts[remainder]++;
        }
        // 记录取的元素须要放的位置
        int index = 0;
        // 把数字取出来
        for (int k = 0; k < counts.length; k++) {
            // 记录数量的数组中当前余数记录的数量不为 0
            if (counts[k] != 0) {
                // 循环取出元素
                for (int l = 0; l < counts[k]; l++) {
                    arr[index] = temp[k][l];
                    // 记录下一个位置
                    index++;
                }
                // 把数量置空
                counts[k] = 0;
            }
        }
    }
}

八种排序算法的总结