深圳网站论坛建设,七零三八零四温州论坛,网站建设合同怎么交印花税,站长之家psd文章目录归并排序递归方法实现非递归方法实现求数组的小和求数组的降序对个数快排荷兰国旗问题#xff08;Partition过程#xff09;快排1.0快排2.0快排3.0堆大根堆堆排序使用堆排序归并排序
递归方法实现
public class Code01_MergeSort {// 递归方法实现public static vo…
文章目录归并排序递归方法实现非递归方法实现求数组的小和求数组的降序对个数快排荷兰国旗问题Partition过程快排1.0快排2.0快排3.0堆大根堆堆排序使用堆排序归并排序
递归方法实现
public class Code01_MergeSort {// 递归方法实现public static void mergeSort1(int[] arr) {if (arr null || arr.length 2) {return;}process(arr, 0, arr.length - 1);}// 请把arr[L..R]排有序// l...r N// T(N) 2 * T(N / 2) O(N)// O(N * logN)public static void process(int[] arr, int L, int R) {if (L R) { // base casereturn;}int mid L ((R - L) 1);process(arr, L, mid);process(arr, mid 1, R);merge(arr, L, mid, R);}public static void merge(int[] arr, int L, int M, int R) {int[] help new int[R - L 1];int i 0;int p1 L;int p2 M 1;while (p1 M p2 R) {help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}// 要么p1越界了要么p2越界了while (p1 M) {help[i] arr[p1];}while (p2 R) {help[i] arr[p2];}for (i 0; i help.length; i) {arr[L i] help[i];}}}非递归方法实现
public static void mergeSort2(int[] arr) {if (arr null || arr.length 2) {return;}int N arr.length;// 步长int mergeSize 1;while (mergeSize N) { // log N// 当前左组的第一个位置int L 0;while (L N) {if (mergeSize N - L) {break;}int M L mergeSize - 1;int R M Math.min(mergeSize, N - M - 1);merge(arr, L, M, R);L R 1;}// 防止溢出if (mergeSize N / 2) {break;}mergeSize 1;}
} 求数组的小和
在一个数组中一个数数左边比它小的数的总和,叫数的小和所有数的小和累加起来,叫数组的小和 一个数右边有多少个数比他 大
public class Code02_SmallSum {public static int smallSum(int[] arr) {if (arr null || arr.length 2) {return 0;}return process(arr, 0, arr.length - 1);}// arr[L..R]既要排好序也要求小和返回// 所有merge时产生的小和累加// 左 排序 merge// 右 排序 merge// mergepublic static int process(int[] arr, int l, int r) {if (l r) {return 0;}// l rint mid l ((r - l) 1);return process(arr, l, mid) process(arr, mid 1, r) merge(arr, l, mid, r);}public static int merge(int[] arr, int L, int m, int r) {int[] help new int[r - L 1];int i 0;int p1 L;int p2 m 1;int res 0;while (p1 m p2 r) {res arr[p1] arr[p2] ? (r - p2 1) * arr[p1] : 0;help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}while (p1 m) {help[i] arr[p1];}while (p2 r) {help[i] arr[p2];}for (i 0; i help.length; i) {arr[L i] help[i];}return res;}
}求数组的降序对个数
一个数左边有多少个数比他 大
public class Code03_ReversePair {public static int reverPairNumber(int[] arr) {if (arr null || arr.length 2) {return 0;}return process(arr, 0, arr.length - 1);}// arr[L..R]既要排好序也要求逆序对数量返回// 所有merge时产生的逆序对数量累加返回// 左 排序 merge并产生逆序对数量// 右 排序 merge并产生逆序对数量public static int process(int[] arr, int l, int r) {if (l r) {return 0;}// l rint mid l ((r - l) 1);return process(arr, l, mid) process(arr, mid 1, r) merge(arr, l, mid, r);}public static int merge(int[] arr, int L, int m, int r) {int[] help new int[r - L 1];int i help.length - 1;int p1 m;int p2 r;int res 0;while (p1 L p2 m) {res arr[p1] arr[p2] ? (p2 - m) : 0;help[i--] arr[p1] arr[p2] ? arr[p1--] : arr[p2--];}while (p1 L) {help[i--] arr[p1--];}while (p2 m) {help[i--] arr[p2--];}for (i 0; i help.length; i) {arr[L i] help[i];}return res;}
}时间复杂度 N*logN
快排
荷兰国旗问题Partition过程
public class Code02_PartitionAndQuickSort {public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}// arr[L..R]上以arr[R]位置的数做划分值// X X// X Xpublic static int partition(int[] arr, int L, int R) {if (L R) {return -1;}if (L R) {return L;}int lessEqual L - 1;int index L;while (index R) {if (arr[index] arr[R]) {swap(arr, index, lessEqual);}index;}swap(arr, lessEqual, R);return lessEqual;}// arr[L...R] 玩荷兰国旗问题的划分以arr[R]做划分值// arr[R] arr[R] arr[R]public static int[] netherlandsFlag(int[] arr, int L, int R) {if (L R) { // L...R LRreturn new int[] { -1, -1 };}if (L R) {return new int[] { L, R };}int less L - 1; // 区 右边界int more R; // 区 左边界int index L;while (index more) { // 当前位置不能和 区的左边界撞上if (arr[index] arr[R]) {index;} else if (arr[index] arr[R]) {
// swap(arr, less 1, index);
// less;
// index; swap(arr, index, less);} else { // swap(arr, index, --more);}}swap(arr, more, R); // [R] [R] [R]return new int[] { less 1, more };}}快排1.0
O(N^2) 和 两个区域 public static void quickSort1(int[] arr) {if (arr null || arr.length 2) {return;}process1(arr, 0, arr.length - 1);}public static void process1(int[] arr, int L, int R) {if (L R) {return;}// L..R partition arr[R] [ arr[R] arr[R] arr[R] ]int M partition(arr, L, R);process1(arr, L, M - 1);process1(arr, M 1, R);}快排2.0
O(N^2) 相比于1.0 三个区域 public static void quickSort2(int[] arr) {if (arr null || arr.length 2) {return;}process2(arr, 0, arr.length - 1);}// arr[L...R] 排有序快排2.0方式public static void process2(int[] arr, int L, int R) {if (L R) {return;}// [ equalArea[0] , equalArea[0]]int[] equalArea netherlandsFlag(arr, L, R);process2(arr, L, equalArea[0] - 1);process2(arr, equalArea[1] 1, R);}快排3.0
O(NlogN) 相比于2.0在数组中随机选择一个数,和arr[R]交换开始2.0 public static void quickSort3(int[] arr) {if (arr null || arr.length 2) {return;}process3(arr, 0, arr.length - 1);}public static void process3(int[] arr, int L, int R) {if (L R) {return;}swap(arr, L (int) (Math.random() * (R - L 1)), R);int[] equalArea netherlandsFlag(arr, L, R);process3(arr, L, equalArea[0] - 1);process3(arr, equalArea[1] 1, R);}堆
结构上完全二叉树
大根堆
public class Code02_Heap {public static class MyMaxHeap {private int[] heap;private final int limit;private int heapSize;public MyMaxHeap(int limit) {heap new int[limit];this.limit limit;heapSize 0;}public boolean isEmpty() {return heapSize 0;}public boolean isFull() {return heapSize limit;}public void push(int value) {if (heapSize limit) {throw new RuntimeException(heap is full);}heap[heapSize] value;// value heapSizeheapInsert(heap, heapSize);}// 用户此时让你返回最大值并且在大根堆中把最大值删掉// 剩下的数依然保持大根堆组织public int pop() {int ans heap[0];swap(heap, 0, --heapSize);heapify(heap, 0, heapSize);return ans;}// 新加进来的数现在停在了index位置请依次往上移动// 移动到0位置或者干不掉自己的父亲了停private void heapInsert(int[] arr, int index) {// [index] [index-1]/2// index 0while (arr[index] arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index (index - 1) / 2;}}// 从index位置往下看不断的下沉// 停较大的孩子都不再比index位置的数大已经没孩子了private void heapify(int[] arr, int index, int heapSize) {int left index * 2 1;while (left heapSize) { // 如果有左孩子有没有右孩子可能有可能没有// 把较大孩子的下标给largestint largest left 1 heapSize arr[left 1] arr[left] ? left 1 : left;largest arr[largest] arr[index] ? largest : index;if (largest index) {break;}// index和较大孩子要互换swap(arr, largest, index);index largest;left index * 2 1;}}private void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}}
}堆排序
public class Code03_HeapSort {// 堆排序额外空间复杂度O(1)public static void heapSort(int[] arr) {if (arr null || arr.length 2) {return;}// O(N*logN)
// for (int i 0; i arr.length; i) { // O(N)
// heapInsert(arr, i); // O(logN)
// }// O(N)for (int i arr.length - 1; i 0; i--) {heapify(arr, i, arr.length);}int heapSize arr.length;swap(arr, 0, --heapSize);// O(N*logN)while (heapSize 0) { // O(N)heapify(arr, 0, heapSize); // O(logN)swap(arr, 0, --heapSize); // O(1)}}// arr[index]刚来的数往上public static void heapInsert(int[] arr, int index) {while (arr[index] arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index (index - 1) / 2;}}// arr[index]位置的数能否往下移动public static void heapify(int[] arr, int index, int heapSize) {int left index * 2 1; // 左孩子的下标while (left heapSize) { // 下方还有孩子的时候// 两个孩子中谁的值大把下标给largest// 1只有左孩子left - largest// 2) 同时有左孩子和右孩子右孩子的值 左孩子的值left - largest// 3) 同时有左孩子和右孩子并且右孩子的值 左孩子的值 right - largestint largest left 1 heapSize arr[left 1] arr[left] ? left 1 : left;// 父和较大的孩子之间谁的值大把下标给largestlargest arr[largest] arr[index] ? largest : index;if (largest index) {break;}swap(arr, largest, index);index largest;left index * 2 1;}}public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}
}使用堆排序
已知一个几乎有序的数组。几乎有序是指如果把数组排好顺序的话每个元素移动的距离一定不超过k,并且k相对于数组长度来说是比较小的时间复杂度N*logK。
// 默认小根堆
PriorityQueueInteger heap new PriorityQueue();public class Code04_SortArrayDistanceLessK {public static void sortedArrDistanceLessK(int[] arr, int k) {if (k 0) {return;}// 默认小根堆PriorityQueueInteger heap new PriorityQueue();int index 0;// 0...K-1for (; index Math.min(arr.length - 1, k - 1); index) {heap.add(arr[index]);}int i 0;for (; index arr.length; i, index) {heap.add(arr[index]);arr[i] heap.poll();}while (!heap.isEmpty()) {arr[i] heap.poll();}}
}
