堆及堆排序、快速排序、歸并排序
Java構(gòu)建堆，以及實(shí)現(xiàn)堆排序，堆實(shí)質(zhì)是一棵完全二叉樹，這里用數(shù)組表示
一個(gè)完全二叉樹，即堆，堆可分為小頂堆、大頂堆，堆化可分為從上到下和
從下到上兩種方式。
public static class Heap{private List<Integer> list = new ArrayList<>();public void build(Integer[] arr) {//堆其實(shí)質(zhì)是一個(gè)完全二叉樹 用數(shù)組表示時(shí) i節(jié)點(diǎn)對(duì)應(yīng)的左子節(jié)點(diǎn)為2i，右子節(jié)點(diǎn)為2i+1//假設(shè)數(shù)組長度為n 則n-1標(biāo)的父節(jié)點(diǎn)為 (n-1)/2 因此 (n-1)/2+1 到 n-1節(jié)點(diǎn)均為葉子節(jié)點(diǎn) 不需要堆化 我們只需要堆化0到(n-1)/2的元素for(int i=arr.length-1/2; i>=0; i--) {heapify(arr, arr.length-1, i);}this.list = new ArrayList<>(Arrays.asList(arr));}/*** 插入的核心思想是 將元素先追加到數(shù)組后面 然后從下向上進(jìn)行堆化* @param val*/public void insert(int val) {list.add(val);int pos = list.size() - 1;//父節(jié)點(diǎn)的index > 0 and 父節(jié)點(diǎn)的值小于當(dāng)前子節(jié)點(diǎn)的值while ((pos-1)/2 >= 0 && list.get(pos) > list.get((pos-1)/2)) {int parent = (pos-1)/2;//子節(jié)點(diǎn)和父節(jié)點(diǎn)的數(shù)據(jù)做交換swap(pos, parent);//設(shè)置當(dāng)前位移為父節(jié)點(diǎn) 繼續(xù)向上堆化pos = parent;}}/*** 數(shù)據(jù)交換* @param a* @param b*/private void swap(int a, int b) {int temp = list.get(a);list.set(a, list.get(b));list.set(b, temp);}/*** 刪除堆頂元素* 思路是將堆頂元素刪除，然后將排在最后的元素移到堆頂*/public int removeMax() {int max = list.get(0);//數(shù)據(jù)交換swap(0, list.size() - 1);list.remove(list.size()-1);//數(shù)組轉(zhuǎn)化Integer[] arr = list.toArray(new Integer[list.size()]);//從上到下堆化heapify(arr, list.size() - 1, 0);this.list = new ArrayList<>(Arrays.asList(arr));return max;}}/*** 堆排序*/public static void sort(Integer arr[]) {//1.先構(gòu)建堆buildHeap(arr);//2.再排序int k = arr.length-1;while (k > 0) {//將堆頂元素和最后的元素進(jìn)行交換 將最大的元素沉底swap(arr, 0, k);//對(duì)0到k-1的元素重新堆化 因?yàn)槎秧敩F(xiàn)在不是最大的數(shù)了heapify(arr, --k, 0);}printAll(arr);}public static void printAll(Integer arr[]) {for (int i : arr) {System.out.print(i + ", ");}}/*** 一個(gè)無序數(shù)組 構(gòu)建一個(gè)堆* @param arr*/public static void buildHeap(Integer[] arr) {//堆其實(shí)質(zhì)是一個(gè)完全二叉樹 用數(shù)組表示時(shí) i節(jié)點(diǎn)對(duì)應(yīng)的左子節(jié)點(diǎn)為2i，右子節(jié)點(diǎn)為2i+1//假設(shè)數(shù)組長度為n 則n-1標(biāo)的父節(jié)點(diǎn)為 (n-1)/2 因此 (n-1)/2+1 到 n-1節(jié)點(diǎn)均為葉子節(jié)點(diǎn) 不需要堆化 我們只需要堆化0到(n-1)/2的元素for(int i=arr.length-1/2; i>=0; i--) {heapify(arr, arr.length-1, i);}}/*** 從上到下堆化* @param arr* @param i*/public static void heapify(Integer[] arr, int n, int i) {while (true) {int maxPos = i;//當(dāng)前節(jié)點(diǎn)和左子節(jié)點(diǎn)比較if(2*i+1 <= n && arr[maxPos] < arr[2*i + 1]) {maxPos = 2*i+1;}//當(dāng)前節(jié)點(diǎn)和右子節(jié)點(diǎn)比較if(2*i+2 <= n && arr[maxPos] < arr[2*i + 2]) {maxPos = 2*i+2;}//如果當(dāng)前節(jié)點(diǎn)大于左右子節(jié)點(diǎn) 則結(jié)束循環(huán)if(maxPos == i) {break;}swap(arr, maxPos, i);i = maxPos;}}public static void swap(Integer[] arr, int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}快排和歸并排序：
public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);}/*** 快速排序* 1：以第一個(gè)數(shù)為中位數(shù)，比中位數(shù)大的數(shù)移動(dòng)到中位數(shù)左邊，比中位數(shù)小的數(shù)移動(dòng)到中位數(shù)右邊 最后返回中位數(shù)的下標(biāo)* 2：接著遞歸排序[0-中位數(shù)下標(biāo)]和[中位數(shù)下標(biāo)+1，length-1] 兩個(gè)子集 直到 low >= high 退出循環(huán)* @param arr*/public static void quickSort(int[] arr, int low, int high) {if(arr == null || arr.length <= 1 || low >= high) {return;}int midIndex = partition(arr, low, high);quickSort(arr, low, midIndex);quickSort(arr, midIndex + 1, high);}/*** 找到中位數(shù)下標(biāo)* @param arr* @param low* @param high* @return*/public static int partition(int[] arr, int low, int high) {int midValue = arr[low];while (low < high) {//從右向左移動(dòng)while (low < high && arr[high] >= midValue) {high--;}if(low < high) {arr[low] = arr[high];low++;}while (low < high && arr[low] <= midValue) {low++;}if(low < high) {arr[high] = arr[low];high--;}}arr[low] = midValue;return low;}public static void swap(int[] arr, int low, int high) {int temp = arr[low];arr[low] = arr[high];arr[high] = temp;}public static void mergeSort(int[] arr) {mergeSort(arr, 0, arr.length - 1);}public static void mergeSort(int[] arr, int low, int high) {if(low >= high) {return;}int mid = (low + high) / 2;mergeSort(arr, low, mid);mergeSort(arr, mid+1, high);mergeArr(arr, low, mid, high);}public static void mergeArr(int[] arr, int low, int mid, int high){if(low >= high) {return;}int i=0,j = 0,k=0;int arrTemp[] = new int[high - low + 1];while (low + i <= mid || high >= mid + 1 + j) {if(low + i <= mid && arr[low + i] <= arr[mid + 1 + j]) {arrTemp[k++] = arr[low + i];i++;}if(low + i > mid) {while (mid + 1 + j <= high) {arrTemp[k++] = arr[mid + 1 + j];j++;}break;}if(mid + 1 + j <= high && arr[low + i] > arr[mid + 1 + j]) {arrTemp[k++] = arr[mid + 1 + j];j++;}if(mid + 1 + j > high) {while (low + i <= mid) {arrTemp[k++] = arr[low + i];i++;}break;}}for (int a=0; a<arrTemp.length; a++) {arr[low + a] = arrTemp[a];}}
評(píng)論
圖片
表情