Java数据结构与算法: https://blog.csdn.net/weixin_46822367/article/details/115478461?spm=1001.2014.3001.5502.
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://www.bmabk.com/index.php/post/123094.html
