只讲解真实场景中常用的, 简单的就不分析了大家稍微看一下就行
快排的思想主要就是每次把一个位置放好后, 可以把数组分成两半, 递归处理子问题即可
空间复杂度OlogN 分析： 每次都分成两半处理子问题, 可以把数组看成树的节点, 则变成整个递归相当于一棵二叉树树高, 即OlogN
时间复杂度优化后基本稳定在ONlogN了, 这个分析过程不要求掌握比较复杂, 不优化的最差ON2
//调用 QuickSort(nums, 0, nums.length - 1)
void QuickSort(int[] nums, int l, int r){
if(l >= r) return ;
//idx即放好了这个位置, 下面递归
int idx = partition(nums, l, r);
QuickSort(nums, l, idx - 1);
QuickSort(nums, idx + 1, r);
}
//每次把一个数放到他正确的位置
int partition(int[] nums, int l, int r){
int midIdx = (l + r) >> 1; //这边主要就是优化一下, 否则每次选左边的话在有序数组中会On2复杂度
swap(nums, l, midIdx); //然后把他放到左边
int pivot = nums[l];
int i = l + 1, j = r;
while(true){
//小于主元的放在左边
while(i <= j && nums[i] < pivot) i ++;
//大于主元的放在右边
while(i <= j && nums[j] > pivot) j --;
if(i >= j) break;
swap(nums, i, j);
i ++; j --;
}
//这边是j的原因是因为在上面的过程中, i最后一定停在>=pivot位置, 我们是不能换>pivot的否则错误
swap(nums, l, j);
return j;
}
void swap(int[] nums, int a, int b){
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
对于本题可以利用partition来达到ON的一个复杂度, 常规做法为堆排序ONlogK这边就不给出堆排序的代码了
复杂度分析:partition函数是一个N的复杂度, 我们这边是优化过的所以是每次partition后把数组拆成两半,后面就是N/2的复杂度, 加起来就是N+N/2+N/4+N/8+...+1这个公式计算完是ON的复杂度
public int findKthLargest(int[] nums, int k) {
//我们可以基于partition每次都可以让一个数字去到排序后的位置, 利用这种思想来
//进行快速选择, 也就是用快速选择找到第k大的数, 他partition后的位置应该在len - k
int len = nums.length;
int target = len - k;
int l = 0, r = len - 1;
while(true){
//把一个位置的元素归位
int partition = partition(nums, l, r);
//正好是归到了target位置则他就是第k大
if(partition == target) return nums[partition];
//大于这个位置代表我们要找的数字在左边
else if(partition > target) r = partition - 1;
//反之右边
else l = partition + 1;
}
}
public int partition(int[] nums, int l, int r){
int midIdx = (l + r) >> 1;
swap(nums, midIdx, l);
int pivot = nums[l];
int i = l + 1, j = r;
while(true){
while(i <= j && nums[i] < pivot) i ++;
while(i <= j && nums[j] > pivot) j --;
if(i >= j) break;
swap(nums, i, j);
i ++; j --;
}
swap(nums, l, j);
return j;
}
public void swap(int[] nums, int a, int b){
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}堆排序则基于树的思想, 建堆的时间复杂度为ON这个必须注意, 大家很多人都会以为跟log有关系其实是无关的, 想象成一颗巨大的树就可以分析出来了
空间复杂度O1, 因为这个是原地操作的算法
时间复杂度ONlogN, 堆排序的自调节复杂度为OlogN
void HeapSort(int[] nums){
int size = nums.length;
//从最后一个非叶子节点调节
for(int i = size / 2 - 1; i >= 0; i --){
adjust(nums, i, size);
}
for(int i = size - 1; i >= 1; i --){
//每次把一个最大的放在最后面, 调节根节点调节完就排序完了
swap(nums, i, 0);
//这边可以发现我们每次size都是比前面一次小了1哦
adjust(nums, 0, i);
}
}
void adjust(int[] nums, int root, int size){
int child = 2 * root + 1;
while(true){
//越界跳出
if(child >= size) break;
//选大儿子
if(child + 1 < size && nums[child + 1] > nums[child]) child ++;
//儿子大就交换
if(nums[root] <= nums[child]){
swap(nums, root, child);
root = child;
child = 2 * root + 1;
}
else break;
}
}
void swap(int[] nums, int a, int b){
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}归并排序的思想则为处理递归到最小的粒度数组处理子问题, 子问题合并后想上归合起来继续处理即可
空间复杂度ON, 这边递归栈的高度同快速排序是OlogN, 但是考虑到归并过程的额外数组, 故为On
时间复杂度为ONlogN
//调用MergeSort(nums, 0, nums.length - 1)
void MergeSort(int[] nums, int l, int r){
if(l >= r) return ;
//对半拆分
int mid = l + r >> 1;
MergeSort(nums, l, mid); //注意这里一定必须右边是mid 否则会出错
MergeSort(nums, mid + 1, r);
Merge(nums, l, mid, r);
}
void Merge(int[] nums, int l, int mid, int r){
int i = l, j = mid + 1;
int[] temp = new int[r - l + 1];
int cnt = 0;
//这里是归并的过程, 就是对比左右两个子数组排序一下
while(i <= mid && j <= r){
if(nums[i] < nums[j]) temp[cnt ++] = nums[i ++];
else temp[cnt ++] = nums[j ++];
}
while(i <= mid) temp[cnt ++] = nums[i ++];
while(j <= r) temp[cnt ++] = nums[j ++];
for(i = 0; i < temp.length; i ++) nums[l ++] = temp[i];
}
void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}public void bubbleSort(int[] nums){
int n = nums.length;
for(int i = 0; i < n; i++){
boolean flag = false;
for(int j = n - 1; j > i;j--){
if(nums[j - 1] > nums[j]){
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
flag = true;
}
}
if(flag == false) return ;
}
} public void insertSort(int[] nums){
int n = nums.length;
for(int i = 0; i < n; i++){
int temp = nums[i];
int j = i - 1;
while(j >= 0 && nums[j] > temp){
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = temp;
}
} public void selectSort(int[] arr){
int min;
for(int i = 0;i<arr.length;i++){
min = i;
for(int j = i;j<arr.length;j++){
if(arr[j] < arr[min]){
min = j;
}
}
if(min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}思想:nums[i] 放到桶里面,对于范围小的好用, 即创建一个int[范围], 然后根据范围取一下就排序完了
主要掌握快速排序, 归并排序, 堆排序就可以, 复杂度必须要会分析！