Summary:
- 时间复杂度基本定义
- 排序算法
2.1选择排序 selection
2.2 冒泡排序 bubble -- 补充1
2.3 插入排序 insertion
2.4 归并排序 merge --补充2，4
2.5 快速排序 quick
2.6 堆排序 heap --补充5
2.7 桶排序 bucket- 排序算法的稳定性及汇总
补充:
- 异或运算exclusive OR (xor)
- 二分查找
- 对数器
- 递归及master公式
- 堆
- java比较器 comparator
1. 时间复杂度
- 常数操作：与数据量无关，每次都是固定时间内完成的操作，e.g. +/-/*/÷, 位运算，Array[i]。但是Linkedlist.get(i) 就不是，因为要遍历，数据量不同，遍历时间不同。
- 时间复杂度：常数操作数量的指标-- Big O()
- 忽略低阶，只要最高阶项，且忽略最高阶项系数
- 评价算法好坏，先看时间复杂度指标，再分析不同数据样本下的实际运行时间(常数项时间)
- 算法流程按最差情况估计时间复杂度
2. 排序算法
2.1 选择排序 Selection sort：时间复杂度O(
), 额外空间复杂度O(1)
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
public static void selectionSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for(i = 0; i < arr.length; i++){
int minIndex = I;
for (int j = 0; j < arr.length; j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
- 时间复杂度O(N^2):
- 对每个数的for loop: N+N-1+N-2+N-3+....+1 -> O(
- 每一个数都要跟后面所有的数比: N+N-1+N-2+N-3+....+1 -> O (
- 交换: 1+1+1+1...+1 -> O(N)
- 额外空间复杂度O(1)
- 创建了新变量i，j，minIndex
2.2冒泡排序 Bubble sort：时间复杂度O(), 额外空间复杂度O(1)
比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
public static void bubbleSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for(int i=0;i<arr.length;i++){//外层循环控制排序趟数
for(int j=0;j<arr.length-i;j++){//内层循环控制每一趟排序多少次
if(arr[j]>arr[j+1]){
swap(arr, i, i+1)
}
}
}
}
public static void swap(int[] arr, int i, int j){
//不需要额外空间，交换值
// 前提，a，b在内存中不同, 内存相同会把此处的值变成0，因为N^N=0
//int a = 甲 int b = 乙
//array中使用，i和j不能是同一位置
arr[i] = arr[i] ^ arr[j];// a = a^b; a = 甲^乙， b= 乙
arr[j] = arr[i] ^ arr[j];// b = a^b; a = 甲^乙, b= 甲^乙^乙 = 甲^(乙^乙) = 甲^0 = 甲
arr[i] = arr[i] ^ arr[j];// a = a^b; a = 甲^乙^甲= 甲^甲^乙 = 0^乙= 乙， b= 甲
}
2.3插入排序 Insertion sort：时间复杂度O(), 额外空间复杂度O(1)
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）
public static void insertSort(int[] arr){
if (arr == null || arr.length < 2){
return;
}
for (int i = 1; i < arr.length; i++){// 0~i 范围有序
for (int j = i-1; j > = 0 && arr[j] > arr[j+1]; j--){//当前数往左换到不能再换为止，小的在左
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
2.4 归并排序 Merge sort : 时间复杂度O(N logN), 额外空间复杂度O(N)
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）或自下而上的迭代
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤 3 直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
public static void mergeSort(int[] arr, int L, int R){
if(L == R){
return;
}
int mid = L + ((R - L) >> 1);
mergeSort(arr, L, mid);//左边有序
mergeSory(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){//判断p1，p2是否越界
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= M){//p1没越界
help[i++] = arr[p1++];
}
while (p2 <= R){//p2没越界
help[i++] = arr[p2++];
}
//两个while只能中一个，p1和p2只能有一个没越界
for(i = 0; i < help.length; i++){//排序好拷贝回原array
arr[L + i] = help [i];
}
}
应用master公式：
T(N) = 2*T(N/2) + O (N)
注：merge时间复杂度 O(N)
a = 2, b = 2, d =1
时间复杂度O(N logN)
- 好处：没有浪费比较行为，左右两边变成了整体有序的array，之后再合成更大的array
2.4.1小和问题：
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。例如：
对于数组[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
思路：逆向思维--> 一个数右边有几个数比它大。使用归并排序
public static int smallSum(int[] arr){
if(arr == null || arr.length < 2){
return 0;
}
return process(arr, 0, arr.length - 1);
}
//arr[L...R] 既要排好序，也要求小和
public static int process(int[] arr, int L, int R){
if (L == R){
return 0;
}
int mid = L + ((R - L) >> 1);
//return左边小和+右边小和+合并时小和
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){//p1没越界
help[i++] = arr[p1++];
}
while (p2 <= R){//p2没越界
help[i++] = arr[p2++];
}
//两个while只能中一个，p1和p2只能有一个没越界
for(i = 0; i < help.length; i++){//排序好拷贝回原array
arr[L + i] = help [i];
}
return res;
}
2.4.2 逆序对：
在一个array中，左边的数如果比右边的数大，则这两个数构成一个逆序对，求逆序对数量
举个例子(前提假设升序为有序)，数组[1，2，3]，逆序对的数目为零；而数组[3，2，1]的逆序对就是3，分别为(3，2)、(3，1)和(2，1)
2.5 快速排序 Quick sort ：时间复杂度O()
- 从数列中挑出一个元素，称为 "基准"（pivot）;
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
2.5.1 快排 1.0: O()
选最末的数为pivot，分两个区域，一个是小于这个数的，一个是大于这个数的，每次完成后把最末的数和大于区域的第一个数交换位置。之后对两个区域继续相同操作
2.5.2 快排 2.0: O()
选最末的数为pivot，分三个区域，一个是小于这个数的，一个是大于这个数的，一个是等于这个数的，每次完成后把最末的数和大于区域的第一个数交换位置。之后对两个区域继续相同操作
- 时间复杂度最差O(
2.5.3 快排3.0: 时间复杂O(N log N) ，额外空间复杂O(log N)
随机选一个数为pivot，分三个区域，一个是小于这个数的，一个是大于这个数的，一个是等于这个数的，每次完成后把最末的数和大于区域的第一个数交换位置。之后对两个区域继续相同操作
时间复杂度：O(N * log N)
public static void quickSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
quickSort(arr, 0, arr.length -1);
}
public static void quickSort(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);//返回array长度一定为2，表示划分值等于此数的左边界和右边界
quickSort(arr, L, p[0] - 1);//< 区
quickSorr(arr, p[1] + 1, R);//> 区
}
}
//处理 arr[1...R]函数
//默认用arr[R] 划分，为三个区域，<arr[R] , ==arr[R], > arr[R]
//返回等于区（左边界，右边界），长度为2的数组res，res[0]等于区左边界，res[1]等于区右边界
public static int[] partition(int[] arr, int L, int R){
int less = L - 1;//<区右边界
int more = R;//>区左边界
while (L < more){//L表示当前数的位置
if(arr[L] < arr[R]){//arr[R] 是pivot
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 tmp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
2.5.4 荷兰国旗问题
2.6 堆排序 heap sort: 时间复杂度O(N log N)，额外空间复杂度O(1)
- 把所有数变成max-heap
- 把第一个数(一定是最大值)根最后一个数交换
- heapsize --，这个数与heap断链
- 重复1-3 直到排序完成
public static void heapSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for (int i = 0; i < arr.length; i ++){//O(N)
heapInsert(arr,i)//O(logN)
}//把数组排列成max-heap
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while(heapSize > 0){
heapify(arr, 0, heapSize);//O(logN)
swap(arr, 0, --heapSize);//O(1)
}
}
优化：
在数组转max-heap时，原来是自上而下，使用heap insert。优化为先把叶节点变成max-heap，然后自右向左，自下而上。时间复杂度O(N)
for (int i = arr.length -1; i >= 0; i --){//O(N)
heapify(arr, i, arr.length);
}
2.6.1 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
解题思路：选定前k个数，做小根堆排序，第一个数一定最小，pop第一个，加入K+1的数继续小根堆排序，直到最后。时间复杂度O(N log K)
priorityQueue<Integer> heap = new Priority Queue<>();// min-heap in java
注意⚠️：在java中，优先级结构就是小根堆，可以自动由小到大排序。可以将他看作黑盒，作用就是排序，并返回最小值。但不能高效地改变堆中的值(遍历)，所以有时需要手写堆(heap insert, heapify)，以便高效查询和修改
public void sortedArrDistanceLessK(int[] arr, int k){
//默认min-heap
priorityQueue<Integer> heap = new Priority Queue<>();
for(int index = 0; index <= Math.min(arr.length, k); index++){
heap.add(arr[index]);
}
for(int i = 0; index < arr,length; index++){
heap.add(arr[index]);
arr[i] = heap.poll();
}
while(!=heap.isEmpty()){
arr[i++] = heap.poll();
}
}
2.7桶排序 bucket sort
不基于比较的排序(计数排序)--需要根据数据状况定制
2.8 基数排序radix sort
3. 排序算法的稳定性及其总结
- 稳定性：值相同的元素保持排序完成后相对次序不变
- 稳定：冒泡/插入/归并/桶/基数
- 不稳定：选择/快速/堆
- 总结:
| 时间复杂 | 空间复杂 | 稳定性 | |
|---|---|---|---|
| 选择 | O( |
O(1) | No |
| 冒泡 | O( |
O(1) | Yes |
| 插入 | O( |
O(1) | Yes |
| 归并 | O(N logN) | O(N) | Yes |
| 快排 | O(N logN) | O(logN) | No |
| 堆 | O(N logN) | O(1) | No |
- 一般选快排，有空间限制选堆，有稳定性要求选归并
- 基于比较的排序，时间复杂度无法低于O(N logN)
- 时间复杂度O(N logN)，空间复杂度不能小于O(N)且稳定
坑⚠️：
1. 归并可以把空间复杂度降为O(1)-->"归并排序 内部缓存法"，但是很难且不稳定。不如堆
2. "原地归并排序"，时间复杂升为O()
3. “01 stable sort”，稳定快排但很难，无意义
4. 所有的改进都不重要
5. 题目：奇数放数组左边，偶数放数组右边，还要原始的相对次序不变，时间复杂O()，空间复杂(1)--> 跟快排评判标准一样(0,1标准)，但做不到稳定
- 工程上对排序改进：
- 综合排序：充分利用O(N logN)排得快 和O(
2.稳定性
- 综合排序：充分利用O(N logN)排得快 和O(
补充1：异或运算exclusive OR (xor)
- basic: 1^1 = 0, 1^0 =1, 0^0=0
- 可以看作不进位相加
- 0^N = N, N^N = 0
- 满足交换结合率：a^b = b^a, (ab)c = a(bc)
- abcd....z 顺序不影响结果
- 例题1：int数组中，只有一个数出现奇数次，其他所有数都出现偶数次，怎么找到一个出现奇数次的数？要求时间O(N)，额外空间O(1)
public static void findOddnumber(int[] arr){
int eor = 0;
for(int cur : arr){//遍历array
eor = eor ^ cur;//偶数会自己消除，奇数剩下
}
//for (int i =0; i< arr.length-1; i++){
// eor = eor ^ arr[i];}
Ststem.out.println(eor);
}
- 例题2: int数组中，有两个数出现奇数次，其他所有数都出现偶数次，怎么找到两个出现奇数次的数？
public static void findOddnumber2(int[] arr){
int eor = 0;
for(int cur : arr){
eor = eor ^ cur;//偶数会自己消除，奇数剩下
}
//eor = a^b
// eor != 0, 因为a！=b
//eor 必有一个位置是1
int rightOne = eor & (~eor+1)// 提取一个非零数最右边的1
int onlyone = 0;
//用这一位的1跟所有元素异或，偶数全都消除，只剩下a 或b。因为a，b这一位一定是不同的
for (int cur:arr){
if((cur & rightOne) == 0){
onlyOne = onlyOne ^cur; // a or b
}
}
Ststem.out.println(onlyOne + " "+ (eor ^ onlyOne));
}
补充2：二分查找：
1.有序数组中，查找某个数是否存在：时间复杂度O(logN)
2.在有序数组中，找>= 某个数最左侧的位置：时间复杂度O(logN)
3.局部最小值：无序array，相邻数一定不想等，求局部最小值
补充3：对数器：
1.通过用大量测试数据来验证算法是否正确的一种方式
- java中：
Math.random()[0,1)所有小数，等概率返回一个
Math.random()*N[0,N)所有小数，等概率返回一个
(int)(Math.random()*N)[0,N-1]所有整数，等概率返回一个 - 生成随机array，可以控制长度和最大值
public static int[] generateRandomArray(int maxSize, int maxValue){
int[] arr = new int[(int)((maxSize + 1) * Math.random())];
for (int i = 0; i< arr.length; i++){
arr[i] = (int)((maxValue + 1) * Math.random())-(int)(maxValue * Math.random());
}
return arr;
}
- for testing
public static void main (String[] args){
int testTime = ;
int maxSize = ;
int maxValue = ;
boolean succeed = true;
for (int i = 0; i < testTime; i++){
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
//method1
//method2
if(!isEqual(arr1,arr2)){
//System.out.println(arr1);
//System.out.println(arr2);
succeed = false;
break;
}
}
System.out.println(succeed? "succeed": "failed")
}
补充4: 递归及master公式：
1.求arr[L...R]范围中求最大值
public static int getMax(int[] arr){
return recursion(arr, 0, arr.length -1);
}
//arr[L...R]范围中求最大值
public static int recursion(int[] arr, int L, int R){
if(L == R){
return arr[L];
}
int mid = L + ((R - L) >> 1); //求中点: `mid = (L + R) / 2` 内存有可能溢出，改为 `mid = L + (R - L)/2` 优化为 `mid = L +((R - L) >> 1)` 右移一位，相当于除2
int leftMax = recursion(arr, L, mid);
int rightMax = recursion (arr, mid + 1, R);
return Math.max (leftMax, rightMax);
}
recursion 示意图
- 递归行为时间复杂度的估算：
master公式: 子问题规模相等
T(N) = a*T(N/b) + O (N^d)
- a = 子问题调用次数
- N/b = 子问题数据规模占总规模的多少(每次递归要相等)
- O (N^d) = 分解合并的时间复杂度
解：
- logb a < d, 时间复杂度为O(N^d)
- logb a > d, 时间复杂度为O(N^(logb a))
- logb a = d, 时间复杂度为O((N^d)*log N)
补充5 ：堆 heap
- 完全二叉树结构：满的二叉树，或从左到右正在变满的二叉树(符合BFS遍历顺序)
- array转完全二叉树：
- arr[i] 左孩子：
2 * i + 1 - arr[i] 右孩子：
2 * i + 2 - arr[i] 父：
int((i-1)/2)
array转完全二叉树
- arr[i] 左孩子：
- 大根堆和小根堆
- 大根堆max-heap：父节点的值大于或等于子节点的值
- 小根堆min-heap： 父节点的值小于或等于子节点的值
- heap insert for max-heap
时间复杂: O(log N)
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;
}
}
- heapify:
Pop the root of a max-heap, then move the last node to the top and rearrange the tree from top-to-bottom to be max-heap again. -- 时间复杂O(log N)
public static void heapify(int[] arr, int index, int heapsize){
int left = index * 2 + 1;//左孩子下标
while(left < heapsize){//下方还有孩子
//左右两个孩子，把值大的下表给largest
int largest = left + 1 < heapsize && arr[left + 1] > arr[left] ?
left + 1 : left;
//较大的孩子和父亲比，把值大的下表给largest
int largest = arr[largest] > arr[index] ? largest : index;
if (largest == index){
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
补充6：java比较器 comparator
- 实质是重载比较运算符（自己定义比较方法）
- 应用在特殊标准的排序上
- 应用在根据特殊标准排序的结构上
- 使用方法：
Array.sort(arr, comparator)- 返回负数时，第一参数排前面
- 返回正数时，第二参数排前面
- 返回0 时，谁在前面无所谓
- 大根堆比较器：
public static class Acomp implements Comparator<Integer>{
public int compare(Integer arg0, Integer arg1){
return arg1 - arg0;
}
}
