排序问题一直都是程序工作或面试中的重点，特别是对于排序算法而言，在一些公司的笔试中，手写个冒泡啥的也不足为奇，因此今天抽空整理一下Java语言实现的各类排序算法，互勉学习一下。根据排序的不同方式大概可归为一下五类：

比较排序（Comparison Sorting）

比较排序是一系列排序算法的集合，它们都是使用比较来确定元素之间的相对顺序。比较排序算法的一般思路是：比较两个元素的大小，如果第一个元素比第二个元素大，则交换它们的位置，然后继续比较剩余的元素，直到所有元素都排序完毕。常见的比较排序有冒泡排序、快速排序、选择排序等等等。下面一一介绍：

冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。一次循环找出一个最大的数放在最后。然后开始第二个循环，再次排序找出除了上一次循环的最大数以外的数，（也就是每次找个最大的放在最后，第二次就不包含上次已找出的最大数再次排序寻找，让最大数从后往前依次递减）依此循环直到没有再需要交换，也就是说该数列已经排序完成。

部分排序示例图如下：

java语言实现：

    /*** 冒泡排序** @param index*/public static void bubbleSort(int[] index) {int len = index.length;for (int i = 0; i < len; i++) {//第二重循环的条件for (int j = 0; j < len - i - 1; j++) {if (index[j] > index[j + 1]) {int temp = index[j];index[j] = index[j + 1];index[j + 1] = temp;}}}}

测试一下1000个随机数的排序时间：

/*** @author young* @date 2022/11/26 18:21* @description:*/
public class SortTest {public static void main(String[] args) {long startTime = System.currentTimeMillis();int[] index = new int[1000];Random random = new Random();for (int i = 0; i < 1000; i++) {index[i] =(int)(random.nextInt()*1000);}Sort.bubbleSort(index);/*排序耗费的时间为：10ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}
}

选择排序（Selection Sort）

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法(比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面)。

这里以每次找最小数为例，部分排序示例图如下：

代码实现如下：

/*** 选择排序* @param array*/public static void selectionSort(int[] array) {int minIndex;int temp;for (int i = 0; i < array.length; i++) {minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {//找到最小数并保存index的位置    minIndex = j;}}temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}}

测试一下效率：

/*** @author young* @date 2022/11/26 18:21* @description:*/
public class SortTest {public static void main(String[] args) {long startTime = System.currentTimeMillis();int[] index = new int[1000];Random random = new Random();for (int i = 0; i < 1000; i++) {index[i] =(int)(random.nextInt()*1000);}//选择排序效率测试Sort.selectionSort(index);/*排序耗费的时间为：3ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}
}

比冒泡更快👍

插入排序（Insertion Sort）

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法--插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素，但将最后一个元素除外(让数组多一个空间才有插入的位置)，而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是:每步将一个待排序的纪录，在已排序序列中从后向前扫描，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

插入排序都采用in-place在数组上实现。具体算法描述如下：

⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

排序示例图如下：

代码实现如下：

/*** 插入排序** @param index*/public static void insertSort(int[] index) {//单独把数组长度拿出来，提高效率int len = index.length;//要插入的数int insertNum;//因为第一次不用，所以从1开始for (int i = 1; i < len; i++) {insertNum = index[i];//序列元素个数int j = i - 1;//从后往前循环，将大于insertNum的数向后移动while (j >= 0 && index[j] > insertNum) {//元素向后移动index[j + 1] = index[j];j--;}//找到位置，插入当前元素index[j + 1] = insertNum;}}

测试结果如下：

public class SortTest {public static void main(String[] args) {long startTime = System.currentTimeMillis();int[] index = new int[1000];Random random = new Random();for (int i = 0; i < 1000; i++) {index[i] =(int)(random.nextInt()*1000);}//插入排序效率测试Sort.insertSort(index);/*排序耗费的时间为：1ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}
}

希尔排序（Shell Sort）

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因希尔于1959年提出而得名。该方法的基本思想是:先将整个待排元素序列分割成若千个子序列，由相隔某个“增量”的元素组成的，分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序，增量足够小时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下，接近最好情况，效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。希尔排序法属于插入类排序，是将整个无序列分割成若千小的子序列分别进行插入排序的方法。

部分排序示例图如下：

代码实现如下：

    /*** 希尔排序** @param index*/public static void shellSort(int[] index) {int n = index.length;// 对每个增量进行希尔排序for (int gap = n / 2; gap > 0; gap /= 2) {// 从gap个元素开始，逐个对其所在的组进行直接插入排序for (int i = gap; i < n; i++) {int j = i;int temp = index[j];if (index[j] < index[j - gap]) {//从后往前遍历while (j - gap >= 0 && temp < index[j - gap]) {index[j] = index[j - gap];//向后移动gap位j -= gap;}index[j] = temp;}}}
}

效率测试：

public class SortTest {public static void main(String[] args) {long startTime = System.currentTimeMillis();int[] index = new int[1000];Random random = new Random();for (int i = 0; i < 1000; i++) {index[i] =(int)(random.nextInt()*1000);}//希尔排序效率测试Sort.shellSort(index);/*排序耗费的时间为：2ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}
}

并归排序（Merge Sort）

归并排序是建立在并归操作上的一种有效，稳定的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。适用于内存少的时候使用。

部分排序示例图如下：

代码实现：

 /*** 并归排序** @param index* @param left* @param right*/public static void mergeSort(int[] index, int left, int right) {// 每组元素个数  int t = 1;int size = right - left + 1;while (t < size) {// 本次循环每组元素个数  int s = t;t = 2 * s;int i = left;while (i + (t - 1) < size) {merge(index, i, i + (s - 1), i + (t - 1));i += t;}if (i + (s - 1) < right) {merge(index, i, i + (s - 1), right);}}}private static void merge(int[] data, int p, int q, int r) {int[] mg = new int[data.length];int s = p;int t = q + 1;int k = p;while (s <= q && t <= r) {if (data[s] <= data[t]) {mg[k] = data[s];s++;} else {mg[k] = data[t];t++;}k++;}if (s == q + 1) {mg[k++] = data[t++];} else {mg[k++] = data[s++];}if (r + 1 - p >= 0){ System.arraycopy(mg, p, data, p, r + 1 - p);}}

测试效率：

public class SortTest {public static void main(String[] args) {long startTime = System.currentTimeMillis();int[] index = new int[1000];Random random = new Random();for (int i = 0; i < 1000; i++) {index[i] =(int)(random.nextInt()*1000);}//并归排序效率测试Sort.mergeSort(index,255,658);/*排序耗费的时间为：1ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}
}

快速排序（Quick Sort）

快速排序是平均速度最快的排序方法，思想如下:每趟选中一个元素，并把这个元素插入到它的正确位置。具体是每趟排完之后，选中元素的左边都小于它，右边元素都大于它。然后再分别对其左边部分和右边部分进行快速排序。

排序示例图如下：

java实现：

public static void quickSort(int[] array, int left, int right) {int i, j, t, temp;if (left > right)return;temp = array[left]; //temp中存的就是基准数i = left;j = right;while (i != j) {//顺序很重要，要先从右边开始找while (array[j] >= temp && i < j)j--;//再找右边的while (array[i] <= temp && i < j)i++;//交换两个数在数组中的位置if (i < j) {t = array[i];array[i] = array[j];array[j] = t;}}//最终将基准数归位array[left] = array[i];array[i] = temp;//继续处理左边的，这里是一个递归的过程quickSort(array, left, i - 1);//继续处理右边的 ，这里是一个递归的过程quickSort(array, i + 1, right);}

测试效率：

public class SortTest {public static void main(String[] args) {long startTime = System.currentTimeMillis();int[] index = new int[1000];Random random = new Random();for (int i = 0; i < 1000; i++) {index[i] =(int)(random.nextInt()*1000);}//快速排序效率测试Sort.quickSort(index,0,index.length-1);/*排序耗费的时间为：2ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}
}

桶排序（Bucket Sort）

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间(O(n))。但桶排序并不是比较排序，他不受到 O(n log n) 下线的影响。

桶排序的示例图如下：

代码实现：

/*** 桶排序** @param inputArray 待排序数组*/public static void bucketSort(int[] inputArray) {//获取待排序数组的最大值int maxValue = getMaxValue(inputArray);//初始化桶数组int[] bucketArray = new int[maxValue + 1];//将待排序数组元素放入桶数组中for (int i = 0; i < inputArray.length; i++) {bucketArray[inputArray[i]]++;}//遍历桶数组，将桶中元素放入待排序数组int index = 0;for (int i = 0; i < bucketArray.length; i++) {for (int j = 0; j < bucketArray[i]; j++) {inputArray[index++] = i;}}}/*** 获取数组最大值** @param arr 待排序数组* @return 数组最大值*/public static int getMaxValue(int[] arr) {int maxValue = arr[0];for (int i = 1; i < arr.length; i++) {if (maxValue < arr[i]) {maxValue = arr[i];}}return maxValue;}

测试效率：

public class SortTest {public static void main(String[] args) {long startTime = System.currentTimeMillis();int[] index = new int[1000];Random random = new Random();for (int i = 0; i < 1000; i++) {index[i] =(int)(random.nextInt()*1000);}//桶排序效率测试Sort.bubbleSort(index);/*排序耗费的时间为：4ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}
}

计数排序（Counting Sort）

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)(其中k是整数的范围)，快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序)

计数排序的示例图如下：

代码实现：

/*** 计数排序* @param array*/public static void countSort(int[] array) {int max = array[0];//找出最大值for (int i = 1; i < array.length; i++) {if (max < array[i]) {max = array[i];}}//初始化计数数组int[] countArray = new int[max + 1];for (int i = 0; i < array.length; i++) {countArray[array[i]]++;}//求出每个元素的位置int index = 0;for (int i = 0; i <= max; i++) {while (countArray[i] > 0) {array[index++] = i;countArray[i]--;}}}

测试排序效率：

public class SortTest {public static void main(String[] args) {long startTime = System.currentTimeMillis();int[] sorted = new int[]{12,52,52,1,45,2,6,5,4,1};//计数排序效率测试Sort.countSort(sorted);/*排序耗费的时间为：1ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}
}

这里有个问题，不能像之前用生成随机数那样排序测试，会出现内存溢出问题，具体原因没深究，留个疑问在这😅

基数排序（Radix Sort）

基数排序(radix sort)属于"分配式排序"(distribution sort)，又称"桶子法"(bucket sort)或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些"桶"中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

其大致排序图如下：

实现流程如下：

1，获取数组中最大值，并得到它的位数，作为基数排序的趟数。
2，创建一个临时存储数据的二维数组temp，及一个记录每个数组中存放数据数量的一维数组counts。
3，从右到左，根据最大长度的数决定排序的趟数，把每一个数字按照位数分别解析出来，放入指定的temp数组中，并记录数量。
4，记录取出的元素需要放的位置，把取出的元素放入原数组，把每个数组计数器置零，完成一趟排序。

代码实现：

public static void radixSort(int[] arr){//得到数组中最大的数的位数int max = arr[0];for (int i = 0; i < arr.length; i++) {if (arr[i] > max){max = arr[i];}}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 ys = arr[j] / n % 10;//把解析出来的数放入指定的temp数组中temp[ys][counts[ys]] = arr[j];//记录数量counts[ys]++;}//记录取的元素需要放的位置int index = 0;//把取出的元素放入原数组for (int k = 0; k < counts.length; k++) {//这里的counts[k]是当前的第k个桶中存放的数据个数if (counts[k] != 0){for (int l = 0; l < counts[k]; l++) {//取出元素arr[index++] = temp[k][l];}}//把每个数组计数器置零counts[k] = 0;}}
}

测试排序效率：

public class SortTest {public static void main(String[] args) {long startTime = System.currentTimeMillis();
//        int[] index = new int[10];
//        Random random = new Random();
//        for (int i = 0; i < index.length; i++) {
//            index[i] =(int)(random.nextInt()*10);
//        }int[] index = new int[]{78,1,2,4,5,87,4,6,88,21,2,15,1,5};//基数排序效率测试Sort.baseSort(index);/*排序耗费的时间为：1ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}
}

这里也不能用随机数生成测试，会出现数组下标越界异常……

堆排序（Heap Sort）

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

排下序示意图如下：

可以通过如下流程来得以实现：

1. 从第一个非叶子结点从下至上，从右至左调整结构：此步骤是用来构造大顶堆，从最后一个非叶子结点开始，调整其子树使其满足大顶堆的性质。
2. 将堆顶元素与末尾元素进行交换：将最大的元素放在末尾，即堆排序的基本思想。
3. 重新对堆进行调整：此步骤重新调整树，使其满足大顶堆的性质。
4. 从i结点的左子结点开始，也就是2i+1处开始：从左子结点开始，比较父节点和左右子节点的大小，取最大值与父节点交换，然后继续调整。

代码实现：

    //堆排序，升序public static void heapSort(int[] array) {//1.构建大顶堆for (int i = array.length / 2 - 1; i >= 0; i--) {//从第一个非叶子结点从下至上，从右至左调整结构adjustHeap(array, i, array.length);}//2.调整堆结构+交换堆顶元素与末尾元素for (int j = array.length - 1; j > 0; j--) {//将堆顶元素与末尾元素进行交换int temp = array[j];array[j] = array[0];array[0] = temp;//重新对堆进行调整adjustHeap(array, 0, j);}}/*** 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）* @param array* @param i* @param length*/public static void adjustHeap(int[] array, int i, int length) {int temp = array[i];//先取出当前元素ifor (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始if (k + 1 < length && array[k] < array[k + 1]) {//如果左子结点小于右子结点，k指向右子结点k++;}if (array[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）array[i] = array[k];i = k;} else {break;}}array[i] = temp;//将temp值放到最终的位置}

测试结果：

 public static void main(String[] args) {long startTime = System.currentTimeMillis();int[] index = new int[1000];Random random = new Random();for (int i = 0; i < index.length; i++) {index[i] =(int)(random.nextInt()*1000);}
//        int[] index = new int[]{78,1,2,4,5,87,4,6,88,21,2,15,1,5};//堆排序效率测试SortTest.heapSort(index);/*排序耗费的时间为：2ms*/System.out.println("排序耗费的时间为："+(System.currentTimeMillis()-startTime)+"ms");}