算法练习day2——190319（大顶堆、冒泡、选择、插入）
1.实现大顶堆，用于排序
步骤：
- 从数组一半的位置开始建堆；
- 不断调整，使最大元素位于顶上
- 调整的过程：使根、左孩子、右孩子中的最大值位于根位置；
- 交换顶元素和末位置元素，同时元素个数-1
- -1是为了避免已换好的元素再参与比较交换
- 换好后，再次从顶部进行调整（因为交换后，顶元素已不是最大的了）
package Heap;public class Test {static int len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量public static void main(String[] args) {int[] array= {4,7,2,8,9,1,3,6,5,0};System.out.println("before:");for(int i=0;i= 0; i--) {//建堆，顶为最大heapify(arr, i);}}public static void heapify(int[]arr, int i) {// 堆调整System.out.println("i:"+i);int left = 2 * i + 1,right = 2 * i + 2,largest = i;if (left < len && arr[left] > arr[largest]) {largest = left;}if (right < len && arr[right] > arr[largest]) {largest = right;}if (largest != i) { swap(arr, i, largest);heapify(arr, largest);//换值后要对被换根的子树进行调整}}public static void swap(int[] arr,int i,int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void heapSort(int[] arr) {buildMaxHeap(arr);//先建一个大顶堆，最大值在顶部，即数组0位置for (int i = arr.length - 1; i > 0; i--) {swap(arr, 0, i);//将最大值换到最后一个位置len--; //长度-1，最后一个位置的数就不参与比较置换了，它已为目前的最大值heapify(arr, 0);//将顶元素和最后一个元素交换后再进行堆调整} }} 2.冒泡排序
public class BubbleSort {public static void bubbleSort(int[] arr) {if(arr==null||arr.length<2)return;for(int end=arr.length-1;end>0;end--) {//end为每次比较的范围//第一次比：0~n-1//第二次比：0~n-1//...for(int i=0;iarr[i+1])swap(arr,i,i+1);}}}public static void swap(int[] arr,int i,int j) {int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}
} 时间复杂度的计算：
第一次：0~n-1——n次
第二次：0~n-2——n-1次
...
总共：
3.选择排序
第一次比较0~n-1，最小的放在0位置；
第二次比较1~n-1，最小的放在1位置；
...
public class SelectSort {public static void selectSort(int[] arr) {if(arr==null||arr.length<2)return;for(int i=0;i时间复杂度还是
冒泡排序和选择排序在工程上不怎么用。
它们的比较流程已确定，和元素具体是什么情况无关，都得比较，有序的话只是不交换而已。
4.插入排序
public class InsertSort {public static void insertSort(int[] arr) {if(arr==null||arr.length<2)return;for(int i=1;i-1;j--)//每次需要比较的元素if(arr[j] 分最好、最坏和平均。
最好：已有序，且和要求的顺序一致；每次只需和最后一个元素比较，
平均：乱序；
最坏：有序，但和要求顺序相反。每次都需要比较到头，
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！