0、排序算法说明 0.1 排序的定义： 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面； 不稳定 ：如果a原本在b的前面，而
0、排序算法说明
0.1 排序的定义： 对一序列对象根据某个关键字进行排序。
0.2 术语说明
- 稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
- 不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
- 内排序 ：所有排序操作都在内存中完成；
- 外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
- 时间复杂度 ： 一个算法执行所耗费的时间。
- 空间复杂度 ：运行完一个程序所需内存的大小。
0.3 算法总结
比较和非比较的区别
常见的快速排序、归并排序、堆排序、冒泡排序 等属于比较排序 。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置 。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
计数排序、基数排序、桶排序则属于非比较排序 。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置 。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
1、冒泡排序（Bubble Sort）
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.3 代码实现
1.1 算法描述
- 步骤1: 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 步骤2: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 步骤3: 针对所有的元素重复以上的步骤，除了最后一个；
- 步骤4: 重复步骤1~3，直到排序完成。
1.2 动图演示
/** * 冒泡排序算法默写 * * @param number * @return */public static int[] BubboSort2(int[] number) { for (int i = number.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (number[j] > number[j + 1]) { int temp = number[j]; number[j] = number[j + 1]; number[j + 1] = temp; } } } return number;}//交换函数public static int[] swap(int a, int b) { a = a + b; b = a - b; a = a - b; return new int[]{a, b}; }
2、选择排序（Selection Sort）
选择排序 是表现最稳定的排序算法之一 ，因为无论什么数据进去都是O(n2)的时间复杂度 ，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
2.3 代码实现
2.1 算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下： 步骤1：初始状态：无序区为R[1…n]，有序区为空； 步骤2：第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区； 步骤3：n-1趟结束，数组有序化了。 2.2 动图演示
/** * Copyright (C), 2018-2020 * FileName: SelectionSort * Author: xjl * Date: 2020/5/31 21:41 * Description: 选择排序 */package 计算机程序算法分类.排序算法;import org.junit.Test;public class 选择排序 { /** * 选择排序 * * @param a */ public static void sort(int[] a) { for (int i = 0; i < a.length - 2; i++) { //定义一个变量 记录最小的所在的索引 默认是选择排序的第一个元素所在的位置的 int minindex = i; for (int j = i + 1; j < a.length; j++) { if (geeratr(a[minindex], a[j])) { minindex = j; } } //交换最小的元素的位置的值 exch(a, i, minindex); } } private static boolean geeratr(int V, int W) { if (V - W < 0) { return true; } return false; } private static void exch(int[] a, int i, int j) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } @Test public void test() { int[] a = {1, 5, 8, 6, 12, 0, 58}; sort(a); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } }}
3、插入排序（Insertion Sort）
插入排序（Insertion-Sort） 的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
3.1 算法描述
- 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 步骤1: 从第一个元素开始，该元素可以认为已经被排序；
- 步骤2: 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 步骤3: 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 步骤4: 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 步骤5: 将新元素插入到该位置后；
- 步骤6: 重复步骤2~5。
3.2 动图演示
/** * Copyright (C), 2018-2020 * FileName: InsertSort * Author: xjl * Date: 2020/3/19 15:28 * Description: c插入排序 */package 计算机程序算法分类.排序算法;import org.junit.Test;public class 插入排序 { public static int[] Insertsort(int[] number) { for (int i = 1; i < number.length; i++) { for (int j = i; j >0; j--) { if (number[j-1]>number[j]) { int temp = number[j]; number[j - 1] = number[j]; number[j] = temp; } else { break; } } } return number; }}
4、希尔排序（Shell Sort）
希尔排序是希尔（Donald Shell） 于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。 希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
4.1 算法描述
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述： 步骤1：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 步骤2：按增量序列个数k，对序列进行k 趟排序； 步骤3：每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。 4.2 过程演示
/** * Copyright (C), 2018-2020 * FileName: ShellSort * Author: xjl * Date: 2020/6/4 15:56 * Description: 希尔排序原理 */package 计算机程序算法分类.排序算法;import java.util.Arrays;/** * 希尔排序的原理 * 1 选定一个增长量 按照增长量h作为数据的分组的依据 对数据进行分组 * 2 按照分好组的每一个组的数据完成的插入的排序 * 3 减少增长量 最下减少为1 重复第二步骤 * 增长量的确定：增长量的h的值的选择规则是： * <p> * int h=1; * while(h<数组的长度/2){ * h=2*h+1; } * <p> * h的减少的规则是 * h=h/2; */public class 希尔排序 { /** * 希尔排序的原理 * * @param a */ public static void sort(int[] a) { //根据数据的a 的长度确定的增长量 int h = 1; while (h < a.length / 2) { h = 2 * h + 1; } //希尔排序 while (h >= 1) { //找到带插入的元素 for (int i = h; i < a.length; i++) { //把带插入的元素插入到有序的数列中 for (int j = i; j >= h; j -= h) { //带插入的元素是的啊a[j] 比较 a[j-h] if (generate(a[j - h], a[j])) { exch(a, j - h, j); } else { break; } } } for (int V : a) { System.out.print(V + " "); } System.out.println(); //减少hd的值 h = h / 2; } } /** * 比较大小的函数 * * @param v * @param w * @return */ private static boolean generate(int v, int w) { return v - w > 0; } /** * 交换的函数 * * @param a * @param i * @param j */ private static void exch(int[] a, int i, int j) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args) { int[] array = {25, 84, 21, 47, 15, 27, 68, 35, 20}; sort(array); System.out.println(Arrays.toString(array)); }}
5、归并排序（Merge Sort）
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。 归并排序 是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
5.1 算法描述 步骤1：把长度为n的输入序列分成两个长度为n/2的子序列； 步骤2：对这两个子序列分别采用归并排序； 步骤3：将两个排序好的子序列合并成一个最终的排序序列。 5.2 动图演示
/** * Copyright (C), 2018-2020 * FileName: MergerSort * Author: xjl * Date: 2020/6/4 16:24 * Description: 归并的排序的原理 */package 计算机程序算法分类.排序算法;import java.util.Arrays;public class 归并排序 { //完成归并排序需要设置的辅助数组 private static int[] assit; //归并排序的调用函数 public static void sort(int[] a) { //初始化数组assit assit = new int[a.length]; //定义一个lo变量和hi变量 分别是记录数组中最小的索引和最大的索引 int lo = 0; int hi = a.length - 1; //调用的sort的重载方法到lo 和hi的元素进行排序 sort(a, lo, hi); } //归并排序的分割函数 public static void sort(int[] a, int lo, int hi) { //做个安全的校验 if (hi <= lo) { return; } //对数据lo 和hi的数据进行分组 int mind = lo + (hi - lo) / 2; //分别是对每一个数据进行排序 sort(a, lo, mind); sort(a, mind + 1, hi); //在将两个组中的数据进行归并 merge(a, lo, mind, hi); } //归并排序的合并函数 public static void merge(int[] a, int lo, int mid, int hi) { //定义三个指针 int i = lo; int p1 = lo; int p2 = mid + 1; //遍历 移动平p1指针和p2指针 比较对应的索引的值，找出最小的那个 放置到辅助的数组的对应的索引的处 while (p1 <= mid && p2 <= hi) { if (less(a[p1], a[p2])) { assit[i++] = a[p1++]; } else { assit[i++] = a[p2++]; } } //遍历 如果是p1的指针没有走完，那么继续针移动p1指针，对应的元素带放到辅助数组的对应的索引 while (p1 <= mid) { assit[i++] = a[p1++]; } //遍历 如果是p2的指针没有走完，那么继续激动p2指针，将对应的元素放到辅助数组的对应的索引处 while (p2 <= hi) { assit[i++] = a[p2++]; } //把辅助数组的元素拷贝的原数组中 for (int index = lo; index <= hi; index++) { a[index] = assit[index]; } } //函数的比较函数 public static boolean less(int v, int w) { return v - w < 0; } //交换函数 public static void excht(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args) { int[] array = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5}; sort(array); System.out.println(Arrays.toString(array)); }}
6、快速排序（Quick Sort）
快速排序 的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
6.1 算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下： 步骤1：从数列中挑出一个元素，称为 “基准”（pivot ）； 步骤2：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作； 步骤3：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 6.2 动图演示
/** * Copyright (C), 2018-2020 * FileName: QuickSort * Author: xjl * Date: 2020/6/11 15:55 * Description: 快速排序 */package 计算机程序算法分类.排序算法;import java.util.Arrays;import java.util.Scanner;public class 快速排序 { //对数组的元素进行排序 public static void sort(int[] a) { int lo = 0; int hi = a.length - 1; sort(a, lo, hi); } //对数组a中从索引lo到hi之间的元素进行排序 public static void sort(int[] a, int lo, int hi) { if (hi <= lo) { return; } //需要对lo到hi的元素进行分组（左数组 右数组） int partition = partition(a, lo, hi);//返回的分界的索引 //让左数组有序 sort(a, lo, partition - 1); //让右数组有序 sort(a, partition + 1, hi); } //对数组a中的从lo到hi之间的元素进行分组 并返回分组界限的对应的索引 public static int partition(int[] a, int lo, int hi) { //确定分界值 int key = a[lo]; //定义两个指针 分别指向代切分的最小的元素的索引的下一个位置 int left = lo; int right = hi + 1; //切分 while (true) { //先从右向左扫描 移动right 找到一个分界值小的元素 停止 while (less(key, a[--right])) { if (right == lo) { break; } } //在从左向右边扫描 移动left 找到一个分界值大的元素 停止 while (less(a[++left], key)) { if (left == hi) { break; } } //判断left是否大于right 如果是表示的扫描完毕 如果不是的交换元素就好 if (left >= right) { break; } else { exch(a, left, right); } } //把分割的点和第一元素进行交换 exch(a, lo, right); return right; } public static boolean less(int v, int w) { if (v - w < 0) { return true; } else { return false; } } public static void exch(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args) { //数据的输入 Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int[] array = new int[m]; for (int i = 0; i < m; i++) { array[i] = sc.nextInt(); } sort(array); System.out.println(Arrays.toString(array)); }}
7、堆排序（Heap Sort）
堆排序（Heapsort） 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
7.1 算法描述 步骤1：将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； 步骤2：将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]； 步骤3：由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
7.2 动图演示
//声明全局变量，用于记录数组array的长度； static int len; /** * 堆排序算法 * * @param array * @return */ public static int[] HeapSort(int[] array) { len = array.length; if (len < 1) return array; //1.构建一个最大堆 buildMaxHeap(array); //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆 while (len > 0) { swap(array, 0, len - 1); len--; adjustHeap(array, 0); } return array; } /** * 建立最大堆 * * @param array */ public static void buildMaxHeap(int[] array) { //从最后一个非叶子节点开始向上构造最大堆 //for循环这样写会更好一点：i的左子树和右子树分别2i+1和2(i+1) for (int i = (len/2- 1); i >= 0; i--) { adjustHeap(array, i); } } /** * 调整使之成为最大堆 * * @param array * @param i */ public static void adjustHeap(int[] array, int i) { int maxIndex = i; //如果有左子树，且左子树大于父节点，则将最大指针指向左子树 if (i * 2 < len && array[i * 2] > array[maxIndex]) maxIndex = i * 2 + 1; //如果有右子树，且右子树大于父节点，则将最大指针指向右子树 if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) maxIndex = i * 2 + 2; //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。 if (maxIndex != i) { swap(array, maxIndex, i); adjustHeap(array, maxIndex); } }
8、计数排序（Counting Sort）
计数排序 的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序(Counting sort) 是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
8.1 算法描述
- 步骤1：找出待排序的数组中最大和最小的元素；
- 步骤2：统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 步骤3：对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 步骤4：反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
8.2 动图演示
/** * 计数排序 * * @param array * @return */ public static int[] CountingSort(int[] array) { if (array.length == 0) return array; int bias, min = array[0], max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) max = array[i]; if (array[i] < min) min = array[i]; } bias = 0 - min; int[] bucket = new int[max - min + 1]; Arrays.fill(bucket, 0); for (int i = 0; i < array.length; i++) { bucket[array[i] + bias]++; } int index = 0, i = 0; while (index < array.length) { if (bucket[i] != 0) { array[index] = i - bias; bucket[i]--; index++; } else i++; } return array; }
9、桶排序（Bucket Sort）
桶排序 是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理： 假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
9.1 算法描述
- 步骤1：人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
- 步骤2：遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 步骤3：对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
- 步骤4：从不是空的桶里把排好序的数据拼接起来。
注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。 9.2 图片演示
/** * 桶排序 * * @param array * @param bucketSize * @return */ public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) { if (array == null || array.size() < 2) return array; int max = array.get(0), min = array.get(0); // 找到最大值最小值 for (int i = 0; i < array.size(); i++) { if (array.get(i) > max) max = array.get(i); if (array.get(i) < min) min = array.get(i); } int bucketCount = (max - min) / bucketSize + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); ArrayList<Integer> resultArr = new ArrayList<>(); for (int i = 0; i < bucketCount; i++) { bucketArr.add(new ArrayList<Integer>()); } for (int i = 0; i < array.size(); i++) { bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i)); } for (int i = 0; i < bucketCount; i++) { if (bucketSize == 1) { // 如果带排序数组中有重复数字时 for (int j = 0; j < bucketArr.get(i).size(); j++) resultArr.add(bucketArr.get(i).get(j)); } else { if (bucketCount == 1) bucketSize--; ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize); for (int j = 0; j < temp.size(); j++) resultArr.add(temp.get(j)); } } return resultArr; }
10、基数排序（Radix Sort）
基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
10.1 算法描述
- 步骤1：取得数组中的最大数，并取得位数；
- 步骤2：arr为原始数组，从最低位开始取每个位组成radix数组；
- 步骤3：对radix进行计数排序（利用计数排序适用于小范围数的特点）；
10.2 动图演示
/** * 基数排序 * @param array * @return */ public static int[] RadixSort(int[] array) { if (array == null || array.length < 2) return array; // 1.先算出最大数的位数； int max = array[0]; for (int i = 1; i < array.length; i++) { max = Math.max(max, array[i]); } int maxDigit = 0; while (max != 0) { max /= 10; maxDigit++; } int mod = 10, div = 1; ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < 10; i++) bucketList.add(new ArrayList<Integer>()); for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) { for (int j = 0; j < array.length; j++) { int num = (array[j] % mod) / div; bucketList.get(num).add(array[j]); } int index = 0; for (int j = 0; j < bucketList.size(); j++) { for (int k = 0; k < bucketList.get(j).size(); k++) array[index++] = bucketList.get(j).get(k); bucketList.get(j).clear(); } } return array; }
