排列顺序：十大排顺序算法

一、冒泡排序

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

1、算法步骤

（1）比较相邻的元素。如果第一个比第二个大，就交换他们两个

（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素 会是最大的数

（3）重复（1）（2）步骤，除了最后一个元素

对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

2、Java代码

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²) 的时间复杂度。所以 用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1、算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

2、Java代码

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;           }       }   }}

三、插入排序

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

1、算法步骤

将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的 元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2、Java代码

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;       }   }}

四、希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定 排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位； 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排 序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

1、算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1； 按增量序列个数 k，对序列进行 k 趟排序； 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直 接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2、Java代码

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、算法步骤

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

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

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

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

2、Java代码

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、算法步骤

从数列中挑出一个元素，称为 "基准"（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的 后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这 个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

2、Java代码

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、算法步骤

创建一个堆 H[0……n-1]；

把堆首（最大值）和堆尾互换；

调用 shift_down方法，使除过堆尾元素的树满足最大堆的性质；

重复步骤 2，直到堆中只有一个元素。

2、Java代码

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

3、Java代码

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、Java代码

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 桶排序

基数排序有两种方法： 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；

• 计数排序：每个桶只存储单一键值；

• 桶排序：每个桶存储一定范围的数值；

2、Java代码

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;   }}