大家好，我是讯享网，很高兴认识大家。

一、冒泡排序

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
冒泡排序优化： 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在 排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。

第一趟排序
(1) 3, 9, -1, 10, 20 // 如果相邻的元素逆序就交换
…
(4) 3, -1, 9, 10, 20 //4次循环之后20就到了最后

第二趟排序
(1) -1, 3, 9, 10, 20 //交换
…
(3) -1, 3, 9, 10, 20 //3次循环之后10就到了倒数第二个数

总结：

1. 正常情况下要循环数组长度-1次
2. 每一次的排序次数在逐渐的减少
3. 如果某一次排序在前一次的基础上没有改变，既没有发生交换，可以提前结束冒泡

代码实现：

public int[] bubbleSort(int[] arr){ 
    int temp = 0; boolean flag = false; //表示是否已经按顺序排列好了 for (int i = 0; i < arr.length - 1; i++) { 
    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 = true; } } // System.out.printf("第%d次排序\n",i+1); // System.out.println(Arrays.toString(arr)); if (!flag){ 
    break; }else { 
    flag = false; } } return arr; } 

讯享网

讯享网int[] arr = new int[]; for (int i = 0; i < arr.length; i++) { 
    arr[i] = (int)(Math.random()*); } long start = System.currentTimeMillis(); BubbleSort bs = new BubbleSort(); // 冒泡排序 int[] bsArr = bs.bubbleSort(arr); Long end = System.currentTimeMillis(); System.out.println("排序花费时长 time = "+ ((double)end - (double)start)/1000 +"s" ); 

二、选择排序

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
选择排序（select sorting）的基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值，
与 arr[0]交换，第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2] 交换，…，第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值， 与 arr[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。

举例说明：
原始的数组 ： 5, 10, 7, 1
第一轮排序 : 1, 10, 7, 5 // 交换1和5
第二轮排序 : 1, 5, 7, 10 // 交换5和10

代码实现：

public int[] selectSort(int[] arr){ 
    for (int i = 0; i < arr.length-1; i++) { 
    int minIndex = i; // 初始最小值下表（假定每一轮的第一个值为最小值） int min = arr[i]; // 初始最小值 for (int j = i; j < arr.length-1; j++) { 
    if (min > arr[j+1]){ 
    minIndex = j+1; // 改变最小值索引 min = arr[j+1]; } } if (minIndex != i){ 
    // 最小值已经改变，将最小值与第一个位置进行交换 arr[minIndex] = arr[i]; arr[i] = min; } } return arr; } 

速度比冒泡排序快了很多。
稳定性差：在一趟选择。假设一个元素比当前元素小。而该小的元素又出如今一个和当前元素相等的元素后面。那么交换后稳定性就被破坏了。
例如：
序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

三、插入排序（直接插入排序）

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排 序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
图解过程：

讯享网
代码实现：

讯享网public int[] insertSort(int[] arr){ 
    for (int i = 1; i < arr.length; i++) { 
    // 从一开始，前面的第一个数为有序数，后面的数与前面的有序数进行比较 int insertValue = arr[i]; // 待插入的数 int insertIndex = i - 1; // 待插入数前面一个数的索引 // insertIndex >= 0 索引不能越界 // insertIndex < arr[i] 从有序的的最后一位向前进行比较 while (insertIndex >= 0 && insertValue < arr[insertIndex]){ 
    arr[insertIndex+1] = arr[insertIndex]; // 将比要插入数大的向后移动 insertIndex--; // 索引向前移动 } arr[insertIndex+1] = insertValue; // 将要插入的数放在找到的位置 } return arr; } 

速度比冒泡和选择排序快了很多

这样速度的确很快，但是简单的插画如排序可能存在问题：
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.
基于这种情况，就产生了希尔排序

四、希尔排序

希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
举例图：


希尔排序插入时可以使用交换法或移动法。（一般使用移动法，移动法更加高效）

交换法实现：

 public int[] shellSort1(int[] arr){ 
    int temp = 0; for (int gap = arr.length/2; gap >0 ; gap /= 2) { 
    // 每次步长减半 for (int i = gap; i < arr.length; i++){ 
    for (int j = i - gap; j >= 0; j -= gap){ 
    //遍历各组中所有元素 if (arr[j] > arr[j + gap]){ 
    // 交换 temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } } return arr; } 

移动法实现：

讯享网public int[] shellSort2(int[] arr){ 
    for (int gap = arr.length/2; gap >0 ; gap /= 2) { 
    // 每次步长减半 for (int i = gap; i < arr.length; i++) { 
    // 从第gap个元素，逐个对其所在的组进行直接插入排序 int insertIndex = i; int insertValue = arr[insertIndex]; while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]){ 
    arr[insertIndex] = arr[insertIndex - gap]; insertIndex -= gap; } arr[insertIndex] = insertValue; } } return arr; } 

交换法测试：
时间复杂度：O(n^s) (1<s<2)
统计排序一千万个数据所需要的时间：

移动法测试：
时间复杂度：O(n^s) (1<s<2)
统计排序一千万个数据所需要的时间：

排序花费时长 time = 3.067s （直接进行一千万数据排序）

可以看出希尔排序（插入法）比直接插入排序更加高效

五、快速排序

快速排序（Quicksort） 是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排 序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

图解：

代码实现：

public void quickSort(int[] arr, int left, int right){ 
    if (left >= right){ 
    return ; } int l = left; int r = right; int temp = arr[right]; int t = 0;// 作为交换变量 while (l < r){ 
    while (arr[l] <= temp && l < r){ 
    // 从左边向右寻找大于等于temp的数 l++; } while (arr[r] >= temp && l < r){ 
    // 从右向左寻找小于等于temp的数 r--; } if (l < r){ 
    //交换 t = arr[l]; arr[l] = arr[r]; arr[r] = t; } } arr[right] = arr[l]; arr[l] = temp; quickSort(arr, left, r-1);//向左递归 quickSort(arr, l+1, right);// 向右递归 } 

速度比冒泡快了许多倍。
这里选择的是最右端的数作为基数，也可以选择中间的数作为基数
参考这篇快速排序

六、归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修 补"在一起，即分而治之)。
图解归并排序：

分： 迭代进行拆分就好了。
治： 将“分”的数据进行合并，合并按顺序排列。以上图最后一次合并为例：


合并之后的数据就是排序好的数据。

代码实现：

讯享网public void mergeSort(int[] arr, int[] temp, int left, int right){ 
    if (left < right){ 
    int mid = (left + right) / 2; // 向左递归分解 mergeSort(arr, temp, left, mid); // 向右递归分解 mergeSort(arr, temp, mid + 1, right); merge(arr, temp, left, right, mid); } } public void merge(int[] arr, int[] temp, int left, int right, int mid){ 
    int i = left; int j = mid + 1; int t = 0; // 1.比较两个两部分每一个的大小，知道有一部分数据全部加入temp while (i <= mid && j <= right){ 
    if (arr[i] < arr[j]){ 
    temp[t] = arr[i]; i++; }else { 
    temp[t] = arr[j]; j++; } t++; } // 2.将剩余的那一部分的全部加入temp while (i <= mid){ 
    // 若前面的部分剩余,将前面那部分剩余的全部加入 temp[t] = arr[i]; i++; t++; } while (j <= right){ 
    // 若后面的部分剩余，则将后面的的部分全部加入 temp[t] = arr[j]; j++; t++; } // 3.将temp的数全部拷贝到arr中 t = 0; int tempLeft = left; while (tempLeft <= right){ 
    arr[tempLeft] = temp[t]; t++; tempLeft++; } } 

七、基数排序

1. 基数排序（radix sort） 属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的目的。
2. 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3. 基数排序(Radix Sort)是桶排序的扩展
4. 基数排序是 1887 年赫尔曼·何乐礼发明的。实现方式：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

图文解释：
将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序。
第一轮排序：

将桶中的数据取出之后放入数组中进行第二轮排序：

将桶中的数据取出之后放入数组中进行第三轮排序
排序轮数 = 最大值位数

代码实现：

public 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();//最大值的长度 // 初始化一个二维数据，二维数组的没一个数组都是一个桶，因为无法确定每一个桶会装多少个数据，所以设置为arr.lenth int[][] bucket = new int[10][arr.length]; // 初始化一个一维数组用于保存桶保存的数的个数 int [] bucketElementCounts = new int[10]; for (int i = 0, n = 1; i < maxLength; i++, n *= 10) { 
    // i控制循环次数，n控制每次取得的位数 for (int j = 0; j < arr.length; j++) { 
    // 循环每个数，按照规则放入桶内 int digitalOfElement = arr[j] / n % 10; // 每次取模得到相应位数的值 bucket[digitalOfElement][bucketElementCounts[digitalOfElement]] = arr[j]; bucketElementCounts[digitalOfElement]++; } int index = 0;//存放数据的索引 for (int k = 0; k < bucket.length; k++) { 
    // 循环所有桶 if (bucketElementCounts[k] != 0){ 
    // 不为空的桶 for (int m = 0; m < bucketElementCounts[k]; m++) { 
    // 将桶的元素放入数组 arr[index++] = bucket[k][m]; } } bucketElementCounts[k] = 0;//清空桶 } } } 

说明：

1. 基数排序是对传统桶排序的扩展，速度很快.
2. 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
3. 基数排序是稳定的。[注:稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些 记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前， 则称这种排序算法是稳定的；否则称为不稳定的]
4. 有负数的数组，我们不用基数排序来进行排序, 如果要使用，将数组中的负数整数分开，使它们成为正数，然后使用基数排序为正值，然后反转并附加排序后的非负数组。

八、堆排序

堆排序要应用顺序存储二叉树原理：
顺序存储二叉树：从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。

上图将二叉树转换为数组存储。

顺序存储二叉树特点：

1. 顺序二叉树通常只考虑完全二叉树
2. 第 n 个元素的左子节点为 2 * n + 1
3. 第 n 个元素的右子节点为 2 * n + 2
4. 第 n 个元素的父节点为 (n-1) / 2
5. n : 表示二叉树中的第几个元素(按 0 开始编号如图所示)

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复 杂度均O(nlogn)，它也是不稳定排序。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
大顶堆：

对堆中的结点按层进行编号，映射到数组中就是下面这个样子:

大顶堆特点：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点，i从0开始编号
小顶堆：

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点，i从0开始编号
一般升序采用大顶堆，降序采用小顶堆

堆排序基本思路：

1. 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

1. 有无序结构 {4，6，8，5，9}
   
2. 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

3. 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

4. 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无序序列构造成了一个大顶堆。

接下来进行第二步：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

1. 将堆顶元素9和末尾元素4进行交换
   
2. 重新调整结构，使其继续满足堆定义
   
3. 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

4. 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

代码实现：

讯享网/ * @Description: heapSort 堆排序 * @param: [arr] * @return: void * @auther: z * @date: 20/6/20 17:10 */ public void heapSort(int[] arr){ 
    int temp = 0; // 第一次调整：将最大是数调整为根节点 // arr.length/2 - 1 :为第一个非叶子节点 for (int i = arr.length/2 - 1; i >= 0; i--) { 
    adjustHeap(arr, i, arr.length); } for (int i = arr.length-1 ; i > 0; i--) { 
    temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; // 为什么这里的的第二个参数写死是0 ？ // 因为经过第一次调整之后，再经过交换，就只有很根节点不是一个大顶堆， // 所以只需要进行简单的与根节点交换就好，而不需要在进行整体的一个大顶堆的构造 adjustHeap(arr, 0, i); } } / * @Description: adjustHeap 调整以i为非叶子节点的局部子树，使得父节点的值大于子节点的值 * @param: [arr 待调整的数组, i 表示非叶子节点的索引, length：表示有多少元素调整] * @return: void * @auther: z * @date: 20/6/20 16:22 */ public void adjustHeap(int[] arr, int i, int length){ 
    int temp = arr[i]; // k = i * 2 + 1：表示i这个节点的左子树 for (int k = i * 2 + 1; k < arr.length; k = k * 2 + 1) { 
    if (k + 1 < length && arr[k] < arr[k+1]){ 
    // 比较左右子节点的大小，将k指向较大的拿一个节点 k++; } if (arr[k] > temp){ 
    // 子节点大于父节点 arr[i] = arr[k];//交换数据第一步：子节点的值给父节点 i = k ;//将i指向调整后的子节点，用于循环结束后交换数据 }else { 
    break; } } arr[i] = temp;//交换数据第二步 } 

九、桶排序

桶排序也是时间复杂度仅为 O(n) 的一种排序方法，它假设输入数据服从均匀分布，我们将数据分别放入到 n 个桶内，先对桶内数据进行排序，然后遍历桶依次取出桶中的元素即可完成排序。

1. 选择合适个数的桶（我是用的是(max - min)/arr.length + 1）
2. 将一定范围的数据放入相应的桶内，插入桶内时要进行排序
3. 依次将桶内元素拷贝到原数组中
   图解：
   对 {21，8，6，11，36，50，27，42，0，12} 排序
   

public void bucketSort(int[] arr){ 
    int min = arr[0]; int max = arr[0]; for (int i = 0; i < arr.length; i++) { 
    // 找出最大值与最小值 min = Math.min(min,arr[i]); max = Math.max(max,arr[i]); } int bucketNumber = (max - min)/arr.length + 1; // 桶的数量 ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(); // 存储每一个桶 ArrayList<Integer> bucket = null; for (int i = 0; i < bucketNumber; i++) { 
    // 将没一个桶放入buckets中 bucket = new ArrayList<Integer>(); buckets.add(bucket); } for (int item : arr) { 
    // 循环数据插入到桶 ArrayList<Integer> bc = buckets.get((item - min) / arr.length); // (item - min) / arr.length 表示桶的位置 insert(bc, item); // 插入桶（桶内排序） } int index = 0; // 索引数组 for (ArrayList<Integer> bc : buckets) { 
    // 循环每一个桶 for (Integer item : bc) { 
    // 循环桶内的数据 arr[index++] = item; // 依次将桶内的数据取出 } } } public void insert(ArrayList<Integer> bc, int item){ 
    ListIterator<Integer> itl = bc.listIterator(); boolean flag = true; while (itl.hasNext()){ 
    if (item <= itl.next()){ 
    itl.previous(); // 将迭代器的位置偏移到上一位 itl.add(item); // 将数据插入到迭代器当前的位置上 flag = false; break; } } if (flag){ 
    // 否在九八数据插插入到末端 bc.add(item); } } 

十、计数排序

计数排序适用于有明确范围的数组，比如给定一个数组，且知道所有值得范围是[m,n]。这个时候可以使用一个n-m+1长度的数组，待排序的数组就可以散在这个数组上，数组的值就是当前值的个数，再经过一次遍历展开，得到的数组就有序了。
计数排序过程：

1. 新建一个长度为n-m+1的临时数组
2. 遍历待排序数组，它的值-m作为临时数组下角标，这个位置的值加1
3. 遍历结束，临时数组就存储了每个值得个数
4. 最后将它展开赋值给原数组
   计数排序图解：
   
   代码实现：

讯享网public void countSort(int[] arr){ 
    int min = arr[0]; int max = arr[0]; for (int i = 0; i < arr.length; i++) { 
    // 找出最大值与最小值 if (arr[i] > max){ 
    max = arr[i]; }else if (arr[i] < min){ 
    min = arr[i]; } } int[] counts = new int[max - min + 1];// 计数空间 for (int i = 0; i < arr.length; i++) { 
    // 将每一个数减去最小值统计到临时数组中 counts[arr[i] - min] += 1; // arr[i]-min对应计数空间的下表 } for (int i = 0,index =0; i < counts.length; i++) { 
    int item = counts[i];//每一个数对应的统计量 while (item-- != 0){ 
    // 直到每一个数的统计量归零 arr[index++] = i + min; // 将原来的数展开放到原数组中，展开就是按照大小排列 } } } 

参考的计数排序

总：常用排序算法总结比较

• In-place: 不占用额外内存
• Out-place: 占用额外内存

比较排序和非比较排序的区别：

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

---

附所有排序代码：

public class Sort { 
    public static void main(String[] args) { 
    int[] arr = new int[]; for (int i = 0; i < arr.length; i++) { 
    arr[i] = (int)(Math.random()*); } // Date date1 = new Date(); // SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); // String formatDateStart = simpleDateFormat.format(date1); // System.out.println("开始排序前="+formatDateStart); long start = System.currentTimeMillis(); Sort bs = new Sort(); // 冒泡排序 //int[] bsArr = bs.bubbleSort(arr); // 选择排序 // int[] selectSort = bs.selectSort(arr); // 插入排序 // int[] insertSort = bs.insertSort(arr); // 希尔排序：交换法 //int[] shellSort1 = bs.shellSort1(arr); // 希尔排序：移动法 // int[] shellSort2 = bs.shellSort2(arr); // 快速排序 // bs.quickSort(arr, 0, arr.length-1); // 归并排序 // int[] temp = new int[arr.length]; // bs.mergeSort(arr, temp, 0, arr.length-1); // 基数排序 // bs.radixSort(arr); // 计数排序 // bs.countSort(arr); // 桶排序 // bs.bucketSort(arr); // 堆排序 bs.heapSort(arr); Long end = System.currentTimeMillis(); System.out.println("排序花费时长 time = "+ ((double)end - (double)start)/1000 +"s" ); // Date date2 = new Date(); // String formatDateEnd = simpleDateFormat.format(date2); // System.out.println("完成排序后="+formatDateEnd); // 选择排序 // int[] arr = {-1,9,1,5,7,6,2}; // System.out.println("排序前="+Arrays.toString(arr)); // int[] selectSort = bs.selectSort(arr); // System.out.println("排序后="+Arrays.toString(selectSort)); // 选择排序 // int[] arr2 = {-1,9,1,5,7,6,2}; // System.out.println("排序前="+Arrays.toString(arr2)); // int[] insertSort = bs.insertSort(arr2); // System.out.println("排序后="+Arrays.toString(insertSort)); // 希尔排序 // int[] arr2 = {-1,9,1,5,7,6,2}; // System.out.println("排序前="+Arrays.toString(arr2)); // int[] shellSort1 = bs.shellSort1(arr2); // int[] shellSort2 = bs.shellSort1(arr2); // System.out.println("排序后="+Arrays.toString(shellSort1)); // System.out.println("排序后="+Arrays.toString(shellSort2)); // 快速排序 // int[] arr2 = {-1,9,8,5,7,6,5}; // bs.quickSort(arr2, 0, arr2.length - 1); // System.out.println("Arrays.toString(arr2) = " + Arrays.toString(arr2)); // 归并排序 // int[] arr2 = {-1,9,8,5,7,6,5}; // int[] temp = new int[arr.length]; // bs.mergeSort(arr2, temp,0, arr2.length-1); // System.out.println("Arrays.toString(arr2) = " + Arrays.toString(arr2)); // 基数排序 // int[] arr2 = {1,9,8,5,7,6,50}; // bs.radixSort(arr2); // System.out.println("Arrays.toString(arr2) = " + Arrays.toString(arr2)); // 计数排序 // int[] arr2 = {1,9,8,5,7,6,50}; // bs.countSort(arr2); // System.out.println("Arrays.toString(arr2) = " + Arrays.toString(arr2)); //桶排序 // int[] arr2 = {1,9,8,5,7,6,50}; // bs.bucketSort(arr2); // System.out.println("Arrays.toString(arr2) = " + Arrays.toString(arr2)); //堆排序 int[] arr2 = { 
   1,9,8,5,7,6,50}; bs.heapSort(arr); System.out.println("Arrays.toString(arr2) = " + Arrays.toString(arr2)); } / * @Description: 冒泡排序 * @param: * @return: * @auther: z * @date: 20/6/15 18:23 */ public int[] bubbleSort(int[] arr){ 
    int temp = 0; boolean flag = false; //表示是否已经按顺序排列好了 for (int i = 0; i < arr.length - 1; i++) { 
    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 = true; } } // System.out.printf("第%d次排序\n",i+1); // System.out.println(Arrays.toString(arr)); if (!flag){ 
    break; }else { 
    flag = false; } } return arr; } / * @Description: selectSort 选择排序 * @param: [arr] * @return: int[] * @auther: z * @date: 20/6/15 18:32 */ public int[] selectSort(int[] arr){ 
    for (int i = 0; i < arr.length-1; i++) { 
    int minIndex = i; // 初始最小值下表（假定每一轮的第一个值为最小值） int min = arr[i]; // 初始最小值 for (int j = i; j < arr.length-1; j++) { 
    if (min > arr[j+1]){ 
    minIndex = j+1; // 改变最小值索引 min = arr[j+1]; } } if (minIndex != i){ 
    // 最小值已经改变，将最小值与第一个位置进行交换 arr[minIndex] = arr[i]; arr[i] = min; } } return arr; } / * @Description: 插入排序 * @param: * @return: * @auther: z * @date: 20/6/15 21:59 */ public int[] insertSort(int[] arr){ 
    for (int i = 1; i < arr.length; i++) { 
    // 从一开始，前面的第一个数为有序数，后面的数与前面的有序数进行比较 int insertValue = arr[i]; // 待插入的数 int insertIndex = i - 1; // 待插入数前面一个数的索引 // insertIndex >= 0 索引不能越界 // insertIndex < arr[i] 从有序的的最后一位向前进行比较 while (insertIndex >= 0 && insertValue < arr[insertIndex]){ 
    arr[insertIndex+1] = arr[insertIndex]; // 将比要插入数大的向后移动 insertIndex--; // 索引向前移动 } if (insertIndex+1 != i){ 
    // 不等时，待插入的数据才不是在待插入数据原来的位置 arr[insertIndex+1] = insertValue; // 将要插入的数放在找到的位置 } } return arr; } / * @Description: shellSort1 希尔排序，交换式 * @param: [arr] * @return: int[] * @auther: z * @date: 20/6/15 22:57 */ public int[] shellSort1(int[] arr){ 
    int temp = 0; for (int gap = arr.length/2; gap >0 ; gap /= 2) { 
    // 每次步长减半 for (int i = gap; i < arr.length; i++){ 
    for (int j = i - gap; j >= 0; j -= gap){ 
    //遍历各组中所有元素 if (arr[j] > arr[j + gap]){ 
    // 交换 temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } } return arr; } / * @Description: shellSort2 希尔排序，插入式 * @param: [arr] * @return: int[] * @auther: z * @date: 20/6/15 23:09 */ public int[] shellSort2(int[] arr){ 
    for (int gap = arr.length/2; gap >0 ; gap /= 2) { 
    // 每次步长减半 for (int i = gap; i < arr.length; i++) { 
    // 从第gap个元素，逐个对其所在的组进行直接插入排序 int insertIndex = i; int insertValue = arr[insertIndex]; while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]){ 
    arr[insertIndex] = arr[insertIndex - gap]; insertIndex -= gap; } arr[insertIndex] = insertValue; } } return arr; } / * @Description: quickSort 快速排序 * @param: [arr, left, right] * @return: void * @auther: z * @date: 20/6/16 12:51 */ public void quickSort(int[] arr, int left, int right){ 
    if (left >= right){ 
    return ; } int l = left; int r = right; int temp = arr[right]; int t = 0;// 作为交换变量 while (l < r){ 
    while (arr[l] <= temp && l < r){ 
    // 从左边向右寻找大于等于temp的数 l++; } while (arr[r] >= temp && l < r){ 
    // 从右向左寻找小于等于temp的数 r--; } if (l < r){ 
    //交换 t = arr[l]; arr[l] = arr[r]; arr[r] = t; } } arr[right] = arr[l]; arr[l] = temp; quickSort(arr, left, r-1);//向左递归 quickSort(arr, l+1, right);// 向右递归 } / * @Description: mergeSort 归并排序 * @param: [arr, temp, left, right] * @return: void * @auther: z * @date: 20/6/16 15:54 */ public void mergeSort(int[] arr, int[] temp, int left, int right){ 
    if (left < right){ 
    int mid = (left + right) / 2; // 向左递归分解 mergeSort(arr, temp, left, mid); // 向右递归分解 mergeSort(arr, temp, mid + 1, right); merge(arr, temp, left, right, mid); } } / * @Description: merge 归并 * @param: [arr, temp, left, right, mid] * @return: void * @auther: z * @date: 20/6/16 15:55 */ public void merge(int[] arr, int[] temp, int left, int right, int mid){ 
    int i = left; int j = mid + 1; int t = 0; // 1.比较两个两部分每一个的大小，知道有一部分数据全部加入temp while (i <= mid && j <= right){ 
    if (arr[i] < arr[j]){ 
    temp[t] = arr[i]; i++; }else { 
    temp[t] = arr[j]; j++; } t++; } // 2.将剩余的那一部分的全部加入temp while (i <= mid){ 
    // 若前面的部分剩余,将前面那部分剩余的全部加入 temp[t] = arr[i]; i++; t++; } while (j <= right){ 
    // 若后面的部分剩余，则将后面的的部分全部加入 temp[t] = arr[j]; j++; t++; } // 3.将temp的数全部拷贝到arr中 t = 0; int tempLeft = left; while (tempLeft <= right){ 
    arr[tempLeft] = temp[t]; t++; tempLeft++; } } / * @Description: radixSort 基数排序 * @param: [arr] * @return: void * @auther: z * @date: 20/6/16 22:57 */ public 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();//最大值的长度 // 初始化一个二维数据，二维数组的没一个数组都是一个桶，因为无法确定每一个桶会装多少个数据，所以设置为arr.lenth int[][] bucket = new int[10][arr.length]; // 初始化一个一维数组用于保存桶保存的数的个数 int [] bucketElementCounts = new int[10]; for (int i = 0, n = 1; i < maxLength; i++, n *= 10) { 
    // i控制循环次数，n控制每次取得的位数 for (int j = 0; j < arr.length; j++) { 
    // 循环每个数，按照规则放入桶内 int digitalOfElement = arr[j] / n % 10; // 每次取模得到相应位数的值 bucket[digitalOfElement][bucketElementCounts[digitalOfElement]] = arr[j]; bucketElementCounts[digitalOfElement]++; } int index = 0;//存放数据的索引 for (int k = 0; k < bucket.length; k++) { 
    // 循环所有桶 if (bucketElementCounts[k] != 0){ 
    // 不为空的桶 for (int m = 0; m < bucketElementCounts[k]; m++) { 
    // 将桶的元素放入数组 arr[index++] = bucket[k][m]; } } bucketElementCounts[k] = 0;//清空桶 } } } / * @Description: countSort 计数排序 * @param: [arr] * @return: void * @auther: z * @date: 20/6/17 9:18 */ public void countSort(int[] arr){ 
    int min = arr[0]; int max = arr[0]; for (int i = 0; i < arr.length; i++) { 
    // 找出最大值与最小值 if (arr[i] > max){ 
    max = arr[i]; }else if (arr[i] < min){ 
    min = arr[i]; } } int[] counts = new int[max - min + 1];// 计数空间 for (int i = 0; i < arr.length; i++) { 
    // 将每一个数减去最小值统计到临时数组中 counts[arr[i] - min] += 1; // arr[i]-min对应计数空间的下表 } for (int i = 0,index =0; i < counts.length; i++) { 
    int item = counts[i];//每一个数对应的统计量 while (item-- != 0){ 
    // 直到每一个数的统计量归零 arr[index++] = i + min; // 将原来的数展开放到原数组中，展开就是按照大小排列 } } } / * @Description: bucketSort 桶排序 * @param: [arr] * @return: void * @auther: z * @date: 20/6/17 10:06 */ public void bucketSort(int[] arr){ 
    int min = arr[0]; int max = arr[0]; for (int i = 0; i < arr.length; i++) { 
    // 找出最大值与最小值 min = Math.min(min,arr[i]); max = Math.max(max,arr[i]); } int bucketNumber = (max - min)/arr.length + 1; // 桶的数量 ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(); // 存储每一个桶 ArrayList<Integer> bucket = null; for (int i = 0; i < bucketNumber; i++) { 
    // 将没一个桶放入buckets中 bucket = new ArrayList<Integer>(); buckets.add(bucket); } for (int item : arr) { 
    // 循环数据插入到桶 ArrayList<Integer> bc = buckets.get((item - min) / arr.length); // (item - min) / arr.length 表示桶的位置 insert(bc, item); // 插入桶（桶内排序） } int index = 0; // 索引数组 for (ArrayList<Integer> bc : buckets) { 
    // 循环每一个桶 for (Integer item : bc) { 
    // 循环桶内的数据 arr[index++] = item; // 依次将桶内的数据取出 } } } / * @Description: insert 向桶加数据（按顺序） * @param: [bc, item] * @return: void * @auther: z * @date: 20/6/17 11:01 */ public void insert(ArrayList<Integer> bc, int item){ 
    ListIterator<Integer> itl = bc.listIterator(); boolean flag = true; while (itl.hasNext()){ 
    if (item <= itl.next()){ 
    itl.previous(); // 将迭代器的位置偏移到上一位 itl.add(item); // 将数据插入到迭代器当前的位置上 flag = false; break; } } if (flag){ 
    // 否在九八数据插插入到末端 bc.add(item); } } / * @Description: heapSort 堆排序 * @param: [arr] * @return: void * @auther: z * @date: 20/6/20 17:10 */ public void heapSort(int[] arr){ 
    int temp = 0; // 第一次调整：将最大是数调整为根节点 // arr.length/2 - 1 :为第一个非叶子节点 for (int i = arr.length/2 - 1; i >= 0; i--) { 
    adjustHeap(arr, i, arr.length); } for (int i = arr.length-1 ; i > 0; i--) { 
    temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; // 为什么这里的的第二个参数写死是0 ？ // 因为经过第一次调整之后，再经过交换，就只有很根节点不是一个大顶堆， // 所以只需要进行简单的与根节点交换就好，而不需要在进行整体的一个大顶堆的构造 adjustHeap(arr, 0, i); } } / * @Description: adjustHeap 调整以i为非叶子节点的局部子树，使得父节点的值大于子节点的值 * @param: [arr 待调整的数组, i 表示非叶子节点的索引, length：表示有多少元素调整] * @return: void * @auther: z * @date: 20/6/20 16:22 */ public void adjustHeap(int[] arr, int i, int length){ 
    int temp = arr[i]; // k = i * 2 + 1：表示i这个节点的左子树 for (int k = i * 2 + 1; k < arr.length; k = k * 2 + 1) { 
    if (k + 1 < length && arr[k] < arr[k+1]){ 
    // 比较左右子节点的大小，将k指向较大的拿一个节点 k++; } if (arr[k] > temp){ 
    // 子节点大于父节点 arr[i] = arr[k];//交换数据第一步：子节点的值给父节点 i = k ;//将i指向调整后的子节点，用于循环结束后交换数据 }else { 
    break; } } arr[i] = temp;//交换数据第二步 } }