冒泡排序（Bubble Sort）：一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 假设一个无序数组的长度N，利用冒泡排序将其从小到到进行排序： 基本思路： 1）要进行N - 1趟，此处趟数用i来表示 2）每一趟中要进行N - i次（i表示第几趟，从而表明了趟数 + 每一趟中进行交换的次数 == N） 3）进行前后比较，如果顺序错误，那么就要将其交换过来 由图可以知道，一共有7个数，最多进行了 7 - 1 = 6 趟，在第i趟中进行了N - i次交换
代码实现：
for(int i = 0; i<arr.length - 1; i++){ for(int j = 0; j<arr.length - i-1; j++){ if(arr[j+1] < arr[j]){//如果顺序错误，那么进行交换 int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } }冒泡排序的优化：由上面可以知道，走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。所以只要有一个标记flag，在每一趟中都没有进行过一次交换，那么说明了数组有序了，不需要再进行下一趟的交换。
for(int i = 0; i<arr.length - 1; i++){ flag = false;//注意要将flag重置为false for(int j = 0; j<arr.length - i-1; j++){ if(arr[j+1] < arr[j]){ int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; flag = true;//说明已经交换 } } if(flag == false)//如果这一趟没有进行过交换，那么就说明了这一次排序使得数字有序，退出循环 break; }选择排序（SelectSort):一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。 算法步骤 1）在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 3）重复第二步，直到所有元素均排序完毕。 说明： 1）最多进行了arr.length - 1趟交换 2）在每一趟排序中，需要找到最小值，然后和当前这个数进行比较，如果当前的值比最小值要大，那么要交换，否则不用（此处是按照升序进行排序），进入下一趟排序（就好比上面图中的20，要遍历其后面的数，找到最小值，然后将其交换）
代码实现：
int minIndex;//最小值对应的下标 int min;//表示最小值 for(int i = 0; i<arr.length; i++){ minIndex = i; min = arr[i]; for(int j = i+1; j<arr.length;j++){ if(arr[j] < min) { minIndex = j;//表示最小值的下标 min = arr[j];//表示最小值 } } if(minIndex != i){ //如果min不是i，那么就说明当前下标的后面还有数比当前的下标对应的数字要小，所以进行交换 arr[minIndex] = arr[i]; arr[i] = min; } }插入排序（InsertSort): 插入排序算法思想：每趟将一个元素，按照其关键字的大小插入到它前面已经排序的子序列中，依此重复，直到插入全部元素。 步骤： 1）将从下标为1的数字开始遍历，将当前的数字赋给临时变量temp 2）将temp和当前下标（temp对应的下标)之前的数字进行比较，如果temp大于等于前面的数字y，那么表明了y的后面就是temp要插入的位置，否则就将前面的数字后移
代码实现：
//这个代码是一边输入，然后一边进行插入排序的 for(int i = 0; i<arr.length; i++) { arr[i] = (int)(Math.random()*800);//产生8000个[0,800)的随机数 temp = arr[i];//将arr[i]赋给临时变量num，然后拿num这个临时变量和arr[i]之前的元素进行比较（要根据需求来比较） for(j = i - 1; j>=0; j--){ if(arr[j] <= temp)//当num这个临时变量比arr[j]要大，那么就说明j后一个元素就是num break; arr[j + 1] = arr[j];//否则就要将i前面的元素后移 } arr[j+1] = num;//注意是j+1，而不是j，因为num比j下标对应的值大或者相等 } //先输入完毕，再进行排序 for(int i = 1; i<arr.length; i++) { num = arr[i];//将arr[i]赋给临时变量num，然后拿num这个临时变量和arr[i]之前的元素进行比较 for(j = i - 1; j>=0; j--){ if(arr[j] <= num)//当num这个临时变量比arr[j]要大，那么就说明j后一个元素就是num break; arr[j + 1] = arr[j];//否则就要将i前面的元素后移 } arr[j+1] = num;//注意是j+1，而不是j，因为num比j下标对应的值大或者相等 }可能大家会疑惑，为什么要将当前的数字赋给临时变量temp呢？如果不赋的话（那下面的代码说明一下），如果arr[i]不赋值给temp，那么如果arr[i]小于其前面的数字，那么会后移，arr[i]的值就变了，所以需要将arr[i]赋值给temp
希尔排序（ShellSort):也是一种插入排序，他是简单插入排序改进之后的一个更加高效的版本，也称为缩小增量排序。
算法描述： 1）将一个数据序列分成若干组，每组由若干相隔一段距离（称为增量）的元素组成，在一个组内采用直接插入排序算法进行排序。
2）增量初值通常为数据序列长度的一半，以后每趟增量减半，最后值为1，此时就成为了直接插入排序了。随着增量逐渐减小，组数也减小，组内元素个数增加，数据序列接近有序。 当增量gap变成了1，此时就只有一组，变成了直接插入排序（增量为1），当gap 为0时，数组实现了有序。
代码实现：
int gap= arr.length / 2;//步长 int j,temp; while(gap != 0){//当gap等于0的时候，退出循环，数组实现有序 for(int i = gap; i<arr.length; i++){ temp = arr[i];//将arr[i]赋给一个临时变量，然后和其同一组中并且在i前面的数字进行比较 for(j = i-gap; j>=0 ; j-=gap){//这一步近似于插入排序,将temp和i前面的而且是同一组的数字进行比较 if(arr[j] <= temp){//此处是升序排序 break; } arr[j+gap] = arr[j];//如果temp小于arr[j]的值，那么后移（注意这里不是arr[j + 1] = arr[j]了哈，因为要在每一组中进行直接插入排序嘛） } arr[j+gap] = temp;//注意这一步是arr[j + length],为什么不是j呢？上面的插入排序已经说明清楚了，这里就不说了哈 } gap /= 2; }归并的含义：将两个或两个以上的有序表合并成一个新的有序表。
归并排序（MergeSort):采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
其算法思路如下：
1.如果给的数组只有一个元素的话，直接返回（也就是递归到最底层的一个情况）—作为结束递归的条件
2.把整个数组分为尽可能相等的两个部分（分）
3.对于两个被分开的两个部分再次进行操作2（也就是递归）
4.把两个被分开且排好序的数组拼接在一起
代码实现：
这是我本来的代码，后来发现如果有重复的数字，就不可以，会发生报错，所以在这里标记一下，既是给自己一个提醒，也给大家一个提醒，希望大家不要像我一样犯这样的错误，哈哈哈~~~
import java.util.Scanner; public class MergeSort { public static int[] arr = new int[10]; public static void main(String[] args){ Scanner sc = new Scanner(System.in); for(int i = 0; i<arr.length; i++) arr[i] = sc.nextInt(); merge(); //调用方法，从而新建一个新的临时数组，将子数组放到这个临时数组中，然后将临时数组赋值给原来的数组，从而排好序的 System.out.println("进行排序之后："); for(int a: arr){ System.out.print(a+ " "); } System.out.println(); } public static void merge(){ //建立一个新数组，从而将子数组复制个这个数组，将所有的子数组进行归并之后，将这个数组赋值给原来的数组即可 int[] array = new int[arr.length]; mergeSort(array,0,arr.length - 1); } public static void mergeSort(int[] array, int n, int m){ if(n >= m){ //如果n>m,那么范围不对，如果相等，就说明只有一个元素，此时不需要进行交换 return; } int index = (n + m ) / 2;//将数组分成两部分 mergeSort(array,n,index); mergeSort(array,index + 1, m);//利用递归，将一个数组分成两个子数组 merge(array,n,index,m);//将两个子数组进行归并 } public static void merge(int[] array,int lower,int mid, int upper){ int n = upper - lower + 1;//统计这个子数组中有多少个元素 int lowerBound = lower; int lower2 = mid + 1;//右子数组的最小下标 int j = 0; while(lower <= mid && lower2 <= upper){ //当两个子数组都有元素的时候，则将两者的元素进行比较，谁小的谁先插入到新的数组中 if(arr[lower] <=arr[lower2]) { array[j++] = arr[lower]; lower++; }else{ array[j++] = arr[lower2]; lower2++; } } //考虑子数组的长度不一样的情况 //当左子数组没有遍历完的时候 while(lower <= mid){ array[j++] = arr[lower++]; } //当右子数组没有遍历完的时候 while(lower2 <= upper){ array[j++] = arr[lower2++]; } //将已经排好序的新数组赋值给原来的数组 for(j = 0; j<n; j++,lowerBound++) arr[lowerBound] = array[j]; } }改正后，实现数组含有重复数字的情况的代码：
//有重复的数字都可以进行排序的代码（改正了） import java.util.Scanner; public class MergeSort { public static int[] arr = new int[10]; public static void main(String[] args){ Scanner sc = new Scanner(System.in); for(int i = 0; i<arr.length; i++) arr[i] = sc.nextInt(); merge(); //调用方法，从而新建一个新的临时数组，将子数组放到这个临时数组中，然后将临时数组赋值给原来的数组，从而排好序的 System.out.println("进行排序之后："); for(int a: arr){ System.out.print(a+ " "); } System.out.println(); } public static void merge(){ //建立一个新数组，从而将子数组复制个这个数组，将所有的子数组进行归并之后，将这个数组赋值给原来的数组即可 int[] array = new int[arr.length]; mergeSort(array,0,arr.length - 1); } public static void mergeSort(int[] array, int n, int m){ if(n >= m){ //如果n>m,那么范围不对（就好比区间[2,3],那么2肯定是比3小的，所以左边的一定比右边的小）如果相等，就说明只有一个元素，此时不需要进行交换 return; } int index = (n + m ) / 2;//将数组分成两部分 mergeSort(array,n,index); mergeSort(array,index + 1, m);//利用递归，将一个数组分成两个子数组 merge(array,n,index,m);//将两个子数组进行归并 } public static void merge(int[] array,int lower,int mid, int upper){ int n = upper - lower + 1;//统计这个子数组中有多少个元素 int lowerBound = lower; int lower2 = mid + 1;//右子数组的最小下标 int j = 0; //将两个子数组进行归并 while(lower <= mid && lower2 <= upper){ //当两个子数组都有元素的时候，则将两者的元素进行比较，谁小的谁先插入到新的数组中，从而实现升序排序 if(arr[lower] <=arr[lower2]) {//如果左子数组的数小于等于右子数组的数，那么先将左子数组的数插入（注意这里是小于等于，要考虑出现重复的数字的情况） array[j++] = arr[lower]; lower++; }else { array[j++] = arr[lower2]; lower2++; } } //考虑子数组的长度不一样的情况 //当左子数组没有遍历完的时候 while(lower <= mid){ array[j++] = arr[lower++]; } //当右子数组没有遍历完的时候 while(lower2 <= upper){ array[j++] = arr[lower2++]; } //将已经排好序的新数组赋值给原来的数组 for(j = 0; j<n; j++,lowerBound++) arr[lowerBound] = array[j]; }快速排序(QuickSort): 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：
1、挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），此处选择数组中间的那个数作为基准。即arr[index] = pivot,此处的index 是数组中间数的下标
2、分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，已经将数组分割成了两个子数组，左子数组都是小于基准的值，右子数组都是大于基准的值。
那么实现分割操作呢？ 将基准值arr[ index ] 赋给临时变量pivot,然后分别从两边进行遍历，如果左边遇到第一个比pivot大的数，右边遇到第一个比pivot小的数，那么将两者进行交换
有同学可能又会问这里为什么又要将arr[index]赋给临时变量pivot呢？ 因为在分割的过程中进行了交换，可能会使arr[index]的值发生变化，从而导致错误。比如一个例子 ：一个数组{5，9，2，6，0，1，2} ，那么index = (0 + 6)/2,有pivot为6,那么从两边进行遍历，从而实现分割得到{5，2，2，1，0，6，9}，那么如果不将arr[index]赋给pivot,那么arr[index]对应的值会发生改变，变为1，而不再是6了
3、递归排序子序列：通过递归，将左右两个子数组进行排序（重复上面1、2操作）-----结束递归的条件是当数组只有一个元素的时候，结束递归，此时实现有序
代码实现：
这是一个片面的代码：只能将一个不含有重复数字的数组进行排序，如果数组含有重复的数字，就会发生报错，在这里做个标记，提醒自己，也希望能够提醒大家,希望大家不要像我一样犯同样错误哦，哈哈哈~~~~
import java.util.Scanner; public class QuickSort { public static int[] arr = new int[10]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); for (int i = 0; i < arr.length; i++) arr[i] = sc.nextInt(); //调用方法进行快速排序 quickSort(0, arr.length - 1); for (int a : arr) System.out.print(a + " "); System.out.println(); } public static void quickSort(int n, int m) { if (n < m) {//因为m的下标是右边的，那么必然是大于n的，就说明不只一个元素，此时进行交换 //定义基准的下标 int index = (m + n) / 2; int pivot = arr[index];//将中间的数作为基准，并将其值赋给临时变量pivot int m2 = m, n2 = n; int partition = getPartition(n,m,pivot);//分割，其中返回的值是分割的值的下标 //利用递归，将左右两个子数组进行排序 quickSort(n2, partition-1);//左子数组 quickSort(partition+1, m2);//右子数组 }else{ //如果n等于m，就说明了只有一个元素，若大于m，那么范围不对（就好比区间[2,3],那么2肯定是比3小的，所以左边的一定比右边的小） return; } } public static int getPartition(int n, int m, int pivot){ //将数组分成两个子数组，其中左子数组的值小于中间枢纽pivot的值，而右子数组的值大于中间枢纽的值 while (true) { //当n>=m,说明了左边都是小于标注的值，这时候就可以退出循环 while (n<m && arr[n] < pivot) { //需要在n<m的前提下进行判断，如果左边是小于标准的值，那么就右移,直到找到第一个大于标准的值的下标 //注意这里需要有n<m,否则有可能n一直移到最右边，那么很容易发生溢出，从而会报错 n++; } while (n<m && arr[m] > pivot) { //需要在n<m的前提下进行判断，如果右边找到了第一个小于标准的值，那么就退出循环，否则往左移 //注意这里需要有n<m，否则有可能m一直移到最左边，那么很容易发生溢出，从而会报错 m--; } if (n >= m) { //相遇了，那么就退出循环，说明基准的左边都是小于基准的数，右边都是大于基准的数，此时基准的下标为n或m，而不是原来的index break; } else { swap(n,m); } } return n;//返回基准的下标 } public static void swap(int n , int m){ //没有相遇，将二者进行交换 int temp = arr[n]; arr[n] = arr[m]; arr[m] = temp; } }含有重复数字的快速排序的情况分析： 这里利用三向切分进行分析的。也就是将数组分为三部分：小于当前切分元素的部分，等于当前切分元素的部分，大于当前切分元素的部分。
步骤： 1）每次切分从数组的左边到右边遍历一次，同时第一个数对应的值作为基准pivot,然后遍历，将基准后一个数字进行比较 ①如果基准比其后的一个数字要大，那么直接将两者进行交换，之后将基准的下标更改，随之的其后的数字的下标也要更改 ②如果基准比其后的一个数字要小，那么将其后的数字和数组最后的数字要交换，此时要将原来数组最后一个数字的下标要更改，然后再进行比较，如果还是基准的值小，那么重复②的操作，直到出现另外两种情况 ③如果基准的值和其后一个数字相等，那么将其后移，注意这里的后移并不是指基准的下标的后移，而是其后的数字进行后移，下面的图可以解释
2）每次切分之后，位于gt指针和lt指针之间的元素的位置都已经被排定，不需要再去移动了。之后将（lo,lt-1）,（gt+1,hi）分别作为处理左子数组和右子数组的递归函数的参数传入，递归结束，整个算法也就结束。 代码实现：
import java.util.Scanner; public class QuickSort2 { public static int[] arr = new int[10]; public static void main(String[] args){ Scanner sc = new Scanner(System.in); for(int i = 0; i<arr.length; i++) arr[i] = sc.nextInt(); System.out.println("进行快速排序之后："); quickSort(0,arr.length - 1); for(int a: arr){ System.out.print(a+" "); } System.out.println(); } public static void quickSort(int n, int m){ if(n >= m){ //如果只有一个元素或者范围不正确，就结束递归 return; }else{ int lo = n, lt = lo + 1, gt = m;//start表示基准的下标，lt表示基准后的数字得下标，gt表示数组最后一个数的下标 int pivot = arr[lo];//将每一个数组的第一个数作为基准 //遍历基准后的数，如果比基准小的，就直接交换，如果比基准大的数，那么就将这个数和数组最后一个数替换，在让基准和当前的数字进行比较 //如果相等，就后移，通过这个操作实现了基准左边都是小于基准的数，右边都是大于基准的数字 while(lt <= gt){ if(arr[lt] > pivot)//如果当前的数字大于基准，那么就将当前的数字和数组最后一个数字进行替换 swap(lt,gt--); else if(arr[lt] < pivot)//如果当前的数字小于基准，那么就将当前的数字和基准进行替换 swap(lt++,lo++); else lt++;//如果当前的数字等于基准，那么就直接基准后一个数的下标后移 } quickSort(n,lo - 1);//对左子数组进行快速排序 quickSort(gt + 1, m);//对右子数组进行快速排序 } } public static void swap(int n, int m){ int temp = arr[n]; arr[n] = arr[m]; arr[m] = temp; } }基数排序（RadixSort):主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
图解： 方法一：通过数组来实现： 思路（个人的思路，有什么疑惑的地方请指教哈，哈哈哈）： ①通过给出的数组arr，获得最大值max与最小值min，从而max - min的值有多少位数，进而可以知道要进行多少次递归（当然也可以通过循环来实现） ②新建一个数组，统计0 - 9 这10个数字分别出现了多少次 同时新建一个二维数组，其中有10行，arr.length列,来储存数组对应的数字，为什么是10行arr.length呢？因为每一行的下标对应的就是0 - 9这是个数字，列有arr.length是为了避免溢出,因为如果数字很多的情况呢，所以我觉得有arr.length列是避免溢出的情况。 ③遍历数组arr，从而可以知道对应的0-9这10个数字出现的次数，并将对应的值赋给二维数组对应的行中去 ④二维数组复制完毕之后，将遍历二维数组，将其值赋给原来的数组arr，然后重复上述操作max - min次，从而实现有序
考虑到数组中有负数的情况，那么要怎么解决呢？–通过将数组转换成含有非负数的数组。 将数组中的值都减去min这个值，从而将数组转化成含有非负数的数组，然后再将进行上述操作，不过注意的是，将二维数组的值赋给arr以后，arr并不是原来的数组了，因为转化成非负数的时候所有的数字都减去了min，所以还要遍历arr,将所有的数都加上min,才是要求的。
代码实现：
import java.util.Scanner; public class RadixSort { public static int[] arr = new int[10]; public static int k = 1; public static void main(String[] args){ Scanner sc = new Scanner(System.in); int max = 0; int min = 0; //输入数字，同时获得最大值、最小值 for(int i = 0; i<arr.length;i++) { arr[i] = sc.nextInt(); if(max < arr[i]) max = arr[i]; if(min > arr[i]) min = arr[i]; } //获取数组中最多有多少位数字 ---由于有了负数的存在，那么最大值的位数需要改变，因为下面的将数组化为整数的时候，最大值要改变，所以此时 //含有负数的数组化为非负整数的时候，最大值发生了改变，为max - min，如果数组是非负整数，因为下面的将数组化为整数的时候，最大值要改变 //所以此时的最大值还是max - min int count = getCount(max - min); getRadixSort(arr,count,min);//调用方法，进行基数排序 System.out.println("进行基数排序之后："); for(int a : arr) System.out.print(a+" "); System.out.println(); } public static int getCount(int max){ int count = 1; max /= 10; while(max != 0){ count++; max /= 10; } return count; } public static void getRadixSort(int[] arr, int total,int min){ //利用递归来求解 if(total <= 0){ return; }else{ int[] count = new int[10]; //新建一维数组，来统计每个数位出现的次数 int[][] array = new int[10][arr.length];//定义一个二维数组 for(int i = 0; i<arr.length; i++){ //获得一个数的个位、十位等数字 int digit = (arr[i] - min) / k % 10;//注意这里要是arr[i] - min，以防止负数的存在 array[digit][count[digit]]= (arr[i] - min);//将数组中的值赋值到有序数组中 count[digit] ++; } //将二位数组中的值赋给原来的数组 int m = 0; for(int i = 0; i<10; i++){ if(count[i] != 0){ for(int j = 0; j<count[i]; j++){ arr[m++] = array[i][j]; } } } //因为防止有负数，本来将数组的值都减去了min,所以要变成原来的数组，要将所有的数字都加上min才可以 for(int i = 0; i<arr.length; i++) arr[i] += min; k *= 10; total--; getRadixSort(arr,total,min); } //利用循环来实现 // while(total > 0){ // //统计每个数位出现的次数 // int[] count = new int[10]; // int[][] array = new int[10][arr.length];//定义一个有序数组 // for(int i = 0; i<arr.length; i++){ // int digit = (arr[i] - min) / k % 10;//获得最小值 // array[digit][count[digit]]= (arr[i] - min);//将数组中的值赋值到有序数组中 // count[digit] ++; // } // //将有序数组中的值赋给原来的数组 // int m = 0; // for(int i = 0; i<10; i++){ // if(count[i] != 0){ // for(int j = 0; j<count[i]; j++){ // arr[m++] = array[i][j]; // } // } // } // for(int i = 0; i<arr.length; i++) // arr[i] += min; // k *= 10; // total--; // } } }通过链表来实现的代码：
/** * 通过链表来实现基数排序 * 思路： * 1、新建链表数组，从而表示有序数组 * 2、获得arr中的最大值、最小值，从而知道arr要转换成有序链表要循环max - min次 * 3、获得arr数组中的每一项中每一个位数出现的次数，然后将这个数放在链表数组对应的位置中 * 4、获得链表数组之后，遍历这个数组，然后将值赋给arr * 5、获得arr并不是要求的有序数组，需要遍历这个数组，将每一项都要加上min才是题目要求的 * 为什么要怎么做？因为要考虑负数存在的情况，因为有负数，所以进行基数排序，我们可以通过将 * 数组转换成最小值为0的数组（注意只是改变其值而已，而不是新建的数组），而要实现将数组转换成 * 含有非负数的，那么将每一项的值都减去min * 6、重复上述操作3、4、5，直至循环max - min次 */ package sort; import java.util.Scanner; public class RadixSort2 { public static int[] arr = new int[10]; public static int k = 1; public static void main(String[] args){ Scanner sc = new Scanner(System.in); int max = 0, min = 0; //输入数组，同时获得数组中的最大值、最小值 for(int i = 0; i<arr.length; i++) { arr[i] = sc.nextInt(); if(max < arr[i]) max = arr[i]; if(min > arr[i]) min = arr[i]; } int count = getCount(max - min);//获得数组arr转换成有序数组循环的次数 getRadixSort(count,min); System.out.println("进行基数排序之后："); for(int a: arr) System.out.print(a+ " "); System.out.println(); } /** * 获得arr要转换成有序数组循环的次数 --- 也就是数组max - min的值有多少位数 * @param max * @return */ public static int getCount(int max){ int count = 1; max /= 10; while(max != 0){ count++; max /= 10; } return count; } /** * 通过链表来实现基数排序 * @param total 表示要转换的次数 * @param min 表述数组中的最小值 */ public static void getRadixSort(int total, int min){ //通过循环来实现 while(total > 0){ LinkedList[] list = new LinkedList[10];//新建一个链表数组，长度为10，对应的是0-9这10个数字 for(int i = 0; i<list.length; i++) list[i] = new LinkedList();//新建链表！！！注意这一步必须要有，否则没有办法初始化链表，也就没有实现其链表的相关操作 for(int i = 0; i<arr.length; i++){ int digit = ((arr[i] - min) / k) % 10;//将arr[i] - min以防数组中含有负数，从而将负数的数组转换成非负数的数组 list[digit].insert(arr[i] - min);//将对应的数插入到链表数组对应的位置 -- 减去min是避免了存在负数的情况 } int m = 0; //将链表数组中的值赋值给arr for(int i = 0; i<list.length; i++){ if(!list[i].isEmpty()){ Node current = list[i].head.next;//因为定义的是带假节点的链表，所以链表真正的头节点就是head.next //遍历链表，将值赋给数组 while(current != null){ arr[m++] = current.value; current = current.next; } } } //这里和上面所说的一样的道理，都是避免负数的存在，转化非负数是将所有的值减去min，所以这里转化成原来的数组要将所有的值都加min才可以 for(int i = 0; i<arr.length; i++){ arr[i] += min; } k *= 10; total--; } } }思路： ①首先按照要求将数组构建成大顶堆或者小顶堆。所谓的大顶堆，就是根节点是数组的最大值，反之，小顶堆的根节点是数组的最小值。
②然后在构建完毕之后，将根节点和数组的最后一个节点进行交换，交换完毕之后，数组的个数要减1，从而在之后的操作中不在涉及到最后的数，保证了最大或最小的数在最后。 ③然后通过递归，重复上面的操作①②，直到数组的个数为1结束递归。
public class SortApp { public static int[] arr = new int[10];//定义一个数组 public static int count = arr.length;//元素的个数 public static void main(String[] args) { for(int i = 0; i<arr.length; i++) { arr[i] = (int)(Math.random() * 100);//随机产生10个随机数 } System.out.print("未进行堆排序之前："); display(); for(int i = 1; i<arr.length;i++) tickUp(i);//构建大顶堆 sort();//进行堆排序 System.out.print("进行堆排序之后："); display();//输出 } public static void display() { for(int a: arr) System.out.print(a +" "); System.out.println(); } public static void sort() { swap(0,count - 1); count --; if(count == 1) {//只有一个元素的时候，结束递归 return; } tickDown(0);//由上面可以知道，根节点和最后一个节点交换了，那么此时根节点不一定是最大的，那么需要和它的子节点进行比较，从而再次构建大顶堆 sort();//构造完毕之后，再次递归，进行堆排序 } public static void swap(int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;//将根节点和最后一个节点进行交换 } /** * 向下筛选，从而再次构建大顶堆 * @param index */ public static void tickDown(int index) { int larger; int temp = arr[index];//将父节点赋给一个临时变量，然后和它的子节点进行比较，如果大于，就说明他的位置是对的，否则进行交换 while(index < count / 2) { //循环条件必须是index < count / 2,否则再计算左右子节点的时候发生报错 int leftChild = index * 2 + 1; int rightChild = index * 2 + 2; if(rightChild < count && arr[leftChild] < arr[rightChild]) { //如果含有右子节点，而且左右子节点中右子节点最大，那么larger = rightChild larger = rightChild; }else { //这里有两种情况，首先如果没有右子节点，那么larger 就是leftChild，其次如果有右子节点，而且左子节点大于右子节点，那么larger = leftChild larger = leftChild; } if(arr[larger] <= temp) { //如果父节点大于等于子节点，那么这个位置就是当前节点的位置,退出循环，注意不可以在这里写arr[index] = temp,然后在结束循环的时候不写这一步了 //因为有可能一直是arr[larger]一直大于temp，直到index = count / 2，退出循环，从而没有办法插入temp，导致数组中有两个相同的数 break; }else { arr[index] = arr[larger];//如果父节点小于子节点，那么子节点替换到其父节点的位置，父节点替换到其子节点的位置 index = larger; } arr[index] = temp;//这里有两种情况，首先第一种是index = count / 2，从而结束循环，第二种是arr[larger] <= temp,从而结束循环 } } /** * 通过向上筛选进行将节点插入到堆中 * @param index */ public static void tickUp(int index) { int temp = arr[index]; int parent = (index - 1) / 2;//获取其父节点 while(index > 0 && arr[parent] < temp) { //当父节点小于子节点的时候，将其进行交换 arr[index] = arr[parent]; index = parent; parent = (parent - 1) / 2; } arr[index] = temp; } }通过参考其他大佬的代码，将只保留tickDown方法：
public class Sorting { public static int[] arr = new int[10]; public static int count = arr.length;//定义数组的个数 public static void main(String[] args) { for(int i = 0; i<count; i++) arr[i] = (int)(Math.random()*100); System.out.println("没有进行堆排序之前："); display(); heapify();//首先将一个无序数组构建成一个大顶堆 sort();//进行堆排序 System.out.println("进行堆排序之后："); display(); } /** * 遍历数组 */ public static void display() { for(int a:arr) System.out.print(a+" "); System.out.println(); } public static void sort() { swap(0,count - 1);//将根节点和最后一个节点进行交换，然后将元素个数减1，从而将最后一个数固定 count --; if(count == 1)//如果只有一个元素，那么结束递归 return; adjustHeap(0);//再次构建最大堆 sort();//递归，从而再次将根节点和最后一个节点交换 } public static void swap(int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void heapify() { //从最后一个非叶子节点开始遍历，将其和它的子节点进行比较，如果自身小于它的子节点，那么就进行交换，从而构建大顶堆 for(int i = arr.length / 2 - 1; i >= 0; i --) adjustHeap(i); } public static void adjustHeap(int index) { int temp = arr[index];//将父节点的值赋给临时变量，将其和它的子节点进行比较 int larger;//标记左右子节点中哪一个子节点的值更大，然后将其和temp进行比较，如果temp大，那么这个父节点的位置是正确的，否则进行交换 while(index < count / 2) { int leftChild = index * 2 + 1; int rightChild = index * 2 + 2; if(rightChild < count && arr[leftChild] < arr[rightChild]) { //这里必须要有rightChild，因为考虑到当index 为count / 2 - 1时，只有一个左子节点 //当存在右子节点时，那么将左右子节点进行比较，从而获得两者中的最大值 larger = rightChild; }else { //当没有右子节点时，那么larger 为leftChild，当有右子节点，而且两个节点中，左子节点最大，那么larger 为leftChild larger = leftChild; } if(arr[larger] <= temp) { //当父节点的值比其左右子节点都大，那么就退出循环 break; }else { //当父节点的值小于其子节点的值，那么进行交换 arr[index] = arr[larger]; index = larger; } } arr[index] = temp; } }我是第一次写博客的，有写的不好的地方，还请大家原谅啊，哈哈哈😊😊😊，当然也请大家指正，下次一定会改正的哦。
