十大排序算法

一、冒泡排序

        冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地走访要排序的数列，一次比
较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经交换慢慢"浮"到数列的头部。

/**
 * 冒泡排序
 */
public class BubbleSort {
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        for (int i = 1; i < arr.length; i++) { //比较的轮数
            for (int j = 0; j < arr.length - i; j++) { // 每轮比较的次数
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

 二、选择排序

        选择排序也是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以
用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

public class SelectionSort {
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) { //比较的轮数
            int min = i;// 记录最小值的索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            // 将最小值放置在索引为i的位置
            if (min != i) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }
}

三、插入排序

       插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理
解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

public class InsertSort {
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            int instartVal = arr[i];
            int j = i - 1; // 有序区最后一个元素
            while (j >= 0) {
                if (arr[j] > instartVal) {
                    arr[j + 1] = arr[j];
                    j--;
                } else {
                    break;
                }
            }
            arr[j + 1] = instartVal;
        }
    }
}

四、希尔排序

     希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
    希尔排序是基于插入排序的以下两点性质而提出改进方法的：
     • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
     • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
    希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排
序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

public class ShellSort {
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int length = arr.length;
        // step:表示希尔增量
        for (int step = length / 2; step >= 1; step /= 2) {
            //从setp位置开始进行插入排序，直至完毕
            for (int i = step; i < arr.length; i++) {
                int instartVal = arr[i];
                int j = i - step; // 有序区最后一个元素
                while (j >= 0) {
                    if (arr[j] > instartVal) {
                        arr[j + step] = arr[j];
                        j -= step;
                    } else {
                        break;
                    }
                }
                arr[j + step] = instartVal;
            }
        }
    }
}

 五、 归并排序

       归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法
（Divide and Conquer）的一个非常典型的应用。
1. 算法步骤
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {
    public int[] sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);
        int[] left = Arrays.copyOfRange(arr, 0, middle );
        int[] right = Arrays.copyOfRange(arr, middle , arr.length);
        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        int m = 0;
        int n = 0;
        while (m < left.length  && n < right.length) {
            if (left[m] <= right[n]) {
                result[i++] = left[m++];
            } else {
                result[i++] = right[n++];
            }
        }
        while (m < left.length) {
            result[i++] = left[m++];
        }
        while (n < right.length) {
            result[i++] = right[n++];
        }
        return result;
    }
}

六、 快速排序

1. 算法步骤
1. 从数列中挑出一个元素，称为 "基准"（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

/**
 * 快速排序
 */
public class FastSort {
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //  排序
        fastSort(arr, 0, arr.length - 1);
    }

    // 对[left,right]区间进行排序
    private void fastSort(int[] arr, int left, int right) {
        // 递归到底的情况
        if (left >= right) {
            return;
        }
        // 递归操作
        int pivot = arr[left];
        int i = left;
        int j = right;

        while (i < j) {
            // 从右边开始找到第一个小于pivot的元素
            while (i < j && arr[j] > pivot) {
                j--;
            }
            // 替换
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            // 从左边开始找到第一个比pivot大的元素
            while (i < j && arr[i] < pivot) {
                i++;
            }
            // 替换
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = pivot;
        fastSort(arr, left, i - 1);
        fastSort(arr, i + 1, right);
    }
}

七、 堆排序

       堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
1. 算法步骤
1. 创建一个堆 H[0……n-1]；
2. 把堆首（最大值）和堆尾互换；
3. 调用 shift_down方法，使除过堆尾元素的树满足最大堆的性质；
4. 重复步骤 2，直到堆中只有一个元素。

// 堆排序
public class HeapSort {
    private int getParentIndex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("index is invalid!");
        }
        if (index == 0) { // 处理根节点
            return -1;
        }
        return (index - 1) / 2;
    }

    // 根据当前结点所在数组的索引获取左孩子结点的索引
    private int getLeftChildIndex(int index) {
        return 2 * index + 1;
    }

    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        // 将完全二叉树整理成堆
        heapify(arr);
        // 排序
        for (int i = arr.length - 1; i > 0; i--) {
            // 将堆尾元素与堆首元素互换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 整理成堆
            siftDown(0, arr, i);
        }
    }


    private void heapify(int[] arr) {
        // 1、找到最后一个元素的父节点
        int parentIndex = getParentIndex(arr.length - 1);

        // 2、从最后一个元素的父节点开始下沉操作，直到根节点
        for (; parentIndex >= 0; parentIndex--) {
            siftDown(parentIndex, arr, arr.length);
        }
    }

    private void siftDown(int curIndex, int[] arr, int length) {
        int leftChildIndex = getLeftChildIndex(curIndex);
        int chageIndex = leftChildIndex;
        while (leftChildIndex < length) {
            int rigthChildIndex = leftChildIndex + 1;
            if (rigthChildIndex < length && arr[rigthChildIndex] > arr[leftChildIndex]) {
                chageIndex = rigthChildIndex;
            }
            if (arr[chageIndex] > arr[curIndex]) {
                // 交换操作
                int temp = arr[curIndex];
                arr[curIndex] = arr[chageIndex];
                arr[chageIndex] = temp;
                curIndex = chageIndex;
                leftChildIndex = getLeftChildIndex(curIndex);
                chageIndex = leftChildIndex;
            } else {
                break;
            }
        }
    }
}

八、 计数排序

      计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
1. 计数排序的特征当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。
2、算法步骤
（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

public class CountingSort {
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 获取数组中最大的值
        int maxVal = getMaxVal(arr);
        // 创建一个数组，用来计数
        int[] counts = new int[maxVal + 1];
        // 计数
        for (int i = 0; i < arr.length; i++) {
            counts[arr[i]]++;
        }
        // 反向填充
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i] > 0) {
                arr[index++] = i;
                counts[i]--;
            }
        }
    }

    private int getMaxVal(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }
}

九、 桶排序

     桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
• 在额外空间充足的情况下，尽量增大桶的数量
• 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
1. 什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
2. 什么时候最慢
当输入的数据被分配到了同一个桶中。

import java.util.ArrayList;
import java.util.List;

// 桶排序
public class BucketSort {
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 创建桶
        List<Integer>[] buckets = new ArrayList[10];
        // 初始化桶
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        // 将数据放入桶中
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] / 10;
            buckets[index].add(arr[i]);
        }
        //分别堆每个桶进行排序
        for (int i = 0; i < buckets.length; i++) {
            buckets[i].sort(null);
        }
        // 将桶中的元素反向填充到arr中
        int index = 0;
        for (int i = 0; i < buckets.length; i++) {
            List<Integer> item = buckets[i];
            while (!item.isEmpty()) {
                arr[index++] = item.remove(0);
            }
        }
    }
}

十、 基数排序

     原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用
LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序
1. 基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；

import java.util.ArrayList;
import java.util.List;

/**
 * 计数排序
 */
public class RadixSort {
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // 获取最大值
        int maxValue = getMaxVal(arr);
        // 获取最大位数
        int maxDigit = getMaxDigit(maxValue);
        radixSort(arr, maxDigit);
    }

    private void radixSort(int[] arr, int maxDigit) {
        int mod = 10;// 模数
        int dev = 1;
        for (int i = 0; i < maxDigit; i++) { // 比较轮数
            // 创建桶
            List<Integer>[] bucket = new ArrayList[10];
            // 对桶进行初始化
            for (int n = 0; n < bucket.length; n++) {
                bucket[n] = new ArrayList<>();
            }
            for (int j = 0; j < arr.length; j++) {
                int bucketIndex = (arr[j] / dev) % mod;
                bucket[bucketIndex].add(arr[j]);
            }
            // 对桶进行排序
            //分别堆每个桶进行排序
            for (int k = 0; k < bucket.length; k++) {
                bucket[k].sort(null);
            }
            // 将桶中的元素反向填充到arr中
            int index = 0;
            for (int m = 0; m < bucket.length; m++) {
                List<Integer> item = bucket[m];
                while (!item.isEmpty()) {
                    arr[index++] = item.remove(0);
                }
            }
            dev = dev * 10;
        }
    }

    private int getMaxDigit(int maxValue) {
        int length = 1;
        int curNum = maxValue;
        while (curNum / 10 != 0) {
            curNum = curNum / 10;
            length++;
        }
        return length;
    }

    private int getMaxVal(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }
}