1.冒泡排序记录左神算法学习笔记之排序算法
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) return;
//0 ~ N-1 -> 0 ~ N - 2
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
//左边元素大于右边，将大的交换到右边去
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
2.选择排序
public static void selectSort(int[] arr) {
if (arr == null || arr.length < 2) return;
//每次选择最小的元素放在对应的位置上
for (int i = 0; i < arr.length - 1; i++) {
//在 i ~ n - 1位置查找最小值
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
//找到一个更小的元素，更新 minIndex
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
if (minIndex != i) swap(arr, minIndex, i);
}
}
3.插入排序
public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) return;
//0~0 是有序的，想要 0~i是有序的
for (int i = 1; i < arr.length; i++) {
// j 是从 i - 1 开始的，就是已经排好序的最后一个位置开始的，然后和即将插入的元素相比，如果最后一个元素比
//待插入的元素 arr[j + 1] 大,那需要将该元素往数组前移动
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
4.归并排序
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) return;
process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int l, int r) {
if (l == r) return;
int mid = l + ((r - l) >> 1);
//让左边有序
process(arr, l, mid);
//让右边有序
process(arr, mid + 1, r);
//合并两个有序的数组
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int m, int r) {
int[] temp = new int[r - l + 1];
//定义左边数组指针 p1，右边数组指针p2，temp 数组指针p
int p = 0, p1 = l, p2 = m + 1;
while (p1 <= m && p2 <= r) {
temp[p++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
temp[p++] = arr[p1++];
}
while (p2 <= r) {
temp[p++] = arr[p2++];
}
//将temp数组赋值到arr数组中
if (temp.length >= 0) System.arraycopy(temp, 0, arr, l, temp.length);
}
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
归并排序解决小和问题 （图解详细流程）
了解归并流程后，在merge过程中，产生小和。规则是左组比右组小，则产生小和。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-21VmNo2m-1641298390748)(../pic/image-20211210105631775.png)]" />
注意：
当左组和右组数相等的时候，拷贝右组的数，不产生小和(区别于归并排序，我们是拷贝的左数组)；
当左组的数大于右组的时候，拷贝右组的数，不产生小和(因为此时如果拷贝左数组，就导致左组当前元素没有和右组的后面元素进行比较，会丢失情况，请特别注意)。
实质是把找左边比本身小的数的问题，转化为找这个数右侧有多少个数比自己大，在每次merge的过程中，一个数如果处在左组中，那么只会去找右组中有多少个数比自己大。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cmvX5YZh-1641298390749)(../pic/image-20211210112144435.png)]" />
public static int smallSum(int[] arr) {
if(arr == null || arr.length < 2) return 0;
return process1(arr,0,arr.length - 1);
}
public static int process1(int[] arr, int l, int r) {
//只有一个数，不存在右组，小和为0
if(l == r) return 0;
int mid = l + ((r - l) >> 1);
// 左侧merge的小和+右侧merge的小和+整体左右两侧的小和
return process1(arr,l,mid) + process1(arr,mid + 1,r) + merge1(arr,l,mid,r);
}
public static int merge1(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int p = 0, p1 = l, p2 = m + 1;
int ans = 0;
while (p1 <= m && p2 <= r){
//当前的数是比右组小的，产生右组当前位置到右组右边界数量个小和，累加到 ans。否则 ans 加 0
ans += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
//归并数组,注意这里的区别，左边小拷贝左边，大于等于的选择拷贝右边
help[p++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m){
help[p++] = arr[p1++];
}
while (p2 <= r){
help[p++] = arr[p2++];
}
//将temp数组赋值到arr数组中
if (help.length >= 0) System.arraycopy(help, 0, arr, l, help.length);
return ans;
}
2.求逆序对?
5.快排 1.荷兰国旗问题
荷兰国旗1.0版本：
Partion过程：
- 给定一个数组arr，和一个整数 num。请把小于等于num的数放在数组的左边，大于num的数放在数组的右边(不要求有序)。要求额外空间复杂度为O(1)，时间复杂度为O(N)。例如[5,3,7,2,3,4,1]，num=3,把小于等于3的放在左边，大于3的放在右边
- 设计一个小于等于区域，下标为 -1。
- 开始遍历该数组，如果arr[i]<=num,当前数和区域下一个数交换，区域向右扩1，i++
- arr[i] > num, 不做 *** 作，i++
荷兰国旗问题：
给定一个数组，和一个整数num。请把小于num的数放在数组的左边，等于num的放中间，大于num的放右边。要求额外空间复杂度为O(1)，时间复杂度为O(N)。[3,5,4,0,4,6,7,2]，num=4。实质是经典荷兰国旗问题。
1.需要维护三个区域，左边的小于区域，中间的等于区域，右边的大于区域。用图中的0,1,2来表示。
2.初始化的时候红-白-蓝 三色是乱序的，所以此时的两条线我们是不是可以看成在最两侧
3.我们发现此时 C 等于0。是不是意味着，我们应把这个元素放到 A 的左侧，所以我们移动 A线。当然，我们也需要移动一下 C 的位置
新的 C 位置处等于2，那是不是说明这个元素应该位于 B 的右侧。所以我们要把该位置的元素 和 B位置处的元素进行交换，同时移动B。
C 交换完毕后，C 不能向前移。因为C指向的元素可能是属于前部的，若此时 C 前进则会导致该位置不能被交换到前部。继续向下遍历。
1）若遍历到的位置为0，则说明它一定位于A的左侧。于是就和A处的元素交换，同时向右移动A和C。
2）若遍历到的位置为1，则说明它一定位于AB之间，满足规则，不需要动d。只需向右移动C。
3）若遍历到的位置为2，则说明它一定位于B的右侧。于是就和B处的元素交换，交换后只把B向左移动，C仍然指向原位置。（因为交换后的C可能是属于A之前的，所以C仍然指向原位置）
75. 颜色分类
public static void sortArray(int[] arr, int target) {
if (arr == null || arr.length < 2) return;
int left = 0, right = arr.length - 1, cur = 0;
while (cur <= right){
if (arr[cur] < target){
//交换到左区域，并且cur指针和left指针都移动
swap2(arr,left,cur);
cur++;
left++;
}else if (arr[cur] > target){
//此时应该将元素移到右边界。右边界指针移动，cur指针也不动，因为我不知道当前移过来的元素是否满足条件，需要继续判断
swap2(arr,cur,right);
right--;
}else {
//当前元素与目标元素相等，只用移动cur指针
cur++;
}
}
}
2.快排
思想：借助荷兰问题，我们从数组中选择一个元素，然后让数组以该元素分为左右两部分。分完之后，该元素在排序数组中的位置一定是确定下来的。
继续计算左边数组和右边数组相同的过程，然后就能将找到所有元素的位置。注意：因为Partion过程会存在元素的交换(将相同的7交换到数组的最后方，所以快排是不稳定的。)
在最差情况下，如果我们每次找的元素都是位于位于排序后数组的末尾，则此时快排的时间复杂度会递增到 O ( N 2 ) O(N^2) O(N2) ，最好情况，其他各种情况的出现概率为 1 / N 1/N 1/N。对于这 N 种情况，数学上算出的时间复杂度最终期望是 O ( N l o g N ) O(NlogN) O(NlogN)
public static void quickSort(int[] arr) {
quickSortHelper(arr, 0, arr.length - 1);
}
public static void quickSortHelper(int[] arr, int l, int r) {
if (l < r) {
//为了避免最坏的情况，我们随机算选择一个数作为划分值，将其放到数组的尾部,可以随机算去
// swap2(arr,l + (int)(Math.random() * (r - l + 1)),r);
//通常我们选中间元素就行
int mid = l + (r - l) / 2;
swap2(arr, mid, r);
int[] p = partition(arr, l, r);
quickSortHelper(arr, l, p[0] - 1);//小于区域
quickSortHelper(arr, p[1] + 1, r);//大于区域
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1; // 小于 p 区域的边界
int more = r; // 大于 p 区域的边界
while (l < more) { // l表示当前操作的元素，而 arr[r] 为划分值
if (arr[l] < arr[r]) {
//当前元素小于划分值，应该放在左测区域,并且移动指针，因为less是前一个区域的边界
swap2(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
//当前元素大于划分值，要分到右边界，此时交换元素，并且l指针不能动，因为我不确定当前交换的值是否满足条件
swap2(arr, --more, l);
} else {
//当前元素为划分值，则只用移动l指针
l++;
}
}
//将划分值放回右边区域的边界位置
swap2(arr, more, r);
//返回中间等于区域的左右边界
return new int[]{less + 1, more};
}
6.堆排序
1.大根堆和小根堆
基础性质：
其中 i i i 表示数组中的索引，将它对应成堆后的性子。
父节点索引： ( i − 1 ) / 2 (i -1)/2 (i−1)/2
左孩子索引：$ 2*i + 1$
右孩子索引： 2 ∗ i + 2 2*i + 2 2∗i+2
大根堆： a r r [ i ] > a r r [ 2 ∗ i + 1 ] & & a r r [ i ] > a r r [ 2 ∗ i + 2 ] arr[i] > arr[2*i + 1] && arr[i] > arr[2*i+2] arr[i]>arr[2∗i+1]&&arr[i]>arr[2∗i+2]
小根堆： a r r [ i ] < a r r [ 2 ∗ i + 1 ] & & a r r [ i ] < a r r [ 2 ∗ i + 2 ] arr[i] < arr[2*i + 1] && arr[i] < arr[2*i+2] arr[i]
完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
完全二叉树中如果每颗子树的最小值都在顶部就是小根堆
两个重要堆结构 *** 作：
- heapInsert
要构建一个大根堆，把所有的数依次添加到一个数组（下标从0开始）中去，每次添加一个数的时候，要去用找父亲节点的公式 p a r e n t = ( i − 1 ) / 2 parent = (i-1) / 2 parent=(i−1)/2找到父节点去比较，如果比父节点大就和父节点交换向上移动，移动后再用自己当前位置和父亲节点比较…，小于等于父节点不做处理。这样用户每加一个数，我们都能保证该结构是大根堆。
我们的调整代价实际上就是这颗树的高度层数， l o g N logN logN
- heapify
删除了最大值，也就是 a r r [ 0 ] arr[0] arr[0]位置，之后我们把堆最末尾的位置调整到 a r r [ 0 ] arr[0] arr[0]位置，堆大小减一。让现在 a r r [ 0 ] arr[0] arr[0]位置的数找左右孩子比较…，进行hearify *** 作，让其沉下去。沉到合适的位置之后，仍然是大根堆。
heapify的下沉 *** 作，仍然是树的高度，logN
整个过程如下：
2.手写大堆：
public class MaxHeap {
private int[] heap;
private final int capacity;
private int heapSize;
public MaxHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
heapSize = 0;
}
public boolean isEmpty() {
return heapSize == 0;
}
public boolean isFull() {
return heapSize == capacity;
}
public void push(int value){
if (heapSize == capacity){
throw new RuntimeException("heap is full");
}
heap[heapSize] = value;
//调整堆结构,heapSize作为 *** 作数组的指针
heapInsert(heap,heapSize++);
}
public int pop(){
if (heapSize == 0) {
throw new RuntimeException("heap is empty");
}
int ans = heap[0];
//这里的移除只是改变 heapSize 指针。至于数组的元素还存在对我们堆结构没有任何影响。因为我们在push *** 作中会覆盖当前值
//我们将堆中最后一个元素移动到堆顶执行heapify *** 作，下沉堆顶元素
swap(heap,0,--heapSize);
//执行下沉 *** 作
heapify(heap,0,heapSize);
return ans;
}
public int peek(){
if (heapSize == 0) {
throw new RuntimeException("heap is empty");
}
return heap[0];
}
private void heapInsert(int[] arr,int index){
//arr[index] 不比 arr[index父]大了，停止heapInsert过程
//注意当比较到 0 位置即堆顶时候，此时循环也不会进入了
while (arr[index] > arr[(index - 1) / 2]){
swap(arr,index,(index - 1) / 2);
//将指针移动到父节点，继续上升的过程
index = (index - 1) / 2;
}
}
private void heapify(int[] arr,int index,int heapSize){
//找到左孩子索引
int leftIndex = index * 2 + 1;
//这里如果左孩子越界，那右孩子更越界，右孩子等于左孩子+1
while (leftIndex < heapSize){
//下沉操作，父节点与左右孩子相比, 左右两个孩子中，谁大，谁把自己的下标给largest,因为大的节点得上升
// 选择右 -> (1) 有右孩子 && (2)右孩子的值比左孩子大才行
int largest = leftIndex + 1 < heapSize && arr[leftIndex + 1] > arr[leftIndex] ? leftIndex + 1 : leftIndex;
//左右孩子中最大值，和当前值父节点比较，谁大谁把下标给largest(当前，左，右的最大值下标)
largest = arr[largest] > arr[index] ? largest : index;
//index 位置上的数比左右孩子的数都大，已经无需下沉
if(index == largest) break;
//交换父节点和子节点中的较大孩子。周而复始进行
swap(arr,index,largest);
//更新父节点的index，即父节点往下沉
index = largest;
//继续看它的左右孩子是否需要调整
leftIndex = index * 2 + 1;
}
}
private void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
3.堆排序
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) return;
//1.将元素数组构建成堆事件复杂度为 0(NlogN)
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
//1.1拓展，如果直接给定一个数组，我们直接执行heapify操作构建大堆,从末尾开始看是否需要heapify
// for (int i = arr.length - 1; i >= 0;i--){
// heapify(arr,i,arr.length);
// }
//2.将堆顶元素移到末尾，堆的heapSize--；
int heapSize = arr.length;
swap2(arr, 0, --heapSize);
//开始下沉 *** 作
while (heapSize > 0) {
heapify(arr, 0, heapSize);
swap2(arr, 0, --heapSize);
}
}
public static void heapInsert(int[] arr, int index) {
//与父节点相比，大于就上身，否则停止
while (arr[index] > arr[(index - 1) / 2]) {
swap2(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) {
//1.找左右孩子中较大的一个
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
//2.将孩子与父节点进行比较，父节点比孩子小，则需要下沉
largest = arr[index] < arr[largest] ? largest : index;
//3.如果父节点的索引没变，则说明下层已经满足大堆结构了，直接break
if (largest == index) break;
//4.否则父节点与子节点交换
swap2(arr, index, largest);
//5.父节点指针移动，移动到孩子节点，接续判断孩子节点的树是否满足大堆结构，周而复始
index = largest;
left = index * 2 + 1;
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）