Java数据结构与算法——排序篇

骑猪看日落 2023-10-04 07:17 18阅读 0赞

> Java数据结构与算法: [https://blog.csdn.net/weixin\_46822367/article/details/115478461?spm=1001.2014.3001.5502][https_blog.csdn.net_weixin_46822367_article_details_115478461_spm_1001.2014.3001.5502].  
> 
> 
> #### 目录 ####
> 
>  *   *   *  1、==冒泡排序==
>          *  2、选择排序
>          *  3、插入排序
>          *  4、希尔排序
>          *  5、==快速排序==
>          *  6、归并排序
>          *  7、基数排序
>          *  8、堆排序

#### 1、冒泡排序 ####

package com.lyp.sort;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class BubbleSort {
        
    
    	public static void main(String[] args) {
        
    		/*int arr[] = {3,9,-1,10,20};
    		System.out.println("排序前");
    		System.out.println(Arrays.toString(arr));
    		*/
    		
    		
    		//创建80000个的随机数组
    		int[] arr = new int[80000];
    		for(int i = 0; i < 80000; i++) {
        
    			arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000] 数
    		}
    		
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("排序前的时间是="+date1Str);
    		
    		//测试冒泡排序
    		bubbleSort(arr);
    		
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("排序后的时间是="+date2Str); //10秒
    		
    		//System.out.println("排序后");
    		//System.out.println(Arrays.toString(arr));
    		
    		/*
    		 * //第一趟排序，就是将最大的数排在最后 
    		//第二趟排序，就是将第二大的数排在倒数第二个位置
    				for(int j = 0; j < arr.length - 1 -1; j++) {
    					if (arr[j] > arr[j + 1]) {
    						temp = arr[j];
    						arr[j] = arr[j + 1];
    						arr[j + 1] = temp;
    					}
    					
    				}
    		System.out.println("第二趟排序的数组为：");
    		System.out.println(Arrays.toString(arr));		
    		
    		//第三趟排序，就是将第三大的数排在倒数第三个位置
    		for(int j = 0; j < arr.length - 1 -2; j++) {
    			if (arr[j] > arr[j + 1]) {
    				temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    			
    		}
    		System.out.println("第三趟排序的数组为：");
    		System.out.println(Arrays.toString(arr));	
    	
    	
    		//第四趟排序，就是将第四大的数排在倒数第四个位置
    		for(int j = 0; j < arr.length - 1 -3; j++) {
    			if (arr[j] > arr[j + 1]) {
    				temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    			
    		}
    		System.out.println("第四趟排序的数组为：");
    		System.out.println(Arrays.toString(arr));	
    		*/
    		
    	}
    	
    	public static void bubbleSort(int[] arr) {
        
    		int temp = 0;//临时变量
    		boolean flag = false;//标识变量，表示是否进行过交换
    		
    		//冒泡排序的时间复杂度 O(n^2）
    		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]) {
        //如果前面的数比后面的数大就进行交换
    					flag = true;
    					temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;
    				}
    				
    			}
    			//System.out.println("第"+(i+1)+"趟排序的数组为：");
    			//System.out.println(Arrays.toString(arr));
    			
    			if(flag == false) {
        //说明在一趟排序中，一次交换都没有发生
    				break;
    			}else {
        
    				flag = false;//重置flag,进行下次判断
    			}
    		}
    	}
    }

#### 2、选择排序 ####

package com.lyp.sort;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class SelectSort {
        
    
    	public static void main(String[] args) {
        
    
    		//int arr[] = {101,34,119,1};
    		
    		//创建80000个的随机数组
    		int[] arr = new int[80000];
    		for(int i = 0; i < 80000; i++) {
        
    			arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000] 数
    		}
    		
    		//System.out.println("排序前：");
    		//System.out.println(Arrays.toString(arr));
    		
    		
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("排序前的时间是="+date1Str);
    		
    		
    		selectSort(arr);
    		
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("排序后的时间是="+date2Str);//2~3秒
    		
    		//System.out.println("排序后：");
    		//System.out.println(Arrays.toString(arr));
    	}
    
    	//选择排序
    	public static void selectSort(int[] arr) {
        
    		//选择排序时间复杂度 O(n^2)
    		for(int i = 0; i < arr.length - 1; i++) {
        
    			int min = arr[i];
    			int minIndex = i;
    			for(int j = i + 1; j < arr.length; j++) {
        
    				if(min > arr[j]) {
        //说明假定的最小值，并不是最小值
    					min = arr[j];//重置min
    					minIndex = j;//重置minIndex
    				}
    			}
    			//将最小值，放在arr[i],即交换
    			if(minIndex != i) {
        
    				arr[minIndex] = arr[i];
    				arr[i] = min;
    			}
    			
    			//System.out.println("第"+(i+1)+"轮后：");
    			//System.out.println(Arrays.toString(arr));
    		}
    		
    		
    		
    		/*
    		//第一轮
    		int min = arr[0];
    		int minIndex = 0;
    		for(int j = 0 + 1; j < arr.length; j++) {
    			if(min > arr[j]) {//说明假定的最小值，并不是最小值
    				min = arr[j];//重置min
    				minIndex = j;//重置minIndex
    			}
    		}
    		//将最小值，放在arr[0],即交换
    		if(minIndex != 0) {
    			arr[minIndex] = arr[0];
    			arr[0] = min;
    		}
    		
    		System.out.println("第一轮后：");//1,34,119,101
    		System.out.println(Arrays.toString(arr));
    		
    		
    		//第二轮
    	    min = arr[1];
    		minIndex = 1;
    		for(int j = 0 + 2; j < arr.length; j++) {
    			if(min > arr[j]) {//说明假定的最小值，并不是最小值
    				min = arr[j];//重置min
    				minIndex = j;//重置minIndex
    			}
    		}
    		if(minIndex != 1) {
    			arr[minIndex] = arr[1];
    			arr[1] = min;
    		}
    		System.out.println("第二轮后：");//1,34,119,101
    		System.out.println(Arrays.toString(arr));
    		
    		//第三轮
    	    min = arr[2];
    		minIndex = 2;
    		for(int j = 0 + 3; j < arr.length; j++) {
    			if(min > arr[j]) {//说明假定的最小值，并不是最小值
    				min = arr[j];//重置min
    				minIndex = j;//重置minIndex
    			}
    		}
    		if(minIndex != 2) {
    			arr[minIndex] = arr[2];
    			arr[2] = min;
    		}
    		System.out.println("第三轮后：");//1,34,101,119
    		System.out.println(Arrays.toString(arr));
    		
    		
    		*/
    		
    	}
    }

#### 3、插入排序 ####

package com.lyp.sort;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class InsertSort {
        
    
    	public static void main(String[] args) {
        
    		//int arr[] = {101,34,119,11};
    		
    		//创建80000个的随机数组
    		int[] arr = new int[80000];
    		for(int i = 0; i < 80000; i++) {
        
    			arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000] 数
    		}
    		
    		
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("排序前的时间是="+date1Str);
    		
    		insertSort(arr);
    		
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("排序后的时间是="+date2Str);//1秒
    		
    		//System.out.println(Arrays.toString(arr));
    	}
    
    	//插入排序
    	public static void insertSort(int[] arr) {
        
    		
    		for(int i = 1; i < arr.length; i++) {
        
    			int insertVal = arr[i];//待插入的数
    			int insertIndex = i - 1;//即待插入数前面这个数的下标
    			//说明
    			//1.insertVal >= 0   保证在给insertVal 找插入位置，不越界
    			//2.insertVal < arr[insertIndex] 待插入的数还没有找到插入的位置
    			//3.就需要将arr[insertIndex] 后移
    			while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
        
    				arr[insertIndex + 1] = arr[insertIndex];
    				insertIndex--;
    			}
    			if(insertIndex + 1 != i) {
        
    				arr[insertIndex + 1] = insertVal;
    			}
    			
    			//System.out.println("第"+i+"轮：");
    			//System.out.println(Arrays.toString(arr));
    		}
    		
    
    		
    		
    		/*
    		//第一轮
    		int insertVal = arr[1];//待插入数
    		int insertIndex = 1 - 1;
    		while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
    			arr[insertIndex + 1] = arr[insertIndex];
    			insertIndex--;
    		}
    		arr[insertIndex + 1] = insertVal;
    		System.out.println("第一轮：");
    		System.out.println(Arrays.toString(arr));
    		
    		//第二轮
    		insertVal = arr[2];//待插入数
    		insertIndex = 2 - 1;
    		while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
    			arr[insertIndex + 1] = arr[insertIndex];
    			insertIndex--;
    		}
    		arr[insertIndex + 1] = insertVal;
    		System.out.println("第二轮：");
    		System.out.println(Arrays.toString(arr));
    		
    		//第三轮
    		insertVal = arr[3];//待插入数
    		insertIndex = 3 - 1;
    		while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
    			arr[insertIndex + 1] = arr[insertIndex];
    			insertIndex--;
    		}
    		arr[insertIndex + 1] = insertVal;
    		System.out.println("第三轮：");
    		System.out.println(Arrays.toString(arr));*/
    	}
    }

#### 4、希尔排序 ####

package com.lyp.sort;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class ShellSort {
        
    
    	public static void main(String[] args) {
        
    		//int[] arr = {8,9,1,7,2,3,5,4,6,0};
    		//创建80000个的随机数组
    		int[] arr = new int[8000000];
    		for(int i = 0; i < 8000000; i++) {
        
    			arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000] 数
    		}
    		
    		
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("排序前的时间是="+date1Str);
    		
    		//ShellSort(arr);//交换式
    		ShellSort2(arr);//移位式
    		
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("排序后的时间是="+date2Str);//0-1秒     8百万数据 2秒
    		
    		//System.out.println(Arrays.toString(arr));
    		
    	}
    
    	public static void ShellSort(int[] arr) {
        
    		
    		int temp = 0;
    		int count = 0;
    		for(int gap = arr.length / 2; gap > 0; gap /= 2) {
        
    			for(int i = gap; i < arr.length; i++) {
        
    				//遍历各组中的所有元素(共gap组)，步长gap
    				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;
    					}
    				}
    			}
    			//System.out.println("希尔排序第"+(++count)+"轮后="+Arrays.toString(arr));
    		}
    		
    		/*
    		//希尔排序 第一轮
    		//10个数据分成了5组
    		for(int i = 5; i < arr.length; i++) {
    			//遍历各组中的所有元素(共5组，每组2个元素)，步长5
    			for(int j = i - 5; j >= 0; j -=5) {
    				//如果当前元素大于加上步长后的那个元素，进行交换
    				if(arr[j] > arr[j + 5]) {
    					temp = arr[j];
    					arr[j] = arr[j + 5];
    					arr[j + 5] = temp;
    				}
    			}
    		}
    		System.out.println("希尔排序一轮后：");
    		System.out.println(Arrays.toString(arr));
    		
    		//希尔排序 第二轮
    		//10个数据分成了5/2=2组
    		for(int i = 2; i < arr.length; i++) {
    			for(int j = i - 2; j >= 0; j -=2) {
    				if(arr[j] > arr[j + 2]) {
    					temp = arr[j];
    					arr[j] = arr[j + 2];
    					arr[j + 2] = temp;
    				}
    			}
    		}
    		System.out.println("希尔排序二轮后：");
    		System.out.println(Arrays.toString(arr));
    		
    		//希尔排序 第二轮
    		//10个数据分成了2/2=1组
    		for(int i = 1; i < arr.length; i++) {
    			for(int j = i - 1; j >= 0; j -=1) {
    				if(arr[j] > arr[j + 1]) {
    					temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;
    				}
    			}
    		}
    		System.out.println("希尔排序三轮后：");
    		System.out.println(Arrays.toString(arr));*/
    	}
    	
    	//对交换式的希尔排序进行排序进行优化 -> 移位法
    	public static void ShellSort2(int[] arr) {
        
    		for(int gap = arr.length / 2; gap > 0; gap /= 2) {
        
    			for(int i = gap; i < arr.length; i++) {
        
    				int j = i;
    				int temp = arr[j];
    				if(arr[j] < arr[j - gap]) {
        
    					while(j - gap >=0 && temp < arr[j - gap]) {
        
    						arr[j] = arr[j - gap];
    						j -= gap;
    					}
    					//当while退出以后，就给temp 找到了待插入的位置
    					arr[j] = temp;
    				}
    			}
    		}
    	}
    }

#### 5、快速排序 ####

package com.lyp.sort;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class QuickSort {
        
    
    	public static void main(String[] args) {
        
    		//int[] arr = {-9,78,0,23,-567,70};
    		//创建80000个的随机数组
    		int[] arr = new int[8000000];
    		for(int i = 0; i < 8000000; i++) {
        
    			arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000] 数
    		}
    		
    		
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("排序前的时间是="+date1Str);
    		
    		quickSort(arr,0,arr.length-1);
    		
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("排序后的时间是="+date2Str);//0-1秒    8百万数据 1秒
    		
    		//System.out.println("arr="+Arrays.toString(arr));
    	}
    
    	public static void quickSort(int[] arr, int left,int right) {
        
    		int l = left;//左下标
    		int r = right;//右下标
    		int temp = 0;//临时变量，作为交换时使用
    		int pivot = arr[(left + right) / 2];//pivot 中轴值
    		while(l < r) {
        
    			//在piovt的左边一直找，找到大于等于pivot的值，才退出
    			while(arr[l] < pivot) {
        
    				l += 1;
    			}
    			//在piovt的右边一直找，找到小于等于pivot的值，才退出
    			while(arr[r] > pivot) {
        
    				r -= 1;
    			}
    			//如果 l >= r 说明pivot 的左右的值：
    			//左边全是小于等于pivot，右边全是大于等于pivot
    			if(l >= r) {
        
    				break;
    			}
    			//交换
    			temp = arr[l];
    			arr[l] = arr[r];
    			arr[r] = temp; 
    			
    			//如果交换完后，发现arr[l] == pivot 相等 r-- 前移
    			if(arr[l] == pivot) {
        
    				r -= 1;
    			}
    			
    			//如果交换完后，发现arr[r] == pivot 相等 l++ 前移
    			if(arr[r] == pivot) {
        
    				l += 1;
    			}
    		}
    		//如果 l == r,必须 l++,r--,否则出现栈溢出
    		if(l == r) {
        
    			l += 1;
    			r -= 1;
    		}
    		//向左递归
    		if(left < r) {
        
    			quickSort(arr,left,r);
    		}
    		//向右递归
    		if(right > l) {
        
    			quickSort(arr,l,right);
    		}
    	}
    }

#### 6、归并排序 ####

package com.lyp.sort;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class MergetSort {
        
    
    	public static void main(String[] args) {
        
    		//int arr[] = {8,4,5,7,1,3,6,2};//8—> merge 7 
    		
    		//创建80000个的随机数组
    		int[] arr = new int[8000000];
    		int temp[] = new int[arr.length];//归并需要一个额外的空间
    		for(int i = 0; i < 8000000; i++) {
        
    			arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000] 数
    		}
    		
    		
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("排序前的时间是="+date1Str);
    		
    		mergetSort(arr,0,arr.length-1,temp);
    		
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("排序后的时间是="+date2Str);//1秒以内      8百万数据 1秒
    		/*
    		
    		System.out.println("归并排序后的结果：");
    		System.out.println(Arrays.toString(arr));*/
    	}
    
    	//分 + 合方法
    	public static void mergetSort(int[] arr, int left, int right, int[] temp) {
        
    		if(left < right) {
        
    			int mid = (left + right)/2;//中间索引
    			//向左递归分解
    			mergetSort(arr,left,mid,temp);
    			//向右递归分解
    			mergetSort(arr,mid + 1,right,temp);
    			//合并
    			merge(arr,left,right,mid,temp);
    		}
    		
    	}
    	
    	//合并的方法
    	/**
    	 * 
    	 * @param arr 排序的原始数组
    	 * @param left 左边有序序列的初始索引
    	 * @param right 右边索引
    	 * @param mid 中间索引
    	 * @param temp 做中转的数组
    	 */
    	public static void merge(int[] arr, int left, int right, int mid ,int[] temp) {
        
    		int i = left;//初始化i,左边有序序列的初始索引
    		int j = mid + 1;//初始化j,右边有序序列的初始索引
    		int t = 0;//指向temp数组的当前索引
    		//1.先把左右两边（有序）序列按照规则填充到temp数组，直达有一边处理完毕为止
    		while(i <= mid && j <= right) {
        
    			//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
    			//即左边的当前元素填充到temp数组，然后t++ ,i++
    			if(arr[i] <= arr[j]) {
        
    				temp[t] = arr[i];
    				i += 1;
    				t += 1;
    			}else {
        //反之，将右边有序的当前元素，填充到temp数组
    				temp[t] = arr[j];
    				j += 1;
    				t += 1;
    			}
    		}
    		
    		//2.把有剩余数据的一边的数据依次全部填充到temp
    		while(i <= mid) {
        
    			temp[t] = arr[i];
    			i += 1;
    			t += 1;
    		}
    		while(j <= right) {
        
    			temp[t] = arr[j];
    			j += 1;
    			t += 1;
    		}
    		
    		//3.将temp数组的元素拷贝到arr
    		//注意，并不是每一次都是全部拷贝
    		t = 0;
    		int tempLeft = left;
    		//第一次合并 tempLeft = 0 ,right = 1 // tl=2,ri=3//tl=0,ri=3
    		//最后一次 tempLeft = 0 , right = 7
    		//System.out.println("tempLeft"+tempLeft+"right"+right);
    		while(tempLeft <= right) {
        
    			arr[tempLeft] = temp[t];
    			t += 1;
    			tempLeft += 1;
    		}
    	}
    }

#### 7、基数排序 ####

package com.lyp.sort;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class RadixSort {
        
    
    	public static void main(String[] args) {
        
    		//int[] arr = {53,3,542,748,14,214};
    		//创建80000个的随机数组
    		int[] arr = new int[80000];
    		int temp[] = new int[arr.length];//归并需要一个额外的空间
    		for(int i = 0; i < 80000; i++) {
        
    			arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000] 数
    		}
    		
    		
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("排序前的时间是="+date1Str);
    		
    		radixSort(arr);
    		
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("排序后的时间是="+date2Str);//1秒以内
    		//System.out.println("基数排序后"+Arrays.toString(arr));
    	}
    
    	
    	//基数排序方法
    	public static void radixSort(int[] arr) {
        
    		
    		//得到数组中最大数的位数
    		int max = arr[0];//假设第一个数就是最大数
    		for(int i = 1; i < arr.length; i++) {
        
    			if(arr[i] > max) {
        
    				max = arr[i];
    			}
    		}
    		//得到最大数是几位
    		int maxLength = (max + "").length();
    		
    		//定义一个二维数组，表示10个桶，每个桶就是一个一维数组
    		//说明
    		//1.二维数组包含10个一维数组
    		//2.为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
    		//3.基数排序是用空间换时间的经典算法
    		int[][] bucket = new int[10][arr.length];
    		
    		//为了记录每个桶，实际存放了多少数据，我们定义一个一维数组来记录各个桶每次放入的数据个数
    		//比如：bucketElementCount[0],记录的就是 bucket[0] 桶的放入数据个数
    		int[] bucketElementCounts = new int[10];
    		
    		for(int i = 0, n = 1;i < maxLength; i++,n *= 10) {
        
    			for(int j =0; j < arr.length; j++) {
        
    				//取出每个元素的某位数，第一轮个位，第二轮十位，第三轮百位。。。
    				int digitOfElement = arr[j] / n % 10;
    				//放入对应的桶中
    				bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    				bucketElementCounts[digitOfElement]++;
    			}
    			//按照这个桶的顺序（一维数组的下标依次除去数据，放入原来的数组）
    			int index = 0;
    			//遍历每一个桶,并将桶中数据放入原数组
    			for(int k = 0; k < bucketElementCounts.length; k++) {
        
    				//如果桶中有数据，才放入原数组中
    				if(bucketElementCounts[k] != 0) {
        
    					//循环该桶，即第k个桶，放入原数组
    					for(int l = 0; l < bucketElementCounts[k]; l++) {
        
    						arr[index++] = bucket[k][l];
    					}
    				}
    				//第i + 1轮处理后，需要将每个 bucketElementCounts[k] = 0 !!!
    				bucketElementCounts[k] = 0;
    			}
    			
    			//System.out.println("第"+(i + 1)+"轮对于某位的排序处理:array="+Arrays.toString(arr));
    		}
    		
    		
    		/*
    		//第一轮（针对每个元素的个位进行排序处理）
    		for(int j =0; j < arr.length; j++) {
    			//取出每个元素的个位数
    			int digitOfElement = arr[j] % 10;
    			//放入对应的桶中
    			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    			bucketElementCounts[digitOfElement]++;
    		}
    		//按照这个桶的顺序（一维数组的下标依次除去数据，放入原来的数组）
    		int index = 0;
    		//遍历每一个桶,并将桶中数据放入原数组
    		for(int k = 0; k < bucketElementCounts.length; k++) {
    			//如果桶中有数据，才放入原数组中
    			if(bucketElementCounts[k] != 0) {
    				//循环该桶，即第k个桶，放入原数组
    				for(int l = 0; l < bucketElementCounts[k]; l++) {
    					arr[index++] = bucket[k][l];
    				}
    			}
    			//第一轮处理后，需要将每个 bucketElementCounts[k] = 0 !!!
    			bucketElementCounts[k] = 0;
    		}
    		
    		System.out.println("第1轮对于个位的排序处理:array="+Arrays.toString(arr));
    		
    		//=======================================================================
    		
    		//第二轮（针对每个元素的十位进行排序处理）
    		for(int j =0; j < arr.length; j++) {
    			//取出每个元素的十位数
    			int digitOfElement = arr[j] /10 % 10;
    			//放入对应的桶中
    			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    			bucketElementCounts[digitOfElement]++;
    		}
    		//按照这个桶的顺序（一维数组的下标依次除去数据，放入原来的数组）
    		index = 0;
    		//遍历每一个桶,并将桶中数据放入原数组
    		for(int k = 0; k < bucketElementCounts.length; k++) {
    			//如果桶中有数据，才放入原数组中
    			if(bucketElementCounts[k] != 0) {
    				//循环该桶，即第k个桶，放入原数组
    				for(int l = 0; l < bucketElementCounts[k]; l++) {
    					arr[index++] = bucket[k][l];
    				}
    			}
    			//第二轮处理后，需要将每个 bucketElementCounts[k] = 0 !!!
    			bucketElementCounts[k] = 0;
    		}
    		System.out.println("第2轮对于十位的排序处理:array="+Arrays.toString(arr));
    		
    		//=======================================================================
    		
    		//第三轮（针对每个元素的百位进行排序处理）
    		for(int j =0; j < arr.length; j++) {
    			//取出每个元素的百位数
    			int digitOfElement = arr[j] /100 % 10;
    			//放入对应的桶中
    			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    			bucketElementCounts[digitOfElement]++;
    		}
    		//按照这个桶的顺序（一维数组的下标依次除去数据，放入原来的数组）
    		index = 0;
    		//遍历每一个桶,并将桶中数据放入原数组
    		for(int k = 0; k < bucketElementCounts.length; k++) {
    			//如果桶中有数据，才放入原数组中
    			if(bucketElementCounts[k] != 0) {
    				//循环该桶，即第k个桶，放入原数组
    				for(int l = 0; l < bucketElementCounts[k]; l++) {
    					arr[index++] = bucket[k][l];
    				}
    			}
    		}
    		System.out.println("第3轮对于百位的排序处理:array="+Arrays.toString(arr));*/
    		
    	}
    	
    }

#### 8、堆排序 ####

package com.lyp.tree;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class HeapSort {
        
    
    	public static void main(String[] args) {
        
    		//int[] arr = {4,6,8,5,9};
    		//创建80000个的随机数组
    		int[] arr = new int[8000000];
    		for(int i = 0; i < 8000000; i++) {
        
    			arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000] 数
    		}
    		
    		//System.out.println("排序前：");
    		//System.out.println(Arrays.toString(arr));
    		
    		
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("排序前的时间是="+date1Str);
    		
    		heapSort(arr);
    		
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("排序后的时间是="+date2Str);//1秒 8百万数据
    		
    	}
    
    	public static void heapSort(int arr[]) {
        
    		int temp = 0;
    		System.out.println("堆排序！！！");
    		
    //		//分布完成
    //		adjustHeap(arr,1,arr.length);
    //		System.out.println("第1次"+Arrays.toString(arr));//4,9,8,5,6
    //		
    //		adjustHeap(arr,0,arr.length);
    //		System.out.println("第2次"+Arrays.toString(arr));//9,6,8,5,4
    		
    		//完成最终代码
    		//将无序序列构成一个堆，根据升序降序需求选择大顶堆或小顶堆
    		for(int i = arr.length / 2 - 1; i >= 0; i--) {
        
    			adjustHeap(arr,i,arr.length);
    		}
    		
    		/**
    		 * 将堆顶元素与末尾元素交换，将最大元素“沉底”到数组末端
    		 * 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整 +交换步骤，直到整个有序序列有序
    		 * 
    		 */
    		
    		for(int j = arr.length - 1; j > 0; j--) {
        
    			//交换
    			temp = arr[j];
    			arr[j] = arr[0];
    			arr[0] = temp;
    			adjustHeap(arr,0,j);
    		}
    		
    		//System.out.println("数组="+ Arrays.toString(arr));
    	
    	}
    	
    	public static void adjustHeap(int[] arr, int i, int length) {
        
    		int temp = arr[i];
    		for(int k = (i * 2 + 1); k < length;  k = (k * 2 + 1)) {
        
    			if(k + 1 < length && arr[k] < arr[k+1]) {
        
    				k++;
    			}
    			if(arr[k] > temp) {
        
    				arr[i] = arr[k];
    				i = k;
    			} else {
        
    				break;
    			}
    		}
    		arr[i] = temp;
    	}
    }

[https_blog.csdn.net_weixin_46822367_article_details_115478461_spm_1001.2014.3001.5502]: https://blog.csdn.net/weixin_46822367/article/details/115478461?spm=1001.2014.3001.5502