网站建设技术团队有多重要,网站界面结构,软件商店最新版本,wordpress feed 地址文章目录 比较排序冒泡排序选择排序插入排序归并排序快速排序堆排序希尔排序 非比较排序#xff08;桶排序#xff09;计数排序基数排序 比较排序
冒泡排序
嵌套循环#xff0c;每次内层循环执行时#xff0c;数组的每两个元素交换#xff0c;将一个最大/小的数排到数组… 文章目录 比较排序冒泡排序选择排序插入排序归并排序快速排序堆排序希尔排序 非比较排序桶排序计数排序基数排序 比较排序
冒泡排序
嵌套循环每次内层循环执行时数组的每两个元素交换将一个最大/小的数排到数组末尾 public void bubbleSort(int[] arr){for (int i 0; i arr.length; i) {// 内层循环中每轮都是让最后一个位置排好序然后外层循环向前递进for (int j 0; j arr.length - i - 1; j) {if (arr[j] arr[j1]){ // 把大的数挪到后面int tmp arr[j];arr[j] arr[j1];arr[j1] tmp;}}}
}选择排序
嵌套循环每次内层循环执行时子数组的后m-1个元素寻找最小值再与子数组的首元素比较如果更大/小就交换 public void selectSort(int[] arr){for (int i 0; i arr.length - 1; i){ // len个元素只需比较n-1次int min_idx i;for (int j i 1; j arr.length; j){if (arr[j] arr[min_idx]) // 在i1后面的数两两比较找到最小下标min_idx j;}// 内层遍历完之后我们拿到后面的元素的最小值下标min_id要和前面的下标i元素进行值的对比if (arr[min_idx] arr[i]){ // 能篡位就篡位arr[min_idx] arr[min_idx] ^ arr[i];arr[i] arr[min_idx] ^ arr[i];arr[min_idx] arr[min_idx] ^ arr[i];}}
}插入排序
嵌套循环默认第一个元素不处理每插入/增加一个数就依次跟前面的数两两对比将前面的所有数进行排好序 public void insertSort(int[] arr){for (int i 1; i arr.length; i) { // 外层循环len-1次// 对应外层的len-1次内层分别循环1到len-1次且后一个数 前一个数才会进循环交换for (int j i - 1; j 0 arr[j 1] arr[j]; j--){// 如果后一个元素更小就交换到前面来arr[j] arr[j] ^ arr[j 1];arr[j 1] arr[j] ^ arr[j 1];arr[j] arr[j] ^ arr[j 1];}}
}归并排序
递归到最底层时会执行merge排序回溯时排序保证了此时两个子数组都必然有序 // 不传参默认对整个数组进行归并排序
public void mergeSort(int[] arr) {if (arr null || arr.length 2) return;mergeSort(arr, 0, arr.length - 1);
}
// 传参则对[l, r]区间进行归并排序
public void mergeSort(int[] arr, int l, int r) {if (l r) return;int mid l ((r - l) 1);mergeSort(arr, l, mid);mergeSort(arr, mid 1, r);merge(arr, l, mid, r); // 回溯位置归并所以此时的子数组皆已排序完成
}
// 对 arr 的 [l, m] [m1, r] 两部分子数组进行归并排序
public void merge(int[] arr, int l, int m, int r) {int[] help new int[r - l 1]; // 辅助数组暂时存放归并后的数组int i 0;// 两个子数组的起始索引位置 p1 p2int p1 l, p2 m 1;// 精髓看数据哪边小就先挪哪边的数据到help数组里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];// 将暂存的归并后的数组覆盖到 arr 上使原数组排好序for (i 0; i help.length; i) {arr[l i] help[i];}
}快速排序
整体的quickSort函数swap后再进行partition划分三部分后区域 区域 分别递归调用局部的quicksort public void quickSort(int[] arr) {if (arr null || arr.length 2) return;quickSort(arr, 0, arr.length - 1);
}public void quickSort(int[] arr, int l, int r) {if (l r) {// 左神的随机让最右的r与[l,r-1]之间的随机一个数交换swap(arr, l (int) (Math.random() * (r - l 1)), r);// 先partition再进递归与归并的回溯时merge区分int[] p partition(arr, l, r);quickSort(arr, l, p[0] - 1); // 区域的左部分quickSort(arr, p[1] 1, r); // 区域的右部分}
}public 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 }; // 区域[ less1, more ]
}public void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;
}堆排序
堆是一种比较特殊的完全二叉树
分为大根堆、小根堆
由于完全二叉树的结构性质可以使用数组或列表等线性数据结构来存储堆(此处用优先级队列)
大根堆每个子树的最大节点是头结点
小根堆每个子树的最小节点是头结点 public static void heapSort(int[] arr) {if (arr null || arr.length 2) return;// 1. 先构建大根堆完成后就已知arr最大值(根节点的value)// 传统 heapInsert1// for (int i 0; i arr.length; i) {// heapInsert1(arr, i);// }// 进化 heapInsert2heapInsert2(arr);// 2. 取出根节点这个最大值与末尾节点做交换然后最大值相当于到末尾排好序了所以移除这个末尾(最大值)元素// 末尾节点到根节点位置后就heapify再去重新进行大根堆的构建int size arr.length;swap(arr, 0, --size);while (size 0) {heapify(arr, 0, size);swap(arr, 0, --size);}
}
// 1. 构建大根堆 v1.0 传统版
public static void heapInsert1(int[] arr, int index) {while (arr[index] arr[(index - 1) / 2]) {swap(arr, index, (index - 1) /2);index (index - 1)/2 ;}
}
// 1. 构建大根堆 v2.0 进化版
public static void heapInsert2(int[] arr){for (int i arr.length - 1; i 0; i--){heapify(arr, i, arr.length);}
}
// 2. 某个数在index位置能否往下(数组下标越大的方向)移动
public static void heapify(int[] arr, int index, int size) {int left index * 2 1;while (left size) {int largest left 1 size arr[left 1] arr[left] ? left 1 : left;largest arr[largest] arr[index] ? largest : index;if (largest index)break;swap(arr, largest, index);index largest;left index * 2 1;}
}public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;
}希尔排序
间隔分组且分组间隔依次减半每次分组后每个组内排序都是插入排序
相比于一开始就用插入排序希尔排序的比较次数更少效率更高
为什么呢大概是因为插入排序没预处理极端情况可能让一个很小很右的数一直比比比比比比到最开头浪费比较次数
而希尔排序会让每次分组比较后基本上左侧大区间 右侧大区间 类似 log(n) 但实际复杂度为 O ( n 1.3 − 2 ) O(n^{1.3-2}) O(n1.3−2) -表示范围不是减号
所以其实最坏情况和插入排序一样只不过可能性较小正常都比插入排序好些
public void shellSort(Comparable[] arr) {// 不断减半分组排序for (int gap arr.length / 2; gap 0; gap / 2) {// 对每个步长的整个数组进行插入排序for (int i gap; i arr.length; i) {// 内层就是插入排序但交换的间隔单位为gap不会影响其他分组for (int j i; j gap arr[j].compareTo(arr[j - gap]) 0; j - gap) {// 交换元素Comparable temp arr[j];arr[j] arr[j - gap];arr[j - gap] temp;}}}
}非比较排序桶排序
计数排序
省流词频表
// only for 0~200 value可以更大但太占内存空间了还不如换别的
// 仅适用于数组数据较为集中密集的情况太稀疏的话中间一堆内存空间浪费
public void countSort(int[] arr) {if (arr null || arr.length 2) return;int max Integer.MIN_VALUE;for (int i 0; i arr.length; i) {max Math.max(max, arr[i]);}// 一个词频表int[] bucket new int[max 1];for (int i 0; i arr.length; i) {bucket[arr[i]];}// 词频表中的数据依次取出放到arr保证有序int i 0;for (int j 0; j bucket.length; j) {while (bucket[j]-- 0) {arr[i] j;}}
}基数排序
数字按最多多少位先补齐
从个位开始排开始进桶再出桶完成个位上的优先级排序
从十位开始排还是进桶出桶完成十位上的优先级排序
依次百位千位… 越往后越晚排优先级越高
同时之前的优先级也会保留下来
所有都排完数组就有序了升序/降序
某种情况比计数排序好因为数字如果按照普通十进制理解则只需准备10个不同数字的桶就好了
局限得根据多少进制准备多个桶需要有进制这个前提规则
前提得知道空间范围比如人的年龄正数[0-200]否则内存爆炸
所以这种不基于比较的算法应用范围很局限大部分情况下不如之前的所有比较算法
图解如下
前缀和处理倒序入桶以及词频——比较难理解可以看下面左神讲解
左神桶排序 2:15:00
// 只适合非负数
public void radixSort(int[] arr) {if (arr null || arr.length 2) return;radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
// 计算数组中最大元素的位数比如324就是三位数
public int maxbits(int[] arr) {int max Integer.MIN_VALUE;for (int i 0; i arr.length; i) {max Math.max(max, arr[i]);}int res 0;while (max ! 0) {res;max / 10;}return res;
}public void radixSort(int[] arr, int begin, int end, int digit) {final int radix 10; // 默认十进制int i 0, j 0;// 有多少个数就准备多少个辅助空间int[] bucket new int[end - begin 1];// 有多少个“十进制位”就出桶进桶多少次所以循环digit次(从个位开始算)for (int d 1; d digit; d) {int[] count new int[radix];// 1. 遍历每一个arr元素根据外层循环次数取出个/十/百...位上的数字getDigit的作用for (i begin; i end; i) {j getDigit(arr[i], d);count[j];}// 2. 遍历好个/十/百...位上的所有数字后count数组记录了对于数字出现的频数// 接下来把词频数换成前缀数记录当前索引的数字个数处理成如下效果// 10个空间// count[0] 当前位(d位)是 0 的数字有多少个// count[1] 当前位(d位)是 0和1 的数字有多少个// count[2] 当前位(d位)是 0,1和2 的数字有多少个// count[i] 当前位(d位)是 0-i 的数字有多少个for (i 1; i radix; i) {count[i] count[i] count[i - 1];}// 3. 入桶操作从右往左遍历根据个/十/百...位上的数字大小进行相应入桶排好序for (i end; i begin; i--) {j getDigit(arr[i], d);bucket[count[j] - 1] arr[i];count[j]--;}// 4. 出桶操作将bucket(help)辅助数组覆盖赋值到原来的数组arr中for (i begin, j 0; i end; i, j) {arr[i] bucket[j];}}
}
// 获取一个整数 x 在指定位数 d 上的数字
public int getDigit(int x, int d) {return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
