一周刷爆LeetCode，左程云老师-认识O(N * logN)的排序

认识O(N * logN)的排序

归并排序

1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序

2）让其整体有序的过程里用了排外序方法
3）利用master公式来求解时间复杂度

4 ）归并排序的实质

时间复杂度O(N*logN)，额外空间复杂度0(N)

package Unit2;public class Code1_MergeSort
{public static void mergeSort(int []arr){if (arr == null || arr.length < 2){return;}mergeSort(arr, 0, arr.length - 1);}private static void mergeSort(int[] arr, int l, int r){// 先左边排好顺序，再右边排好顺序，然后合并if (l == r){return ;}// mid = (l + r) / 2 = l + (r - l) / 2 = l + (r - l) >> 1int mid = l + ((r - l) >> 1);mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);merge(arr, l, mid, r);}private static void merge(int[] arr, int l, int mid, int r){int []help = new int[r - l + 1];int index = 0;int p1 = l;int p2 = mid + 1;// 两段都没有走完while (p1 <= mid && p2 <= r){help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}// 剩下的部分复制while (p1 <= mid){help[index++] = arr[p1++];}while (p2 <= r){help[index++] = arr[p2++];}// 拷贝到原函数for (index = 0; index < help.length; index++){arr[l + index] = help[index];}}public static void printArray(int[] arr){if (arr == null){return ;}for (int i = 0; i < arr.length; i ++){System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args){int []a = {1,3, 8, 4,2,9};printArray(a);System.out.println("====Sorting====");mergeSort(a);printArray(a);}
}
/*
1 3 8 4 2 9 
====Sorting====
1 2 3 4 8 9 
*/

归并排序的拓展（小和问题和逆序对问题）

小和问题 ——在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组 的小和。求一个数组 的小和。 例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左 边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、 2; 所以小和为1+1+3+1+1+3+4+2=16

逆序对问题 ——在一个数组中，左边的数如果比右边的数大，则折两个数 构成一个逆序对，请打印所有逆序

小和问题解题思路：我们可以利用归并排序的算法求和，把数组分成左半部分和右半部分，当左半部分和右半部分排好序后，我们假设左边数M比右边数N小，假设左边数组下标范围[L…Mid]右边数组下标范围[Mid+1…R] 则相加(R-N的下标+1)*左边数M的值

package Unit2;public class Code2_SmallSum
{public static int MergeSort(int []arr){if (arr == null || arr.length < 2){return 0;}return MergeSort(arr, 0, arr.length - 1);}private static int MergeSort(int[] arr, int l, int r){if (l == r){return 0;}int mid = l + ((r - l) >> 1);return MergeSort(arr, l, mid)+MergeSort(arr, mid + 1, r)+Merge(arr, l, mid, r);}private static int Merge(int[] arr, int l, int mid, int r){int []help = new int[r - l + 1];int index = 0;int p1 = l, p2 = mid + 1;int sum = 0;while (p1 <= mid && p2 <= r){sum += (arr[p1] < arr[p2]) ? (r - p2 + 1) * arr[p1]: 0;help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= mid){help[index++] = arr[p1++];}while (p2 <= r){help[index++] = arr[p2++];}for (index = 0; index < help.length; index++){arr[l + index] = help[index];}return sum;}public static void PrintArray(int[] arr){if (arr == null){return ;}for (int i = 0; i < arr.length; i++){System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args){int []a = {1,3,4,2,5};int sum = MergeSort(a);PrintArray(a);System.out.println("sum = " + sum);}
}
/*1 2 3 4 5 
16
*/

逆序对问题解题思路：前面思路都一样，重点是给数组左右两边排好序后，假设arr[p1] > arr[p2], 则在p1 - mid之间的所有元素都可以和p2构成逆序对, 个数是mid - p1 + 1

package Unit2;public class Code2_0_ReverseOrder
{public static int MergeSort(int []arr){if (arr == null || arr.length < 2){return 0;}return MergeSort(arr, 0, arr.length - 1);}private static int MergeSort(int[] arr, int l, int r){if (l == r){return 0;}int mid = l + ((r - l) >> 1);int cnt = MergeSort(arr, l, mid)+MergeSort(arr, mid + 1, r)+Merge(arr, l, mid, r);return cnt;}private static int Merge(int[] arr, int l, int mid, int r){int []help = new int[r - l + 1];int index = 0;int p1 = l, p2 = mid + 1;int cnt = 0;while (p1 <= mid && p2 <= r){if (arr[p1] > arr[p2]){cnt += (mid - p1 + 1);for (int i = 0; i < mid - p1 + 1; i++){System.out.print(arr[p1 + i] + " " + arr[p2]);System.out.println();}}help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= mid){help[index++] = arr[p1++];}while (p2 <= r){help[index++] = arr[p2++];}for (index = 0; index < help.length; index++){arr[l + index] = help[index];}return cnt;}public static void PrintArray(int[] arr){if (arr == null){return ;}for (int i = 0; i < arr.length; i++){System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args){int []a = {1,3,4,2,5};System.out.print("a[] = ");PrintArray(a);int cnt = MergeSort(a);System.out.println("===sorting===");PrintArray(a);System.out.println("cnt = " + cnt);}}

堆的定义

堆

1，堆结构就是用数组实现的完全二叉树结构

2，完全二叉树中如果每棵子树的最大值都在顶部就是大根堆

3，完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

4，堆结构的heapInsert与heapify操作

5，堆结构的增大和减少

6，优先级队列结构，就是堆结构

堆排序

1，先让整个数组都变成大根堆结构，建立堆的过程

​ 1)从上到下的方法，时间复杂度为O(N*logN)

​ 2)从下到上的方法，时间复杂度为O(N)

2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调 整堆，一直周而复始，时间复杂度为O(N*logN)

3，堆的大小减小成0之后，排序完成

package Unit2;public class Code3_HeapSort
{public static void HeapSort(int[] a){if (a == null && a.length < 2){return ;}for (int i = 0; i < a.length; i++){HeapInsert(a, i);}// 把堆首放到最后，然后有效下边-1int size = a.length;swap(a, 0, --size);while(size > 0){Heapify(a, 0, size);swap(a, 0, --size);}PrintArray(a);}private static void Heapify(int[] a, int index, int size){// 堆的头往下放// 大根堆int left = 2 * index + 1; // 下边为0的堆左孩子的下标while (left < size){int largest = (left + 1 < size && a[left + 1] > a[left]) ? left + 1 : left;largest = (a[largest] > a[index]) ? largest : index;if (largest == index){break;}swap(a, index, largest);index = largest;left = index * 2 + 1;}}private static void swap(int[] a, int i, int j){// 利用异或把两个数交换a[i] = a[i] ^ a[j];a[j] = a[i] ^ a[j];a[i] = a[i] ^ a[j];}private static void HeapInsert(int[] a, int i){// 最后插入的节点分别和它的父节点pk，while (a[(i - 1) / 2] < a[i]){swap(a, i, (i - 1) / 2);i = (i - 1) / 2;}}public static void PrintArray(int[] a){if (a == null){return ;}for (int i = 0; i < a.length; i++){System.out.print(a[i] + " ");}System.out.println();}public static void main(String[] args){int []a = {1,3,4,2,5};PrintArray(a);System.out.println("====Heap Sorting====");HeapSort(a);PrintArray(a);}
}

堆排序的拓展问题

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元 素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的 排序算法针对这个数据进行排序。

解题思路：1.建立由k可元素的小顶堆，然后取出顶上元素

2.堆顶用没有建堆的下一元素替代，重新建堆

3.反复调用，完成排序，此算法因为每个元素移动都在k以内，所以时间复杂度为O（nlogk）

public static void sortedArrDistanceLessK(int[] arr, int k) {PriorityQueue<Integer> heap = new PriorityQueue<>();int index = 0;for (; index < Math.min(arr.length, k); 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();}}

荷兰国旗问题

问题一
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度0(1)，时间复杂度O(N)
问题二(荷兰国旗问题)
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度0(1)，时间复杂度o(N)

package Unit2;public class Code5_NetherlandsFlag
{public static int[] partition(int []arr, int l, int r, int p){int less = l - 1;int more = r;int index = l;while (index < more) {if (arr[index] < p) {swap(arr, ++less, index++);} else if (arr[index] > p) {swap(arr, --more, index);} else {index++;}}return new int[] { less + 1, more - 1 };}public static void swap(int []arr, int p, int q){arr[p] = arr[p] ^ arr[q];arr[q] = arr[p] ^ arr[q];arr[p] = arr[p] ^ arr[q];}public static int[] generateArray(){int[] arr = new int[10];for (int i = 0; i < arr.length; i++) {arr[i] = (int) (Math.random() * 3);}return arr;}public static void PrintArray(int []a){for (int i = 0; i < a.length; i++){System.out.print(a[i] + " ");}System.out.println();}public static void main(String[] args){int []test = generateArray();PrintArray(test);int []p =partition(test, 0, test.length, 1);PrintArray(test);System.out.println("p[0] = " + p[0] + " p[1] = " + p[1]);}
}

不改进的快速排序

不改进的快速排序
1）把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分:
左侧<划分值、中间==划分值、右侧>划分值

2)对左侧范围和右侧范围，递归执行
分析
1）划分值越靠近两侧，复杂度越高;划分值越靠近中间，复杂度越低
2）可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为0(N^2)

改进的快速排序

1）在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分:
左侧<划分值、中间==划分值、右侧>划分值

2）对左侧范围和右侧范围，递归执行
3）时间复杂度为O(N*logN)

package Unit2;public class Code6_QuickSort {public static void QuickSort(int []a){if (a == null && a.length < 2){return ;}QuickSort(a, 0, a.length - 1);}public static void QuickSort(int []arr, int l, int r){if (l == r){return ;}// Math.random()产生大于等于0，小于1的小数int random = l + (int)(Math.random() * (r - l + 1));swap(arr, random, r);int []p = partition(arr, 1, r);QuickSort(arr, l, p[0] - 1);QuickSort(arr, p[1] + 1, r);}public static int[] partition(int []arr, int l, int r){int less = l - 1;int more = r;int index = l;while (index < more){if (arr[index] < arr[r]){swap(arr, index++, ++less);}else if (arr[index] > arr[r]){swap(arr, index, --more);}else{index++;}}swap(arr, more, r);return new int[]{less + 1, more};}public static void swap(int []a, int i, int j){int tmp = a[i];a[i] = a[j];a[j] = tmp;}public static void PrintArray(int[] a){if (a == null){return ;}for (int i = 0; i < a.length; i++){System.out.print(a[i] + " ");}System.out.println();}public static void main(String[] args) {int []a = {1, 3, 4, 2, 5};QuickSort(a);PrintArray(a);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！