- 排序算法，默认是升序，左边的值是属于“小”值
理解比较大小后的交换：当前元素cur 和 左边的元素cur-1， 左边的比较大，就交换或者挪动 array[cur] = array[cur-1];
- 编码的区间设置：建议是左闭 右开，方便 [begin, end)
- 计算方面：使用右移 代替 除法
☺ 排序算法---重点放到比较的排序算法---冒泡、选择、堆排序 插入、归并、快速、希尔，
对于计数排序、基数排序不是面试的重点
排序算法-冒泡、选择、堆排序
一、冒泡排序：
为什么要叫冒泡排序？ 因为形象生动上，每一轮都是最大的那个数冒到结尾
定义：
① 从头开始index=1 比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置；执行完一轮后，最末尾那个元素就是最大的元素。
② 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①，直到全部元素有序。
【一轮的比较范围是从1 到 end，然后根据理解得到end 从最后一个元素开始不断减少】
- 第一轮的比较，下标从1开始，左边比右边大进行交换
int array[] = {1, 3, 5, -1, -8}; //比较 end 的结束范围，从最后一个元素-第二个元素 for(int end = array.length - 1; end > 0; end--) { //冒泡排序-一轮的交换 for(int begin = 1; begin <= end; begin++) { if(array[begin] < array[begin-1]) {//当前元素的左边元素比较大时要交换 int temp = array[begin]; array[begin] = array[begin-1]; array[begin-1]=temp; } } }
优化1-冒泡排序
▪ 提前有序，终止比较（不一定有用：因为一般在随机数据中要提前有序的概率是很低的，）
- 布尔变量：假设本轮已经有序
//比较 end 的结束范围，从最后一个元素-第二个元素 for(int end = array.length - 1; end > 0; end--) { boolean sorted = true;//假设提前有序 //冒泡排序-一轮的交换 for(int begin = 1; begin <= end; begin++) { if(array[begin] < array[begin-1]) {//当前元素的左边元素比较大时要交换 int temp = array[begin]; array[begin] = array[begin-1]; array[begin-1]=temp; sorted = false;//本轮有交换，证明假设提前有序 不成立 } } if(sorted) break;//果然提前有序，不用再比较了 }
优化2-冒泡排序
- 如果序列尾部已经局部是有序的，可以记录最后一次交换的位置，从而减少比较的次数。
int array[] = {1, 3, 5, -1, -8}; //比较 end 的结束范围，从最后一个元素-第二个元素 for(int end = array.length - 1; end > 0; end--) { int sortedIndex = 1;//记录最后一次交换的位置，初始值为1，是为了考虑一开始数组就是完全有序的 //冒泡排序-一轮的交换 for(int begin = 1; begin <= end; begin++) { if(array[begin] < array[begin-1]) {//当前元素的左边元素比较大时要交换 int temp = array[begin]; array[begin] = array[begin-1]; array[begin-1]=temp; sortedIndex = begin;//记录最后一次交换的位置 } } end = sortedIndex;//更新比较范围到最后一次交换的位置 }
二、选择排序
为什么要叫选择排序？ 因为每一轮都是把最大的那个数的位置给选择出来
定义：
① 从序列中找出最大的那个元素，然后与最末尾的元素交换位置；执行完一轮后，最末尾的那个元素就是最大的元素。
② 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①
▪ 选择排序本质上看是冒泡的优化：
因为冒泡是从头到尾：相邻两个元素比较完就交换
选择排序是从头到尾：先找到最大元素位置，然后记录位置，最后才交换
int array[] = {1, 3, 5, -1, -8}; //比较 end 的结束范围，从最后一个元素-第二个元素 for(int end = array.length - 1; end > 0; end--) { int maxIndex = 0; //选择排序-找出本轮的最大值 for(int begin = 1; begin <= end; begin++) { if(array[maxIndex] <= array[begin]) {//取等号是为了变成稳定的排序算法 10 10() 8 --一轮比较--> 10 8 10() maxIndex = begin; } } //交换，把本轮找到的最大一个数放到结尾 int temp = array[maxIndex]; array[maxIndex] = array[end]; array[end] = temp; }
三、堆排序
▪ 堆排序本质上看是冒泡的优化：
选择排序是从头到尾：每一轮都在 从头到尾找到最大元素位置（内循环在找最大值）
---- 找最值，可以交给堆负责（优化）
▪ 堆排序：先原地建堆，然后尾部元素放到堆顶，然后下滤
int array[] = {1, 3, 5, -1, -8}; // 原地建堆 heapSize = arrayay.length; for (int i = (heapSize >> 1) - 1; i >= 0; i--) { siftDown(i); } while (heapSize > 1) { // 交换堆顶元素和尾部元素 int temp = array[0]; array[0] = array[heapSize]; array[heapSize] = temp; heapSize--; // 对0位置进行siftDown（恢复堆的性质） siftDown(0); } /** * 下滤 */ private void siftDown(int index) { int half = heapSize >> 1; Integer element = array[index]; while(index < half) { //index 必须是非叶子节点！！！ // 默认拿是左边跟父节点比大小 int childIndex = (index << 1) + 1; Integer childElement = array[childIndex]; int rightIndex = childIndex + 1; if(rightIndex < size && compare(array[rightIndex], childElement) > 0) { childElement = array[childIndex = rightIndex]; } if(compare(element, childElement) >= 0) break; //子结点大的话 array[index] = childElement; index = childIndex; } array[index] = element; }
排序算法-插入排序
一、插入排序
插入排序非常类似于扑克牌的排序
定义：① 在执行过程中，插入排序会将序列分为2部分；头部是已经排好序的，尾部是待排序的
② 从头开始扫描每一个元素；每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序
private void sort(Integer[] array) { ------------------------------------------- 核心代码开始 ------------------------------------------------------------ for(int begin = 1; begin < array.length; begin++) {//从无序区抓起的牌 int cur = begin; while(cur > 0 && cmp(array[cur], array[cur - 1]) < 0) {//这张牌不断往左边走，和紧邻[cur-1]的头部有序区进行比较,小于左边就交换 swap(array[cur], array[cur - 1]); cur--;//交换完，这个牌的位置 } } ------------------------------------------- 核心代码结束 ------------------------------------------------------------ } protected int cmp(int v1, int v2) { return v1 - v2; } protected void swap(int v1, int v2) { int tmp = v1; v1 = v2; v2 = tmp; }
优化1-插入排序
- 优化：挪动替换交换
private void sort(Integer[] array) { for(int begin = 1; begin < array.length; begin++) {//从无序区抓起的牌 int cur = begin; Integer v = array[cur]; while(cur > 0 && cmp(v, array[cur - 1]) < 0) {//头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置 array[cur] = array[cur-1];//左边的值比较大就往右边挪动 cur--; } //找到合适的位置，插入 array[cur] = v; } }
优化2-插入排序
- 找位置--使用二分搜索法(通过挪动左右指针，不断缩小一半的可能范围)
- 使用二分搜索优化了比较次数
细节：二分搜素的开始-结束区间[begin, end）
- int begin = 0； int end = array.length;
- 为什么结束要取 end，因为方便后续其他计算，比如算出该区间有多少元素
- 优化二分搜素[原：查找位置]为[查找待插入的位置]
▪ 原：查找到位置
查找目标位置的：查找过程分成三种判断条件：小于，去左边查找；大于，去右边查找；等于直接返回目标
▪ 现：查找到待插入位置
查找待插入的目标位置的：查找过程分成两种种判断条件：小于，去左边查找；大等于，去右边查找；因为这个等于不是待插入的目标位置
- 待插入的目标位置是第一个大于 待插入原始的值v 的元素位置
/** * 查找待插入位置的索引 */ private int search(int index) {//index 是待插入索引 int begin = 0; int end = index; while(begin < end) { int mid = (begin + end) >> 2; if(cmp(array[index], array[mid]) < 0) { end = mid; }else { begin = mid + 1; } } return begin; } private void sort(Integer[] array) { for(int begin = 1; begin < array.length; begin++) {//从无序区抓起的牌 Integer v = array[begin];//备份插入元素 int insertIndex = search(begin);//查找到合适的插入位置 for(int i = begin; i > insertIndex; i--) {//挪动腾出空间 array[i] = array[i - 1]; } array[insertIndex] = v; } }
排序算法-归并排序
一、归并排序
定义：
① 不断地将当前序列平均分割成2个子序列；直到不能再分割（序列中只剩1个元素）
② 不断地将2个子序列合并成一个有序序列；直到最终只剩下1个有序序列
int[] leftArray; int[] array; private void sort(int begin, int end) { if(end - begin < 2) return;//至少要有2个元素 int mid = (begin + end) >> 1; sort(begin, mid);//左边归并 sort(mid, end);//右边归并 merge(begin, mid, end);//最后进行合并 } /** * 将 [begin, mid) 和 [mid, end) 范围的序列数组合并成一个有序序列 */ private void merge(int begin, int mid, int end) { int li = 0, le = mid - begin;//左边数组leftArray int ri = mid, re = end;//右边数组 int ai = begin;//arrayay 的索引 for(int i = li; i < le; i++) {//拷贝arrayay左边数组到leftArray leftArray[i] = array[begin + i]; } while(li < le) {//左边还有元素 if(ri < re && cmp(array[ri], leftArray[li]) < 0) {//右边有元素，且右边的值更加小 array[ai++] = array[ri++]; }else { array[ai++] = leftArray[li++];//左边有元素，且左边的值更加小 } }
排序算法-快速排序、希尔排序
一、快速排序
快速排序的本质：逐渐将每一个元素都转换成轴点元素
定义：
① 从序列中选择一个轴点元素（pivot）
▪ 假设每次选择 0 位置的元素为轴点元素
② 利用 pivot 将序列分割成 2 个子序列
▪ 将小于 pivot 的元素放在pivot前面（左侧）
▪ 将大于 pivot 的元素放在pivot后面（右侧）
▪ 等于pivot的元素放哪边都可以
③ 对子序列进行 ① ② 操作
▪ 直到不能再分割（子序列中只剩下1个元素）
是一个递归排序：从轴点切分成两部分，不断地对左部分进行快速排序，不断地对右部分进行快速排序
判断该元素是 "甩"到左边 还是 右边，不加等号，因为加上等号会使得轴点元素分割出来的子序列极度不均匀
- 比如 6 6 6 6 6，轴点是6，那么取等号，全部给甩到一边了
int[] array; private void sort(int begin, int end) { if(end - begin < 2) return;//至少要有两个元素 int mid = pivotIndex(begin, end);//轴点，以轴点分割成了左右两部分 sort(begin, mid);//对左部分进行快速排序 sort(mid + 1, end);//对右部分进行快速排序 } /** * 对 [begin, end) 范围内的元素进行快速排序 */ private int pivotIndex(int begin, int end) { swap(begin, begin + (int)(Math.random() * (end - begin)));//随机交换begin位置的元素 Integer pivot = array[begin];//备份轴点元素 end--;//让右边指针直到元素上 ------------------------------------------- 核心代码开始 ------------------------------------------------------------ while(begin < end) { //内部使用了两个while 搭配 break，实现在右边找“小”、在左边找“大”后，对数组指针指向"调头" while(begin < end) { //不加等号，因为加上等号会使得轴点元素分割出来的子序列极度不均匀 if(cmp(pivot, array[end]) < 0) {// 右边元素>轴点元素,不是目标，要在右边找“小” end--; }else { array[begin++] = array[end]; break; } } while(begin < end) { if(cmp(pivot, array[begin]) > 0) {// 左边元素<轴点元素,不是目标，要在左边找“大” begin++; }else { array[end--] = array[begin]; break; } } } ------------------------------------------- 核心代码结束 ------------------------------------------------------------ array[begin] = pivot;//数组轴点元素进行赋值 return begin; } protected int cmp(int v1, int v2) { return v1 - v2; } protected void swap(int v1, int v2) { int tmp = v1; v1 = v2; v2 = tmp; }
二、希尔排序
切分成n 列然后进行排序--> 逆序对数量逐渐减少 --> 希尔排序，底层是使用插入排序，也可以把希尔看成是对插入排序的改进版
int[] array; private void sort() { List<Integer> stepSequence = shellStepSequence(); for(Integer step: stepSequence) {//按照每个步长进行切割，然后进行一一对应的比较 排序 sort(step); } } /** * 按照给定的步长进行切割，然后对 step 列进行排序 */ private void sort(Integer step) { ------------------------------------------- 核心代码开始 ------------------------------------------------------------ // col: 第几列 for(int col = 0; col < step; col++) {//对col列进行排序 // 第col 列中的元素: col、col+2*step、col+3*step、col+4*step // 结合了步长的插入排序 for(int begin = col + step; begin < array.length; begin++) { int cur = begin; while(cur > col && cmp(array[cur], array[cur - step]) < 0) { swap(array[cur], array[cur - step]); cur -= step; } } } ------------------------------------------- 核心代码结束 ------------------------------------------------------------ } /** * 步长序列：获取 step 步长分割数组 */ private List<Integer> shellStepSequence(){ List<Integer> stepSequence = new ArrayList<>(); int step = array.length; while((step >>= 1) > 0) { stepSequence.add(step); } return stepSequence; } protected int cmp(int v1, int v2) { return v1 - v2; } protected void swap(int v1, int v2) { int tmp = v1; v1 = v2; v2 = tmp; }
▪ 冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序 [面试会考]
- 平均时间复杂度目前最低是 O(nlogn)
▪ 计数排序、桶排序、基数排序，都不是基于比较的排序 [面试不考，作为了解]
- 它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比 O(nlogn) 更低
排序算法-计数排序、基数排序、桶排序
一、计数排序
细节：在java 整型数组，new出数组之后，内部元素默认都是 0
int counts = new int[10]; //new 完，默认所有元素都是0
int[] array; private void sort() { //找出最大值 int max = array[0]; for(int i = 1; i < array.length; i++) { if(array[i] > max) { max = array[i]; } } ------------------------------------------- 核心代码开始 ------------------------------------------------------------ // 开辟内存空间，存储每一个整数出现的次数 int[] counts = new int[1 + max];//整型数组，new出数组之后，内部元素默认都是 0 //统计每个整数出现的次数 for(int i = 0; i < array.length; i++) { counts[array[i]]++; } //根据整数出现次数，对整数进行排序 int index = 0;//整数数组上的指针 for(int i = 0; i < counts.length; i++) { while(counts[i]-- > 0) { array[index++] = i; } } ------------------------------------------- 核心代码结束 ------------------------------------------------------------ }
■ 计数排序缺点：
- 无法对负整数进行排序
- 极其浪费内存空间
- 是个不稳定的排序
■ 计数排序的优化
int[] array; private void sort() { // 找出最大值、最小值 int max = array[0];//最大值 int min = array[0];//最小值 for(int i = 1; i < array.length; i++) { if(array[i] > max) { max = array[i]; } if(array[i] < min) { min = array[i]; } } ------------------------------------------- 核心代码开始 ------------------------------------------------------------ //开辟内存空间，存储次数 int[] counts = new int[max - min + 1]; //统计每个整数出现的次数 for(int i = 0; i < array.length; i++) { counts[array[i] - min]++; } //累加次数 for(int i = 1; i < counts.length; i++) { counts[i] += counts[i - 1]; } //从后往前遍历元素，将它放到有序数组中的合适位置 int[] newArray = new int[array.length]; for(int i = array.length - 1; i >= 0; i--) { newArray[--counts[array[i] - min]] = array[i];// 公式 count[k - min] -p 其中p是该元素k倒数着出现的次数 } ------------------------------------------- 核心代码结束 ------------------------------------------------------------ //将有序数组赋值到array for(int i = 0; i < newArray.length; i++) { array[i] = newArray[i]; } }
二、基数排序
定义：依次对个位数、十位数、百位数、千位数、万位数...进行排序（从低位到高位）
int[] array; private void sort() { // 找出最大值 int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } } // max = 593 // 个位数 array[i] / 1 % 10 = 3 // 十位数 array[i] / 10 % 10 = 9 // 百位数 array[i] / 100 % 10 = 5 for (int divider = 1; divider <= array.length; divider *= 10) { countingSort(divider); } } private void countingSort(int divider) { // 开辟内存空间，存储次数 int[] counts = new int[10];//给个位数、十位数、百位数排序，它们的范围都是 0-9 // 统计每个整数出现的次数 for (int i = 0; i < array.length; i++) { // counts[array[i]的基数]++; counts[array[i] / divider % 10]++; } // 累加次数 for (int i = 1; i < counts.length; i++) { counts[i] += counts[i - 1]; } // 从后往前遍历元素，将它放到有序数组中的合适位置 int[] newArray = new int[array.length]; for (int i = array.length - 1; i >= 0; i--) { // newArray[--counts[array[i]的基数] = array[i]; newArray[--counts[array[i] / divider % 10]] = array[i]; } // 将有序数组赋值到array for (int i = 0; i < newArray.length; i++) { array[i] = newArray[i]; } }
■ 基数排序的另外一种思路：元素先存到桶里，然后再回收
三、桶排序
如果本文对你有帮助的话记得给一乐点个赞哦，感谢！
