十大排序总结

曾经终败给现在 2022-02-22 04:36 190阅读 0赞

总结![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
**1.冒泡排序**  
【实现】

//冒泡排序
    	public static void bubbleSort(int[] arr){
    		if(arr== null || arr.length<2){
    			return;
    		}
    		for(int end = arr.length-1;end>0;end--){//O（n）
    			for(int i = 0;i<end;i++){//O（n）
    				if(arr[i]>arr[i+1]){
    					swap(arr,i,i+1);
    				}
    			}
    		}
    	}

【结果】<时间复杂度O（n^2） 空间复杂度O（1），稳定>  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
【特点】  
每一趟排序最大的到最后面（沉底）

**优化1**：定义一个flag，用来判断有没有进行交换，如果在某一次内层循环中没有交换操作，就说明此时数组已经是有序的了，不用再进行判断，可以节省时间。  
**优化2**：每一次交换记录最后一次交换的位置为0时候就停止  
**优化3**：鸡尾酒排序，从低到高，再从高到低排序。

**2.选择排序**  
【实现】

//选择排序
    	public static void selectSort(int[] arr){
    		if(arr == null ||arr.length < 2) return;
    		for(int i = 0;i<arr.length;i++){//O（n）
    			int minIndex= i;
    			for(int j = i+1;j<arr.length;j++){//O（n）
    				minIndex = arr[j]<arr[minIndex] ? j:minIndex;
    			}
    			swap(arr,i,minIndex);
    		}
    	}

【结果】<时间复杂度O（n^2） 空间复杂度O（1），不稳定>  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]  
【特点】  
每一趟排序都找到最小值

**3.插入排序**  
【实现】

//插入排序
    	public static void insertSort(int[] arr){
    		if(arr == null || arr.length < 2) return;
    		for(int i = 1;i<arr.length;i++){//O（n）
    			for(int j = i-1;j>=0 && arr[j]>arr[j+1];j--){//O（n）
    				swap(arr,j,j+1);
    			}
    		}
    	}

【结果】<时间复杂度O（n^2） 空间复杂度O（1），稳定>  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3]  
【特点】  
每次找到下一个数字在前面已经排好序的应该在的位置

**4.希尔排序**  
【实现】

//希尔排序
    	public static void shellSort(int[] arr){
    		if(arr == null ||arr.length < 2) return;
    		int n = arr.length;
    		int gap = n/2;
    		while(gap > 0){
    			for(int j = gap;j<n;j++){
    				int i = j;
    				while(i>=gap && arr[i-gap]>arr[i]){
    					swap(arr,i-gap,i);
    					i -= gap;
    				}
    			}
    			gap = gap/2;
    		}
    	}

【结果】<时间复杂度O（nlogn） 空间复杂度O（nlog^2 n），不稳定>  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 4]

**5.归并排序**  
【实现】

//归并排序
    	public static void mergeSort(int[] arr){
    		if(arr ==null ||arr.length<2) return;
    		sortProcess(arr,0,arr.length-1);
    	}
    	public static void sortProcess(int[] arr,int L,int R){
    		if(L == R) return;
    		if(L<R){
    			int mid = (L+R)/2;
    			sortProcess(arr,L,mid);
    			sortProcess(arr,mid+1,R);
    			merge(arr,L,mid,R);
    		}
    	}
    	public static void merge(int[] arr,int L,int mid,int R){
    		int[] help = new int[R-L+1];
    		int i = 0;
    		int p1 = L;
    		int p2 = mid+1;
    		while(p1 <= mid && p2<=R){
    			help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
    		}
    		//两个必有一个越界
    		while(p1<=mid){
    			help[i++] = arr[p1++];
    		}
    		while(p2<=R){
    			help[i++] = arr[p2++];
    		}
    		for(i=0;i<help.length;i++){
    			arr[L+i] = help[i];
    		}
    	}

【结果】<时间复杂度O（nlogn） 空间复杂度O（n），稳定>  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 5]

**6.快速排序**  
【实现】

//快速排序
    	public static void quickSort(int[] arr){
    		if(arr == null || arr.length < 2){
    			return;
    		}
    		quickSort(arr,0,arr.length-1);
    	}
    	public static void quickSort(int[] arr,int l,int r){
    		if(l < r){
    			swap(arr,l+(int)Math.random()*(r-l+1),r);
    			int[] p = partition(arr,l,r);
    			quickSort(arr,l,p[0] - 1);
    			quickSort(arr,p[1] + 1,r);
    		}
    	}
    	public static int[] partition(int[] arr,int l,int r){
    		int less = l-1;
    		int more = r;
    		while(l < more){
    			if(arr[l] < arr[r]){
    				swap(arr,++less,l++);
    			}else if(arr[l] >arr[r]){
    				swap(arr,--more,l);
    			}else{
    				l++;
    			}
    		}
    		swap(arr,more,r);
    		return new int[] {less+1,more};
    	}

【结果】<时间复杂度O（nlogn） 空间复杂度O（logn），不稳定>  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][20190409230851611.png]  
【特点】  
找到一个基准数，左右哨兵，从右往左走，遇到小于基准数的放左边，从左往右走，遇到大于基准数的放到右边，一趟结果为基准数左边的比基准数小，基准数右边的比基准数大。  
**7.堆排序**  
【实现】

//堆排序
    	public static void heapSort(int[] arr){
    		if(arr == null || arr.length < 2){
    			return;
    		}
    		for(int i = 0;i < arr.length;i++){
    			heapInsert(arr,i);
    		}
    		int size = arr.length;
    		swap(arr,0,--size);
    		while(size>0){
    			heapify(arr,0,size);
    			swap(arr,0,--size);
    		}
    	}
    		
    	public static void heapInsert(int[] arr,int index){
    		while(arr[index] >arr[(index-1)/2]){
    			swap(arr,index,(index-1)/2);
    			index = (index-1)/2;
    		}
    	}
    	
    	public static void heapify(int[] arr,int index,int size){
    		int left = index*2+1;
    		while(left<size){
    			int largest = left +1<size && arr[left+1]>arr[left]?left+1:left;
    			largest = arr[largest]>arr[index]?largest:index;
    			if(largest == index){
    				break;
    			}
    			swap(arr,largest,index);
    			index = largest;
    			left = index*2+1;
    		}
    	}

【结果】<时间复杂度O（nlogn） 空间复杂度O（1），不稳定>  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 8]  
**8.计数排序**  
【实现】

//计数排序
    	/*
    	 * 计数排序有如下四个步骤。
    	 * 		首先会对每个输入进行频率统计，得到元素的频率表；
    	 * 		然后将频率表转换为该元素的开始索引；
    	 * 		根据各个元素的开始索引，将相同元素分类到临时数组中。
    	 * 		最后将临时数组中的元素写回到原数组中
    	 */
    	public static void countingSort(int[] arr){
    		//计算最大最小值，用ifPresent检查一下
    		int max = Arrays.stream(arr).max().getAsInt();
    		int min = Arrays.stream(arr).min().getAsInt();
    		int N = arr.length;
    		int R = max - min +1;//最大最小元素之间范围【min，max】的长度
    		//1.计算频率，再需要的数组长度上额外加1
    		int[] count = new int[R+1];
    		for(int i = 0;i < N;i++){
    			//使用加1 后的索引，有重复的该位置就自增
    			count[arr[i] - min + 1]++;
    		}
    		//2.频率 -> 元素的开始索引
    		for(int r = 0;r < R;r++){
    			count[r+1] += count[r];//小于当前元素r+1的个数等于上一个元素的个数（count[r+1]）与小于上一个元素的个数（count[r]）之和
    		}
    		//3.元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
    		int[] aux = new int[N];
    		for(int i = 0;i<N;i++){
    			//填充一个数据后，自增，以便相同的数据可以填到下一个空位
    			aux[count[arr[i]-min]++]=arr[i];
    		}
    		//4.数据回写
    		for(int i = 0;i<N;i++){
    			arr[i] = aux[i];
    		}
    	}

【结果】<时间复杂度O（n+k） 空间复杂度O（k），稳定>  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 9]

**9.桶排序**  
【实现】

/*
    	 * 思想：
    	 * 根据输入建立适当个数的桶，每个桶可以存放某个范围内的元素；
    	 * 将落在特定范围内的所有元素放入对应的桶中；
    	 * 对每个非空的桶中元素进行排序，可以选择通用的排序方法，比如插入、快排；
    	 * 按照划分的范围顺序，将桶中的元素依次取出。排序完成。
    	 */
    	/*
    	 * 桶的数量为数组长度arr.length
    	 * 映射函数使用bucketIndex =(value * arr.length)/(maxvalue+1),加1是为了保证最大元素可以存到数组最后一个位置
    	 */
    	public static void BucketSort(int[] arr){
    		//建立桶，个数和待排序的数组长度一样
    		int N = arr.length;
    		LinkedList<Integer>[] bucket = (LinkedList<Integer>[]) new LinkedList[N];
    		
    		//待排序数组中的最大值
    		int maxValue = Arrays.stream(arr).max().getAsInt();
    		System.out.println(maxValue);
    		//根据每个元素的值，分配到对应范围的桶中
    		for(int i = 0;i < arr.length;i++){
    			int index = toBucketIndex(arr[i],maxValue,N);
    			System.out.println("放入"+index+"号桶");
    			//没有桶才建立（延时）
    			if(bucket[index] == null){
    				bucket[index] = new LinkedList<>();
    			}
    			//有桶直接使用
    			bucket[index].add(arr[i]);
    		}
    		//对每个非空的桶排序，排序后顺便存入临时的List,则list中已经有序
    		List<Integer> temp = new ArrayList<>();
    		for(int i = 0;i<N;i++){
    			if(bucket[i] != null){
    				Collections.sort(bucket[i]);
    				temp.addAll(bucket[i]);
    			}
    			System.out.println("加入"+i+"号桶");
    			System.out.println(temp);
    		}
    		System.out.println();
    		System.out.println("最终");
    		System.out.println(temp);
    		//将temp中的数据写入原数组
    		for(int i = 0;i<N;i++){
    			arr[i] = temp.get(i);
    		}
    		System.out.println();
    		printList(arr);
    	}
    	
    	//映射函数，将值转换为对应存放到的同数组的索引
    	private static int toBucketIndex(int value,int maxValue,int N){
    		return (value * N)/(maxValue + 1);
    	}

【结果】<时间复杂度O（n+k） 空间复杂度O（n+k），稳定>  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 11]  
【特点】  
待排序的数据要分散一些

**10.基数排序**  
【实现】

//基数排序
    	public static void RadixSort(int[] arr){
    		//每位数字范围0~9，基位10
    		int R = 10;
    		int N = arr.length;
    		int[] aux = new int[N];
    		int[] count = new int[R+1];
    		
    		//以关键字来排序的轮数，由位数最多的数字决定，其余位数少的数字在比较高位时，自动用0进行比较
    		//将数字转换成字符串，字符串的长度就是数字的位数，字符串最长的哪个数字也拥有最多的位数
    		int W = Arrays.stream(arr).map(s -> String.valueOf(s).length()).max().getAsInt();
    		//共需要d轮计数排序，从d = 0开始，说明时从个位开始比较，符号从右到左的顺序
    		for(int d = 0;d < W;d++){
    			//1.计算频率，在需要的数组长度上额外加1
    			for(int i = 0;i<N;i++){
    				//使用加1后的索引，有重复的该位置就自增
    				count[digitAt(arr[i],d)+1]++;
    			}
    			//2.频率 ->元素的开始索引
    			for(int r = 0;r<R;r++){
    				count[r+1]+=count[r];
    			}
    			
    			//3.元素按照开始索引分类，用到一个和待排序数组一样大临时数组存放数据
    			for(int i = 0;i<N;i++){
    				//填充一个数据后，自增，以便相同的数据可以填到下一个空为
    				aux[count[digitAt(arr[i],d)]++] = arr[i];
    			}
    			//4.数据回写
    			for(int i= 0;i<N;i++){
    				arr[i] = aux[i];
    			}
    			//重置count[]，以便下一轮统计使用
    			for(int i =0;i<count.length;i++){
    				count[i] = 0;
    			}
    		}
    		System.out.println();
    		printList(arr);
    	}
    	//根据d，获取某个值的个位，十位，百位等，d = 0取出个位，d = 1取出十位，一次类推，对于不存在的高位，用0补
    	private static int digitAt(int value,int d){
    		return (value / (int) Math.pow(10, d))%10;
    	}

【结果】<时间复杂度O（n\*k） 空间复杂度O（n+k），稳定>  
![在这里插入图片描述][20190411225852498.png]  
【整体代码】

package 不会的东西;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    
    public class 排序 {
    	
    	public static void main(String[] args) {
    		int[] arr = {4,3,9,8,7,1,5,10,2,6};
    		System.out.print("原数组为：");
    		printList(arr);
    		System.out.println();
    		System.out.println("=================");
    		//System.out.println("冒泡排序为：");
    		//bubbleSort(arr);
    		//System.out.println();
    		//System.out.println("选择排序为：");
    		//selectSort(arr);
    		//System.out.println();
    		//System.out.println("插入排序为：");
    		//insertSort(arr);
    		//System.out.println();
    		//System.out.println("希尔排序为：");
    		//shellSort(arr);
    		//System.out.println();
    		//System.out.println("归并排序为：");
    		//mergeSort(arr);
    		//System.out.println();
    		//System.out.println("快速排序为：");
    		//quickSort(arr);
    		//System.out.println();
    		//System.out.println("堆排序为：");
    		//heapSort(arr);
    		//System.out.println();
    		//System.out.println("计数排序为：");
    		//countingSort (arr);
    		int[] arr1 = {44, 67, 32, 21, 9, 98, 44, 111, 99, 6};
    		System.out.println();
    		System.out.print("原数组为：");
    		printList(arr1);
    		//System.out.println();
    		//System.out.println("桶排序为：");
    		//BucketSort(arr1);
    		int[] arr2 = {244, 167, 1234, 321, 29, 98, 1444, 111, 99, 6};
    		System.out.println();
    		System.out.print("原数组为：");
    		printList(arr2);
    		System.out.println();
    		System.out.println("基数排序为：");
    		RadixSort(arr2);
    	}
    	
    	//冒泡排序
    	public static void bubbleSort(int[] arr){
    		if(arr== null || arr.length<2){
    			return;
    		}
    		for(int end = arr.length-1;end>0;end--){
    			for(int i = 0;i<end;i++){
    				if(arr[i]>arr[i+1]){
    					swap(arr,i,i+1);
    				}
    			}
    			System.out.println();
    			printList(arr);
    		}
    	}
    	
    	//选择排序
    	public static void selectSort(int[] arr){
    		if(arr == null ||arr.length < 2) return;
    		for(int i = 0;i<arr.length;i++){
    			int minIndex= i;
    			for(int j = i+1;j<arr.length;j++){
    				minIndex = arr[j]<arr[minIndex] ? j:minIndex;
    			}
    			swap(arr,i,minIndex);
    			System.out.println();
    			printList(arr);
    		}
    	}
    	//插入排序
    	public static void insertSort(int[] arr){
    		if(arr == null || arr.length < 2) return;
    		for(int i = 1;i<arr.length;i++){
    			for(int j = i-1;j>=0 && arr[j]>arr[j+1];j--){
    				swap(arr,j,j+1);
    			}
    			System.out.println();
    			printList(arr);
    		}
    	}
    	
    	//希尔排序
    	public static void shellSort(int[] arr){
    		if(arr == null ||arr.length < 2) return;
    		int n = arr.length;
    		int gap = n/2;
    		while(gap > 0){
    			for(int j = gap;j<n;j++){
    				int i = j;
    				while(i>=gap && arr[i-gap]>arr[i]){
    					swap(arr,i-gap,i);
    					i -= gap;
    				}
    			}
    			System.out.println();
    			System.out.println(gap);
    			printList(arr);
    			System.out.println();
    			gap = gap/2;
    		}
    	}
    	//归并排序
    	public static void mergeSort(int[] arr){
    		if(arr ==null ||arr.length<2) return;
    		sortProcess(arr,0,arr.length-1);
    	}
    	public static void sortProcess(int[] arr,int L,int R){
    		if(L == R) return;
    		if(L<R){
    			int mid = (L+R)/2;
    			sortProcess(arr,L,mid);
    			System.out.print("L="+L);
    			System.out.print("mid="+mid);
    			sortProcess(arr,mid+1,R);
    			System.out.print("R="+R);
    			System.out.println("mid+1="+(mid+1));
    			merge(arr,L,mid,R);
    		}
    	}
    	public static void merge(int[] arr,int L,int mid,int R){
    		
    		int[] help = new int[R-L+1];
    		int i = 0;
    		int p1 = L;
    		int p2 = mid+1;
    		while(p1 <= mid && p2<=R){
    			help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
    		}
    		//两个必有一个越界
    		while(p1<=mid){
    			help[i++] = arr[p1++];
    		}
    		while(p2<=R){
    			help[i++] = arr[p2++];
    		}
    		for(i=0;i<help.length;i++){
    			arr[L+i] = help[i];
    		}
    		//System.out.println();
    		printList(arr);
    		System.out.println();
    		System.out.println();
    	}
    	//快速排序
    	public static void quickSort(int[] arr){
    		if(arr == null || arr.length < 2){
    			return;
    		}
    		quickSort(arr,0,arr.length-1);
    		printList(arr);
    	}
    	
    	public static void quickSort(int[] arr,int l,int r){
    		if(l < r){
    			System.out.print("l = "+l);
    			System.out.println("r = "+r);
    			printList(arr);
    			System.out.println();
    			System.out.println();
    			swap(arr,l+(int)Math.random()*(r-l+1),r);
    			int[] p = partition(arr,l,r);
    			quickSort(arr,l,p[0] - 1);
    			quickSort(arr,p[1] + 1,r);
    		}
    		
    	}
    	
    	public static int[] partition(int[] arr,int l,int r){
    		int less = l-1;
    		int more = r;
    		while(l < more){
    			if(arr[l] < arr[r]){
    				swap(arr,++less,l++);
    			}else if(arr[l] >arr[r]){
    				swap(arr,--more,l);
    			}else{
    				l++;
    			}
    		}
    		swap(arr,more,r);
    		return new int[] {less+1,more};
    	}
    	
    	//堆排序
    	public static void heapSort(int[] arr){
    		if(arr == null || arr.length < 2){
    			return;
    		}
    		for(int i = 0;i < arr.length;i++){
    			heapInsert(arr,i);
    		}
    		int size = arr.length;
    		swap(arr,0,--size);
    		while(size>0){
    			heapify(arr,0,size);
    			swap(arr,0,--size);
    		}
    	}
    		
    	public static void heapInsert(int[] arr,int index){
    		while(arr[index] >arr[(index-1)/2]){
    			swap(arr,index,(index-1)/2);
    			index = (index-1)/2;
    		}
    		System.out.println("heapInsert");
    		printList(arr);
    		System.out.println();
    	}
    	
    	public static void heapify(int[] arr,int index,int size){
    		int left = index*2+1;
    		while(left<size){
    			int largest = left +1<size && arr[left+1]>arr[left]?left+1:left;
    			largest = arr[largest]>arr[index]?largest:index;
    			if(largest == index){
    				break;
    			}
    			swap(arr,largest,index);
    			index = largest;
    			left = index*2+1;
    		}
    		System.out.println("heapify");
    		printList(arr);
    		System.out.println();
    	}
    	
    	//计数排序
    	/*
    	 * 计数排序有如下四个步骤。
    	 * 		首先会对每个输入进行频率统计，得到元素的频率表；
    	 * 		然后将频率表转换为该元素的开始索引；
    	 * 		根据各个元素的开始索引，将相同元素分类到临时数组中。
    	 * 		最后将临时数组中的元素写回到原数组中
    	 */
    	public static void countingSort(int[] arr){
    		//计算最大最小值，用ifPresent检查一下
    		int max = Arrays.stream(arr).max().getAsInt();
    		int min = Arrays.stream(arr).min().getAsInt();
    		int N = arr.length;
    		int R = max - min +1;//最大最小元素之间范围【min，max】的长度
    		//1.计算频率，再需要的数组长度上额外加1
    		int[] count = new int[R+1];
    		for(int i = 0;i < N;i++){
    			//使用加1 后的索引，有重复的该位置就自增
    			count[arr[i] - min + 1]++;
    		}
    		System.out.println();
    		System.out.println("count1 加1后的索引");
    		printList(count);
    		//2.频率 -> 元素的开始索引
    		for(int r = 0;r < R;r++){
    			count[r+1] += count[r];//小于当前元素r+1的个数等于上一个元素的个数（count[r+1]）与小于上一个元素的个数（count[r]）之和
    		}
    		System.out.println();
    		System.out.println("元素的开始索引");
    		printList(count);
    		//3.元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
    		int[] aux = new int[N];
    		for(int i = 0;i<N;i++){
    			//填充一个数据后，自增，以便相同的数据可以填到下一个空位
    			aux[count[arr[i]-min]++]=arr[i];
    		}
    		System.out.println();
    		System.out.println("辅助数组");
    		printList(aux);
    		//4.数据回写
    		for(int i = 0;i<N;i++){
    			arr[i] = aux[i];
    		}
    		System.out.println();
    		System.out.println("写回数组");
    		printList(arr);
    	}
    	
    	/*
    	 * 思想：
    	 * 根据输入建立适当个数的桶，每个桶可以存放某个范围内的元素；
    	 * 将落在特定范围内的所有元素放入对应的桶中；
    	 * 对每个非空的桶中元素进行排序，可以选择通用的排序方法，比如插入、快排；
    	 * 按照划分的范围顺序，将桶中的元素依次取出。排序完成。
    	 */
    	/*
    	 * 桶的数量为数组长度arr.length
    	 * 映射函数使用bucketIndex =(value * arr.length)/(maxvalue+1),加1是为了保证最大元素可以存到数组最后一个位置
    	 */
    	public static void BucketSort(int[] arr){
    		//建立桶，个数和待排序的数组长度一样
    		int N = arr.length;
    		LinkedList<Integer>[] bucket = (LinkedList<Integer>[]) new LinkedList[N];
    		
    		//待排序数组中的最大值
    		int maxValue = Arrays.stream(arr).max().getAsInt();
    		System.out.println(maxValue);
    		//根据每个元素的值，分配到对应范围的桶中
    		for(int i = 0;i < arr.length;i++){
    			int index = toBucketIndex(arr[i],maxValue,N);
    			System.out.println("放入"+index+"号桶");
    			//没有桶才建立（延时）
    			if(bucket[index] == null){
    				bucket[index] = new LinkedList<>();
    			}
    			//有桶直接使用
    			bucket[index].add(arr[i]);
    		}
    		//对每个非空的桶排序，排序后顺便存入临时的List,则list中已经有序
    		List<Integer> temp = new ArrayList<>();
    		for(int i = 0;i<N;i++){
    			if(bucket[i] != null){
    				Collections.sort(bucket[i]);
    				temp.addAll(bucket[i]);
    			}
    			System.out.println("加入"+i+"号桶");
    			System.out.println(temp);
    		}
    		System.out.println();
    		System.out.println("最终");
    		System.out.println(temp);
    		//将temp中的数据写入原数组
    		for(int i = 0;i<N;i++){
    			arr[i] = temp.get(i);
    		}
    		System.out.println();
    		printList(arr);
    	}
    	
    	//映射函数，将值转换为对应存放到的同数组的索引
    	private static int toBucketIndex(int value,int maxValue,int N){
    		return (value * N)/(maxValue + 1);
    	}
    
    	//基数排序
    	public static void RadixSort(int[] arr){
    		//每位数字范围0~9，基位10
    		int R = 10;
    		int N = arr.length;
    		int[] aux = new int[N];
    		int[] count = new int[R+1];
    		
    		//以关键字来排序的轮数，由位数最多的数字决定，其余位数少的数字在比较高位时，自动用0进行比较
    		//将数字转换成字符串，字符串的长度就是数字的位数，字符串最长的哪个数字也拥有最多的位数
    		int W = Arrays.stream(arr).map(s -> String.valueOf(s).length()).max().getAsInt();
    		//共需要d轮计数排序，从d = 0开始，说明时从个位开始比较，符号从右到左的顺序
    		for(int d = 0;d < W;d++){
    			//1.计算频率，在需要的数组长度上额外加1
    			for(int i = 0;i<N;i++){
    				//使用加1后的索引，有重复的该位置就自增
    				count[digitAt(arr[i],d)+1]++;
    			}
    			//2.频率 ->元素的开始索引
    			for(int r = 0;r<R;r++){
    				count[r+1]+=count[r];
    			}
    			
    			//3.元素按照开始索引分类，用到一个和待排序数组一样大临时数组存放数据
    			for(int i = 0;i<N;i++){
    				//填充一个数据后，自增，以便相同的数据可以填到下一个空为
    				aux[count[digitAt(arr[i],d)]++] = arr[i];
    			}
    			//4.数据回写
    			for(int i= 0;i<N;i++){
    				arr[i] = aux[i];
    			}
    			//重置count[]，以便下一轮统计使用
    			for(int i =0;i<count.length;i++){
    				count[i] = 0;
    			}
    		}
    		System.out.println();
    		printList(arr);
    	}
    	//根据d，获取某个值的个位，十位，百位等，d = 0取出个位，d = 1取出十位，一次类推，对于不存在的高位，用0补
    	private static int digitAt(int value,int d){
    		return (value / (int) Math.pow(10, d))%10;
    	}
    	
    	
    	
    	
    	
    	//交换两个数字
    	public static void swap(int[] arr,int i,int j){
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    	//打印数组
    	public static void printList(int[] arr){
    		System.out.print("[");
    		for(int i = 0;i<arr.length;i++){
    			if(i < arr.length-1){
    				System.out.print(+arr[i]);
    				System.out.print(",");
    			}else if(i == arr.length-1){
    				System.out.print(+arr[i]);
    			}
    			
    		}
    		System.out.print("]");
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220222/f406aa2081f1471fa78f91db68cdd7d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220222/92a29132cbb14e84960e5e6b7a7ba6b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]: /images/20220222/f55ce8b22645476ab2a003cdb2f5040f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3]: /images/20220222/d21156b5665047e6b4e345196afeec8f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 4]: /images/20220222/4ead6f4922964baabe7a6d7c1b3e7517.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 5]: /images/20220222/366dbace9b9d4eaca52df4cd2b3cf3b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 6]: /images/20220222/ee8dec16841f435d946206ba6e1752d0.png
[20190409230851611.png]: /images/20220222/8f0d2fef0e64460e8f0209b6c7bfa4d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 7]: /images/20220222/35f3ce2972d945048ac862796d687484.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 8]: /images/20220222/0ae9dc88a3664992921b87f9149cc9cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 9]: /images/20220222/c34da509b05748a1868cbc5e58bfa956.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 10]: /images/20220222/737dd13429954486a3a233a91d68a591.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 11]: /images/20220222/2d56df6a194041b18987f96d9aafdafb.png
[20190411225852498.png]: /images/20220222/c40195ddee0148f8a846d014fff5c3eb.png