目录
目录
O(N^2)算法
选择排序：
public static void selectSort(int[] arr) {
if(arr == null || arr.length < 2) return;
for(int i = 0;i < arr.length - 1;i++) {
int minIndex = i;
for(int j = i + 1;j < arr.length;j++) {
minIndex = arr[minIndex] > arr[j] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
冒泡排序：
public static void sort(int[] arr) {
for(int i = 0;i < arr.length - 1;i++) {
for(int j = 0;j < arr.length - i - 1;j++) {
if(arr[j] > arr[j + 1]) {
swap(arr, j + 1, j);
}
}
}
}
位运算取最右边的1：eor & (~eor + 1)
插入排序:
public static void insertSort(int[] arr) {
if(arr == null || arr.length < 2) return;
for(int i = 1;i < arr.length;i++) {
for(int j = i - 1;j >= 0 && arr[j] > arr[j+1];j--) {
swap(arr,j,j+1);
}
}
}
找一个数时，条件是范围的就可以用二分分为左右两个部分
求局部最小：
一个数组中相邻的数不相等，返回一个局部最小（左右的值都大于当前值）
可以使用二分，虽是无序数组，但有升降趋势就可以划分左右部分
public static int select(int[] arr) {
if(arr[0] < arr[1]) return arr[0];
if(arr[arr.length - 1] < arr[arr.length - 2]) return arr[arr.length - 1];
int left = 0;
int right = arr.length - 1;
while(left <= right) {
int mid = left + (right - left) >> 1;
if(arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
return arr[mid];
}else if(arr[mid] < arr[mid - 1] /*&& arr[mid] > arr[mid + 1]*/) {
left = mid + 1;
}else if(arr[mid] > arr[mid - 1] /*&& arr[mid] < arr[mid + 1]*/){
right = mid;
}
}
return -1;
}
O(N*logN)算法
master公式：
T(N) = a * T(N/b) + O(N^d)
a：相同规模的子问题调用了多少次
b：什么规模的子问题
O(N^d)：其他操作的所用时间复杂度
满足master公式的递归：
归并排序：
public static void process(int[] arr,int left,int right) {
if(left == right) return;
int mid = left + ((right - left) >> 1);
//递归分到至少有两个元素的时候停止
process(arr,left,mid);
process(arr,mid + 1,right);
//将当前元素合并
merge(arr,left,mid,right);
}
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++];
}
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];
}
}
归并排序从N^2变为了N*logN是因为没有浪费比较行为，每一次比较后都会变为有序
归并排序-小和问题：
/*
* 小和问题：求一个数组中当前位置的左边有多少个数小就产生左边所有小的数的和，所有位置加起来就是小和
*
* 问题转换：求一个数组中当前位置的右边有多少个数比当前数大，就产生多少个当前数的和
*/
public static int process(int[] arr,int left,int right) {
if(left == right) return 0;
int mid = left + ((right - left) >> 1);
//将当前元素合并 并求出小和
return process(arr,left,mid)
+ process(arr,mid + 1,right)
+ merge(arr,left,mid,right);
}
public static int merge(int[] arr,int L,int M,int R) {
int sum = 0;
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = M + 1;
while(p1 <= M && p2 <= R) {
sum += arr[p1] < arr[p2] ? arr[p1] * (R - p2 + 1) : 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 sum;
}
快速排序：
快排一次为n，如果根据基准值确定的两个区间很极端最坏情况就是N^2（排一遍确定一个数排n遍），减少快排次数加快时间
public static void sort(int[] arr, int left, int right) {
if(left > right) {
return;
}
int l = left;
int r = right;
int pivot = arr[left];//基准值
while(l < r) {//右指针先移动找一个小的 这样在两指针相遇的时候交换的就是小的
while(pivot <= arr[r] && l < r) {//结束后是小于
r--;
}
while(pivot >= arr[l] && l < r) {//结束后是大于
l++;
}
swap(arr,l,r);//交换后左指针踩的位置是小的 如果左指针先移动可以找不到大于的一个数就与右指针相遇，这样与基准交换的数就是大于基准的数
}
//交换基准值
swap(arr,left,l);
sort(arr, left, l - 1);
sort(arr, l + 1, right);
}
标准值随机：
public static void sort(int[] arr,int L,int R) {
if(L >= R) return;
//取一个随机标准
int index = (int)(Math.random() * (R - L + 1)) + L;
int l = L;
int r = R;
//将这个随机标准放在最左边不加入排序中
swap(arr,index,L);
while(l < r) {
while(arr[L] <= arr[r] && l < r) {
r--;
}
while(arr[L] >= arr[l] && l < r) {
l++;
}
swap(arr,l,r);
}
//当前左右指针相遇的地方就是为标准值找到的位置，交换标准值
swap(arr,l,L);
sort(arr,L,l - 1);
sort(arr,l + 1,R);
}
一次性排一堆相同的数：
public static void quickSork(int[] arr,int L,int R) {
if(L < R) {
//将数组中随机一位数交换到最后 当作划分值
swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
int[] p = partition(arr, L, R);//划分当前区域
quickSork(arr,L,p[0] - 1);//划分等于的左边
quickSork(arr,p[1] + 1,R);//划分等于的右边
}
}
public static int[] partition(int[] arr,int L,int R) {
int less = L - 1;//小于区域右边界
int more = R;//大于区域左边界 以R所在下标为划分值
while(L < more) {//L表示当前数的下标 当前值与大于区域左边界碰撞时遍历结束
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 testQuickSort() {
int maxLength = 100;
int maxValue = 100;
int maxCount = 500000;
HashMap<String,Long> record = new HashMap<>();
record.put("1", 0L);
record.put("2", 0L);
record.put("3", 0L);
for(int i = 0;i < maxCount;i++) {
int[] arr1 = getRandomArr(maxLength, maxValue);
int[] arr2 = getCopyArr(arr1);
int[] arr3 = getCopyArr(arr1);
long start = 0L;
long end = 0L;
// Arrays.sort(arr1);
// int p1 = 0;
// int p2 = arr1.length - 1;
// while(p1 <= p2) {
// swap(arr1,p1++,p2--);
// }
//System.out.println(Arrays.toString(arr1));
start = System.currentTimeMillis();
quickSort1(arr1,0,arr1.length - 1);
end = System.currentTimeMillis();
record.put("1", record.get("1") + (end - start));
start = System.currentTimeMillis();
quickSort2(arr2,0,arr2.length - 1);
end = System.currentTimeMillis();
record.put("2", record.get("2") + (end - start));
start = System.currentTimeMillis();
quickSort3(arr3,0,arr3.length - 1);
end = System.currentTimeMillis();
record.put("3", record.get("3") + (end - start));
// if(!check(arr1,arr2)) {
// System.out.println("error!");
// }
}
for(Map.Entry<String, Long> entry : record.entrySet()) {
System.out.println(entry.getKey() + "总用时:" + entry.getValue() + "毫秒;;执行一次平均用时:" + (entry.getValue().doubleValue() / maxCount) + "毫秒");
}
System.out.println("success!");
}
public static boolean check(int[] arr1,int[] arr2) {
for(int i = 0;i < arr1.length;i++) {
if(arr1[i] != arr2[i]) {
System.out.println("arr1:" + Arrays.toString(arr1));
System.out.println("arr2:" + Arrays.toString(arr2));
return false;
}
}
return true;
}
public static int[] getCopyArr(int[] arr) {
int[] copyArr = new int[arr.length];
System.arraycopy(arr, 0, copyArr, 0, arr.length);
return copyArr;
}
public static int[] getRandomArr(int maxLength,int maxValue) {
int[] arr = new int[1 + (int)(Math.random() * maxLength)];
for(int i = 0;i < arr.length;i++) {
arr[i] = (int)(Math.random() * maxValue) - (int)(Math.random() * maxValue);
}
return arr;
}
public static void quickSort3(int[] arr,int L,int R) {
if(L >= R) {
return;
}
swap(arr,L + (int)(Math.random() * (R - L + 1)),R);
int[] p = partition(arr, L, R);
quickSort3(arr, L, p[0] - 1);
quickSort3(arr, p[1] + 1, R);
}
//以最右作为划分值
public 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};
}
//快排2
public static void quickSort2(int[] arr,int L,int R) {
if(L >= R) {
return;
}
int index = (int)(Math.random() * (R - L + 1)) + L;
int radix = arr[index];
swap(arr,index,L);
int r = R;
int l = L;
while(l < r) {
while(l < r && arr[r] >= radix) {
r--;
}
while(l < r && arr[l] <= radix) {
l++;
}
swap(arr,r,l);
}
swap(arr,L,l);
quickSort2(arr,L,l - 1);
quickSort2(arr,l + 1,R);
}
//快排1 无随机
public static void quickSort1(int[] arr,int L,int R) {
if(L >= R) {
return;
}
int radix = arr[L];
int r = R;
int l = L;
while(l < r) {
while(l < r && arr[r] >= radix) {
r--;
}
while(l < r && arr[l] <= radix) {
l++;
}
swap(arr,r,l);
}
swap(arr,L,l);
quickSort1(arr,L,l - 1);
quickSort1(arr,l + 1,R);
}堆排序
public static void heapSort(int[] arr) {
if(arr == null || arr.length < 2) return;
for(int i = 0;i < arr.length;i++) {//整体时间复杂度O(NlogN)
heapInsert(arr,i);//O(logN)
}
/*
* for(int i = (arr.length - 1) / 2;i >= 0;i--) {//整体时间复杂度O(N)
* heapify(arr,i,arr.length); }
*/
int heapSize = arr.length;
swap(arr,0,--heapSize);
while(heapSize > 0) {
heapify(arr,0,heapSize);
swap(arr,0,--heapSize);
}
}
//将整个数组都变为大根堆时，可以遍历数组从后往前遍历调用该方法 时间复杂度O(N)
//数往下窜
public static void heapify(int[] arr,int index,int heapSize) {
//左孩子下标
int left = 2 * index + 1;
while(left < heapSize) {
//在左右孩子中选一个大的
int maxIndex = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
//孩子与父pk
maxIndex = arr[maxIndex] < arr[index] ? index : maxIndex;
if(maxIndex == index) break;
swap(arr,maxIndex,index);
index = maxIndex;
left = index * 2 + 1;
}
}
//一个一个添加数时，每添加一个数调用一次该方法 使添加完数的结构重新变为大根堆 时间复杂度O(logN)
//数往上窜
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;
}
}
优先级队列（PriorityQueue）默认小根堆，相当于黑盒对于给一个数返一个数可以使用，但要改写黑盒内部的数据，黑盒自己无法让其重新有序或者所需时间代价大，这时就需要手写堆结构定制
几乎有序
一个几乎有序的数组当前位置与最终有序的位置不超过k，如何快速排好序
public static void sort(int[] arr,int k) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
int i = 0;
for(;i <= Math.min(k, arr.length - 1);i++) {
heap.add(arr[i]);
}
int index = 0;
while(!heap.isEmpty()) {
arr[index++] = heap.poll();
if(i < arr.length) {
heap.add(arr[i++]);
}
}
}
比较器
分为内部比较器Comparable和外部比较器Comparator
Arrays.sort()传入的元素为实现了内部比较器的元素类型时就会调用元素的内部比较器来比较大小
如果传入的类型没有实现Comparable接口，传入自定义的比较器Comparator的匿名内部类来比较大小
根据数据状况
基数排序
package com.wtp.排序.基数排序;
import java.util.Arrays;
public class 法1 {
public static void main(String[] args) {
int[] arr = {9,78,0,23,567,70,2,5,1,7,9,3};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
//准备十个桶 每个桶最多能装arr.length个数
int[][] bucket = new int[10][arr.length];
//统计每个桶中有多少个数 方便将桶中的元素倒回原数组
int[] bucketElementCounts = new int[10];
int max = arr[0];
for(int i = 1;i < arr.length;i++) {
max = Math.max(max, arr[i]);
}
//数组中最多为多少位 有多少位就进行多少次循环
max = (max + "").length();
for(int i = 0,n = 1;i < max;i++,n*=10) {
for(int j = 0;j < arr.length;j++) {
//取出当前的位数
int w = arr[j] / n % 10;
//将当前数放到对应的桶中
bucket[w][bucketElementCounts[w]++] = arr[j];
}
int index = 0;
//将桶中的元素都倒出来
for(int j = 0;j < 10;j++) {
//如果当前桶中有数据就倒出来
if(bucketElementCounts[j] != 0) {
for(int k = 0;k < bucketElementCounts[j];k++) {
arr[index++] = bucket[j][k];
}
//当前桶倒空了
bucketElementCounts[j] = 0;
}
}
}
}
}
package com.wtp.排序.基数排序;
import java.util.Arrays;
public class 法2 {
public static void main(String[] args) {
int[] arr = {9,78,0,23,567,70,2,5,1,7,9,3};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
if(arr == null || arr.length < 2) return;
radixSort(arr,0,arr.length - 1);
}
public static void radixSort(int[] arr,int L,int R) {
final int radix = 10;
int digit = maxbits(arr);
//排多少个数就准备多少个辅助空间
int[] bucket = new int[R - L + 1];
//有多少位就进出几次
for(int d = 1;d <= digit;d++) {
//标注当前位是下标的数有多少个
int[] count = new int[radix];
for(int i = L; i <= R;i++) {
count[getDigit(arr[i], d)]++;
}
//将count数组加工成前缀和数组 每一位意义为小于等于当前下标的有多少个数
for(int i = 1;i < radix;i++) {
count[i] += count[i - 1];
}
//倒桶
for(int i = R;i >= L;i--) {
//从右往左遍历根据后进后出当前下标的数减一就是该倒出的位置
int index = --count[getDigit(arr[i], d)];
bucket[index] = arr[i];
}
//拷贝到原数组 完成一次进桶出桶
for(int i = L,j = 0;i <= R;i++,j++) {
arr[i] = bucket[j];
}
}
}
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for(int num : arr) {
max = Math.max(max, num);
}
return (max + "").length();
}
//获取num的d位数字
public static int getDigit(int num,int d) {
return num / (int)Math.pow(10, d - 1) % 10;
}
}
排序算法总结：
时间 空间 稳定性
选择： O(N^2) O(1) 无
冒泡： O(N^2) O(1) 有
插入： O(N^2) O(1) 有
归并： O(N*logN) O(N) 有
随机快排： O(N*logN) O(logN) 无
堆： O(N*logN) O(1) 无
5、经典快排的partition做不到稳定性，经典快排的partition又是01标准和当前问题是同一调整策略，快排做不到
![[LeetBook]【<span style='color:red;'>学习</span>日记】<span style='color:red;'>排序</span><span style='color:red;'>算法</span>——归并<span style='color:red;'>排序</span>](https://img-blog.csdnimg.cn/direct/56c30fe5be394ce8a4a2c0ad3e78f83c.png)
