Article Outline
TOC
Collection Outline
1荷兰国旗类问题（数组划分）
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
x 坐标为 L - 1，y 坐标为 R + 1，两边分别表示小于 num 和大于 num 的值，当前位置坐标为 cur，然后依次向右遍历，如果该数小于 num，则该数和小于区域最右边下标（x）的下一个坐标元素交换，小于区域向右扩充（即 x + 1），如果该数等于 num ,则 cur 指向下一个元素，如果大于 num，则该数和大于区域最左边区域的前一个坐标元素交换，大于区域向左扩充一个（即 y - 1），然后这里交换回来的数还需要按照上面的标准进行判断，直到 cur 和 又边界相遇停止；
public class Test{
public static int[] partition(int[] arr,int L,int R,int num){
int less = L - 1;
int more = R + 1;
int cur = L;
while(cur < more){
if(arr[cur] < num){
swap(arr,++less,cur++);
}else if(arr[cur] > num){
swap(arr,--more,cur);
}
}
return new int[]{less +1,more -1};
}
public static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// for test
public static int[] generateArray() {
int[] arr = new int[20];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 10);
}
return arr;
}
// for test
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[] test = generateArray();
System.out.println("测试数据为：");
printArray(test);
int[] res = partition(test, 0, test.length - 1, 5);
System.out.println("划分之后数据为：值为原地修改");
printArray(test);
System.out.println("等于区域的开始下标为：");
System.out.println(res[0]);
System.out.println("等于区域的结束下标为：");
System.out.println(res[1]);
}
}2.快速排序
2.1经典快排
首先以数组最后一个数值为基准，将小于等于该数值的全部放在数组前半部分，大于该数值的全部放在数组的后半部分，然后前半部分和后半部分分别以该部分最后一个元素为基准重复以上步骤；
特点：
- 经典快排和数据的状态有关：
- 当小于最后一个数值的元素远大于大于最后一个数组的元素个数时候，或者反之情况，时间复杂度都是：$O({N}^{2})$
- 如果数据状态较好，即大于和小于差不多的情况下，时间复杂度为：$T(N) = 2T(\frac{N}{2}) + O(N) = O(N * log_{2}^{N})$
经典快排的空间复杂度为：$O(N)$
2.2随机快速排序
通过随机选一个数和最后一个数进行互换，使得每次划分标准都在改变； 根据随机性，随机快速排序的时间复杂度是：$O(N * \log_{2}^{N})$，同时需要空间复杂度为：$O(\log_{2}^{N})$，这里的额外空间主要用于记录每次划分区域的断点；
package cn.test;
import java.util.Arrays;
/**
* @Author smallmartial
* @Date 2020/2/28
* @Email [email protected]
*/
public class QuickSort {
public static void quickSort(int[] sourceArray) {
if (sourceArray == null || sourceArray.length < 2) {
return;
}
quickSort(sourceArray, 0, sourceArray.length - 1);
}
/**
* @param sourceArray：需要排序的数组
* @param left：排序数组左边界，一般为：0
* @param right：排序数组右边界，一般为：length - 1;
* less：小于参照元素区域的最右边边界：less = p[0] - 1;
* more：大于参照元素区域的最左边边界：more = p[1] + 1;
* p[0]：等于参照元素区域的最左边边界；
* p[1]：等于参数元素区域的最右边边界；
* 小于参照元素区域：[Left ~ less];
* 等于参照元素区域：[p[0] ~ p[1]]；
* 大于参照元素区域：[more ~ right]；
*/
public static void quickSort(int[] arr, int L, int R) {
if (L < R) {
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
// p 数组中： p[0] 表示等于区域的左边界，p[1] 表示等于区域的右边界， // 左边区域：L ~ p[0] - 1;右边区域： p[1] + 1 ~ R;
int[] p = partition(arr, L, R);
quickSort(arr, L, p[0] - 1);
quickSort(arr, p[1] + 1, R);
}
}
private static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
// 以数组最后一个元素为标准，将整个数组划分为 小于、等于、大于 三个部分
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[]{less + 1, more};
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {1, 5, 3, 2};
quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}
3.堆排序
3.1堆
堆是一个完全二叉树，可以采用数组进行实现；
对于完全二叉树，
- 结点 i 的左孩子序号为：2i + 1；
- 右孩子序号为：2i + 2；
- 父结点的序号为：$\frac{i - 1}{2}$。
分类：
- 大根堆：每棵树（包括任意一棵子树）的最大值都是其头部（父结点）；
- 小根堆：每棵树（包括任意一棵子树）的最小值都是其头部（父结点）；
完全二叉树：对一棵具有 n 个节点的二叉树按照层序进行编号，如果编号 i （1<=i<=n）的结点与同样深度的满二叉树中编号为 i 的结点位置完全相同；
满二叉树：所有的分支结点都存在左子树和右子树，且所有的叶子都在同一层；
3.2数组转换为大根堆
以数组 [2,1,3,6,0,4]为例： 首先取出第一元素 2 作为头结点，然后取出第二个元素 1，该元素比 2 小，放在左孩子位置，数组元素为：[2,1]；然后取出第三个元素 3，计算该元素的父结点：$\frac{2 - 1}{2} = 0$，则与 0 位置元素 2 进行比较，发现 3 比较大，则在数组中将 3 和 2 两个元素互换，则数组变为：[3,1,2]；然后取出第四个元素 6，计算父结点下标为：$\frac{3 - 1}{2} = 1$，则与 1 位置的元素 1 进行比较，发现 6 比较大，则将元素 1 和元素 6 互换，得到[3,6,2,1]，然后再比较元素 6 和其父结点：$\frac{1 - 1}{2} = 0$，比较得出 6 比 3 大，然后再换，最后得到数组为：[6,3,2,1]，剩下元素依次类推......
每加入一个节点其最多比较的次数和已经形成的二叉树高度有关（因为每次只和其父结点比较），因此最多时间复杂度为：$O(log_{2}^{N})$，所有整个转换过程时间复杂度为：$log_{2}^{1} + log_{2}^{2} + ..... + log_{2}^{N} = O(N)$
3.3堆排序
package cn.test;
import java.util.Arrays;
/**
* @Author smallmartial
* @Date 2020/2/28
* @Email [email protected]
*/
public class HeapSort {
public static void heapSort(int[] arr) {
if (arr == null && arr.length < 2) {
return;
}
//首先将数组转化为大根堆
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
//不断将堆顶的元素和最后一个元素交换然后进行 heapify
// int size = arr.length;
// swap(arr, 0, --size);
// while (size > 0) {
// heapify(arr, 0, size);
// swap(arr, 0, --size);
// }
}
/**
* size - 1 到 length - 1 位置上已经拍好
*
* @param arr 要排序的数组
* @param i 哪个节点位置上元素发生了变化，传入的初始值一直为0
* @param size 还没有排好序的数组长度
*/
private static void heapify(int[] arr, int i, int size) {
int left = i * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[i] ? largest : i;
if (largest == i) {
break;
}
swap(arr, largest, i);
i = largest;
left = i * 2 + 1;
}
}
private static void heapInsert(int[] arr, int index) {
//判断插入新节点与父节点的大小 父节点位置 （i-1）/2
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
//int[] arr = {2,1,3,6,0,4};
int[] arr = {2,8,5,3,4};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}