排序算法------堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父结点。

时间复杂度：O（n1og2n）空间复杂度：O（1）稳定性：不稳定 先堆化 package 排序算法; import java.util.Arrays; import java.util.Random; public class HeapSort { public static void main(String[] args) { int arr[]=new int[20]; Random random=new Random(); for (int i=0;i<arr.length;i++){ arr[i]=random.nextInt(50); } heapSort(arr); System.out.println(Arrays.toString(arr)); } private static int len; private static void heapSort(int[] arr) { len=arr.length; //1.将传入的数组堆化 heapify heapify(arr); //2.将最大值与最后一个元素交换 再heapify() for(int i=arr.length-1;i>=0;i--){ swap(arr,0,i); len--; heapify(arr); } } private static void heapify(int [] arr) { for (int i=len-1;i>=0;i--){ siftDown(arr,i); } } private static void siftDown(int[] arr, int k) { while (leftChild(k)<len){ int j=leftChild(k); if (j+1<len&&arr[j+1]>arr[j]){ j=rightChild(k); } if (arr[k]<arr[j]){ swap(arr,k,j); k=j; }else { break; } } } private static void swap (int [] arr,int i,int j){ int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } private static int leftChild(int i){ return i*2+1; } private static int rightChild(int i){ return i*2+2; }private static int parent(int i){ return (i-1)/2; } }

执行结果

[0, 6, 8, 15, 16, 17, 18, 19, 20, 23, 30, 30, 31, 32, 39, 40, 41, 42, 44, 47]

测试（完全随机）

package 排序算法; import java.util.Arrays; import java.util.Random; public class TestSort { /* 数据分布情况 1.完全随机 2.大致有序 3.方差小 */ public static int[] getTotalRandom(){ Random random=new Random(); int [] arr=new int[10000]; for (int i=0;i<arr.length;i++){ arr[i]=random.nextInt(10000); } return arr; } public static void main(String[] args) { int [] arr1=getTotalRandom(); int [] arr2= Arrays.copyOf(arr1, arr1.length); int [] arr3= Arrays.copyOf(arr1, arr1.length); int [] arr4= Arrays.copyOf(arr1, arr1.length); int [] arr5= Arrays.copyOf(arr1, arr1.length); int [] arr6= Arrays.copyOf(arr1, arr1.length); testSelectionSort(arr1); testBubbleSort(arr2); testInsertSort(arr3); testShellSort(arr4); testMergSort(arr5); testHeapSort(arr6); } private static void testHeapSort(int[] arr6) { long startTime=System.currentTimeMillis(); HeapSort.heapSort(arr6); long endTime=System.currentTimeMillis(); System.out.println("堆排序"+(endTime-startTime)); } private static void testInsertSort(int[] arr3) { long startTime=System.currentTimeMillis(); BubbleSort.bubbleSort(arr3); long endTime=System.currentTimeMillis(); System.out.println("冒泡排序"+(endTime-startTime)); } private static void testBubbleSort(int[] arr2) { long startTime=System.currentTimeMillis(); insertionSort.lnsertionSortUpper(arr2); long endTime=System.currentTimeMillis(); System.out.println("插入排序"+(endTime-startTime)); } private static void testSelectionSort(int[] arr) { long startTime=System.currentTimeMillis(); SelectionSort.selectionSort(arr); long endTime=System.currentTimeMillis(); System.out.println("选择排序"+(endTime-startTime)); } private static void testShellSort(int[] arr) { long startTime=System.currentTimeMillis(); ShellSort.shellSort(arr); long endTime=System.currentTimeMillis(); System.out.println("希尔排序"+(endTime-startTime)); } private static void testMergSort(int[] arr) { long startTime=System.currentTimeMillis(); MergSort.mergSort(arr,0,arr.length-1); long endTime=System.currentTimeMillis(); System.out.println("归并排序"+(endTime-startTime)); } }

执行结果

选择排序182 插入排序12 冒泡排序148 希尔排序4 归并排序23 堆排序168

大致有序里面归并比插入稍快