Java 排序

Ne0inhk

— 14 min read
Java 排序

文章目录

在这里插入图片描述

排序

  1. 稳定的排序：排序之前和排序之后它们俩的相对顺序没有发生变化
  2. 内部排序：在内存上的排序
  3. 外部排序：需要借助磁盘等外部空间进行的排序

插入排序

  1. 思想：假设这组数据的第一个元素是有序的，从第二个元素和前面的元素进行比较，找到合适的位置进行插入
在这里插入图片描述
// 插入排序publicstaticvoidinsertSort(int[] array){for(int i =1;i < array.length;i++){int j = i -1;int tmp = array[i];for(;j >=0;j--){if(array[j]> tmp){ array[j+1]= array[j];}else{break;}} array[j +1]= tmp;}}

分析

  1. 时间复杂度：O(N^2)
    最坏情况：O(N^2)
    最好情况：有序的数组，O(N)
    数据越有序，排序越快
    适用于待排序数组基本上趋于有序了，时间复杂度趋于O(N)
  2. 空间复杂度：O(1)
  3. 稳定性：是一个稳定的排序
    例子：5 5 7
    稳定的排序可以改成不稳定的排序，但是不稳定的排序不能改成稳定的排序

希尔排序

  1. 对直接插入排序进行了优化，如果是 5 4 3 2 1 会退化为O(N^2)
  2. 分组：分完组后，每组都采用直接插入排序
  3. 中间隔一些元素进行分组的好处：比较大的元素都往后走了，比较小的元素都往前走了
  4. 缩小增量到最后会把整体看成是一组，5 3 1 组，前面的5 3 都是预排序，真正的排序是最后的一组
  5. 缩小增量的目的：为了让排序更接近O(N)，为了让排序更快
在这里插入图片描述


在这里插入图片描述
// 希尔排序publicstaticvoidshellSort(int[] array){int gap = array.length;while(gap >1){ gap /=2;shell(array,gap);}}// 对每组进行插入排序publicstaticvoidshell(int[] array,int gap){for(int i = gap;i < array.length;i++){int j = i - gap;int tmp = array[i];for(;j >=0;j -= gap){if(array[j]> tmp){ array[j+gap]= array[j];}else{break;}} array[j + gap]= tmp;}}

分析

  1. 时间复杂度：O(N^1.3 - N ^ 1.5)，时间复杂度不好计算
  2. 空间复杂度：O(1)
  3. 稳定性：不稳定的排序

检测排序速度：

publicstaticvoidtestInsert(int[] array){long startTime =System.currentTimeMillis();int[] tmp =Arrays.copyOf(array,array.length);Sort.insertSort(tmp);long endTime =System.currentTimeMillis();System.out.println(" "+(endTime - startTime));}publicstaticvoidtestShell(int[] array){long startTime =System.currentTimeMillis();int[] tmp =Arrays.copyOf(array,array.length);Sort.shellSort(tmp);long endTime =System.currentTimeMillis();System.out.println(" "+(endTime - startTime));}// 逆序初始化publicstaticvoidinitOrder(int[] array){for(int i =0;i < array.length;i++){ array[i]= array.length - i;}}publicstaticvoidmain(String[] args){int[] arr =newint[10000];initOrder(arr);testInsert(arr);testShell(arr);}

选择排序

在当前i下标对应的值的后面，找到后面最小的值和i下标对应的值交换

// 交换publicstaticvoidswap(int i,int j,int[] array){int tmp = array[i]; array[i]= array[j]; array[j]= tmp;}// 选择排序publicstaticvoidselectSort(int[] array){// 在i下标的后面找到比i下标对应的值的最小值,然后交换int n = array.length;for(int i =0;i < n;i++){int minIndex = i;for(int j = i +1;j < n;j++){if(array[j]< array[i]){if(array[j]< array[minIndex]){ minIndex = j;}}}swap(i,minIndex,array);}}

双向选择排序
时间复杂度还是O(N^2)
左边找最大的，右边找最小的，和第一个数和最后一个数交换

在这里插入图片描述


存在缺陷，maxIndex下标可能是在0下标是最大的，0下标会和最小值小标的值交换，那么0下标就不是最大值下标，应该更新为maxIndex = minIndex

在这里插入图片描述
publicstaticvoidselectSort2(int[] array){// 在i下标的后面找到比i下标对应的值的最小值,然后交换int left =0;int right = array.length -1;while(left < right){int minIndex = left;int maxIndex = left;for(int i = left +1;i <= right;i++){if(array[i]< array[minIndex]){ minIndex = i;}if(array[i]> array[maxIndex]){ maxIndex = i;}}swap(left,minIndex,array);// 第一个数是最大的数,防止最小的下标和第一个数换了,最大值就在minIndex的位置了if(maxIndex == left){ maxIndex = minIndex;}swap(right,maxIndex,array); left++; right--;}}

分析

  1. 时间复杂度：O(N^2)
  2. 空间复杂度：O(1)
  3. 稳定性：不稳定的排序

堆排序

// 堆排序privatestaticvoidshifDown(int[] array,int parent,int len){int child =2* parent +1;while(child < len){if(child +1< len && array[child]< array[child +1]){ child++;}if(array[child]> array[parent]){swap(child,parent,array); parent = child; child =2* parent +1;}else{break;}}}privatestaticvoidcreateHeap(int[] array){// 建立大根堆for(int parent =(array.length -1-1)/2;parent >=0;parent--){shifDown(array, parent, array.length);}}publicstaticvoidheapSort(int[] array){createHeap(array);int end = array.length -1;while(end >0){swap(end,0,array);shifDown(array,0,end); end--;}}

分析

  1. 时间复杂度：O(N * logN)
  2. 空间复杂度：O(1)
  3. 稳定性：不稳定的排序

冒泡排序

// 冒泡排序publicstaticvoidbubbleSort(int[] array){// i是趟数for(int i =0;i < array.length;i++){// j是比较的大小的boolean flag =true;for(int j =0;j < array.length - i -1;j++){if(array[j]> array[j +1]){swap(j,j +1,array); flag =false;}}if(flag){break;}}}

分析

  1. 时间复杂度：O(N ^ 2)
  2. 空间复杂度：O(1)
  3. 稳定性：稳定的排序

快速排序

霍尔法

  1. 根据二叉树进行递归划分
在这里插入图片描述
// 快速排序publicstaticvoidquickSort(int[] array){quick(array,0,array.length -1);}privatestaticvoidquick(int[] array,int start,int end){if(start >= end){return;}int prvot =partitionHoare(array,start,end);quick(array,start,prvot -1);quick(array,prvot +1,end);}privatestaticintpartitionHoare(int[] array,int left,int right){// 基准元素int tmp = array[left];// 记录第一个基准下标int i = left;while(left < right){// 必须先找先右再左// 找小while(left < right && array[right]>= tmp){ right--;}// 找大while(left < right && array[left]<= tmp){ left++;}swap(left, right, array);}swap(i,left,array);return left;}
  1. 为什么有等于号？
    没有等于号，会死循环，比如两端都是6
在这里插入图片描述

为什么先从右边开始，不先从左边开始？
先走左边的话，先遇到大的停下来，如果相遇的话，那么相遇位置的值就是大于基准元素的，这时候交换的话，6的左边有一个数比6大

在这里插入图片描述

分析

  1. 时间复杂度：
    最好情况下：O(N * logN)
    每层都有N个节点，高度为logN，需要每个节点都遍历到，N * logN次遍历
    最坏情况下：O(N^2)，有序/逆序，单分支的树
  2. 空间复杂度：
    最好情况下：O(logN)
    最坏情况下：O(N)，有序/逆序，单分支的树
    递归左边再递归右边，递归右边左边没有释放
  3. 稳定性：不稳定的排序

挖坑法找基准

  1. 先走右边再走左边，以第一个元素为基准，并且拿出基准元素，基准元素的位置就是坑，如果右边找到比基准小的，把它放入坑中，左边找到比基准元素大的放到坑中，最后两者相遇，把基准元素放入其中
// 挖坑法privatestaticintpartitionHole(int[] array,int left,int right){// 基准元素int tmp = array[left];while(left < right){// 必须先找先右再左// 找小while(left < right && array[right]>= tmp){ right--;} array[left]= array[right];// 找大while(left < right && array[left]<= tmp){ left++;} array[right]= array[left];} array[left]= tmp;return left;}

前后指针法

  1. 如果cur比基准元素小并且cur下标的值和prev下标的值不相等，
在这里插入图片描述
// 前后指针法publicstaticintpartition(int[] array,int left,int right){int prev = left;int cur = left +1;while(cur <= right){while(array[cur]< array[left]&& array[++prev]!= array[cur]){swap(cur,prev,array);} cur++;}swap(prev,left,array);return prev;}

题目

  1. 优先试挖坑法，其次是Hoare，最后是前后指针法

A

在这里插入图片描述

快排的优化

  1. 均匀的分割数组
  2. 让递归的次数变少
三数取中法
  1. 三数取中法：left，right，mid三个下标中的中间值和第一个数交换位置，然后右边找比基准元素小的值，左边找比基准元素大的值

规定array[mid] <= array[left] <= array[right]

在这里插入图片描述
// 三数取中法,求中位数的下标privatestaticintmiddleNum(int[] array,int left,int right){int mid =(left + right)/2;if(array[left]< array[right]){// 1. x < 3 < 9// 2. 3 < 9 < x// 3. 3 < x < 9if(array[mid]< array[left]){return left;}elseif(array[mid]> array[right]){return right;}else{return mid;}}else{// 9 > 3 == left > right// 1. x > left > rightif(array[mid]> array[left]){return left;}elseif(array[right]> array[mid]){// 2. left > right > xreturn right;}else{// 3. left > x > rightreturn mid;}}}privatestaticvoidquick(int[] array,int start,int end){if(start >= end){return;}// 1 2 3 4 5 6 7// 中间值的下标和第一个数交换,作为新的基准元素int index =middleNum(array,start,end);swap(index,start,array);// 4 2 3 1 5 6 7// 为了让左右分布更均匀,降低树的高度,减少递归的次数int prvot =partition(array,start,end);quick(array,start,prvot -1);quick(array,prvot +1,end);}

只剩最后几层时，使用插入排序进行优化，降低递归次数，可以使用插入排序是因为前面递归成有序的序列了

publicstaticvoidinsertSort(int[] array,int left,int right){for(int i = left +1;i <= right;i++){int j = i -1;int tmp = array[i];for(;j >= left;j--){if(array[j]> tmp){ array[j+1]= array[j];}else{break;}} array[j +1]= tmp;}}privatestaticvoidquick(int[] array,int start,int end){if(start >= end){return;}if(end - start +1<=15){// 减少递归的次数// 因为最后几层节点数最多,递归次数也多insertSort(array,start,end);return;}// 1 2 3 4 5 6 7// 中间值的下标和第一个数交换,作为新的基准元素int index =middleNum(array,start,end);swap(index,start,array);// 4 2 3 1 5 6 7// 为了让左右分布更均匀,降低树的高度,减少递归的次数int prvot =partition(array,start,end);quick(array,start,prvot -1);quick(array,prvot +1,end);}

非递归实现快排

  1. 找基准里面会进行交换元素，进行排序，外面就进行找到左右下标位置
在这里插入图片描述
// 非递归实现快速排序publicstaticvoidquickSortNor(int[] array){int start =0;int end = array.length -1;Stack<Integer> stack =newStack<>();int pivot =partitionHoare(array,start,end);if(pivot -1> start){// 左边有两个元素 stack.push(start); stack.push(pivot -1);}elseif(pivot +1< end){// 右边至少有两个元素 stack.push(pivot +1); stack.push(end);}// 找基准里面会互换元素进行排序while(!stack.empty()){ end = stack.pop(); start = stack.pop(); pivot =partitionHoare(array,start,end);if(pivot -1> start){// 左边有两个元素 stack.push(start); stack.push(pivot -1);}elseif(pivot +1< end){// 右边至少有两个元素 stack.push(pivot +1); stack.push(end);}}

归并排序

  1. 分解：根据mid进行分解

合并：第一个有序段和第二个有序段，比较大小放入一个新的数组中

在这里插入图片描述
// 归并排序publicstaticvoidmergeSort(int[] array){merge(array,0,array.length -1);}privatestaticvoidmerge(int[] array,int start,int end){if(start >= end){return;}int mid =(start + end)/2;// 分解merge(array,start,mid);merge(array,mid +1,end);// 合并mergeHeB(array,start,mid,end);}privatestaticvoidmergeHeB(int[] array,int left,int mid,int right){int s1 = left;int e1 = mid;int s2 = mid +1;int e2 = right;// 新数组的下标int k =0;int[] tmpArray =newint[right - left +1];while(s1 <= e1 && s2 <= e2){if(array[s1]< array[s2]){ tmpArray[k++]= array[s1++];}else{ tmpArray[k++]= array[s2++];}}while(s1 <= e1){ tmpArray[k++]= array[s1++];}while(s2 <= e2){ tmpArray[k++]= array[s2++];}// left是因为有左边还有右边的数组// tmpArray是临时数组,会销毁的,需要拷贝回原来的数组for(int i =0;i < tmpArray.length;i++){ array[i + left]= tmpArray[i];}}

分析

  1. 时间复杂度：O(N * logN)
  2. 空间复杂度：O(N)，因为每次合并数组的时候要开O(N)大小的额外空间
  3. 稳定性：稳定的排序

非递归实现归并排序

  1. 先一个一个有序，两个两个有序，四个四个有序，八个八个有序…
  2. gap = 1
    left = i
    mid = left + gap - 1
    right = mid + gap
    gap *= 2
  3. 每组合并完，最终就有序了
在这里插入图片描述
// 非递归实现归并排序publicstaticvoidmergeSortNor(int[] array){// gap表示每组的数据个数int gap =1;while(gap < array.length){for(int i =0;i < array.length;i = i +2* gap){int left = i;// mid和right可能会越界// 比如只有5个元素// 分解右边一半的时候// l = i mid = 5 r = 7int mid = left + gap -1;int right = mid + gap;if(mid >= array.length){ mid = array.length -1;}if(right >= array.length){ right = array.length -1;}mergeHeB(array,left,mid,right);} gap *=2;}}

海量数据的排序

  1. 使用归并排序进行外部排序，如果内存中不够空间的话
在这里插入图片描述

非比较的排序

计数排序

  1. 通过统计每次数字出现的次数，最后按照顺序从小到大输出这些数字
  2. 适用的场景：指定范围内的数据
在这里插入图片描述
// 计数排序,指定范围内的数据进行排序// O(Max(N，范围))publicstaticvoidcountSort(int[] array){int minVal = array[0];int maxVal = array[0];// O(N)for(int i =0;i < array.length;i++){if(minVal > array[i]){ minVal = array[i];}if(maxVal < array[i]){ maxVal = array[i];}}int len = maxVal - minVal +1;int[] count =newint[len];// O(N)for(int i =0;i < array.length;i++){ count[array[i]- minVal]++;}// 写回array数组中// O(范围)// 因为count数组集中于一个数字,那么也是O(范围)// 如果count数组不集中于一个数子,也是N倍的范围// 也是O(范围)int k =0;for(int i =0;i < count.length;i++){while(count[i]>0){ array[k++]= i + minVal; count[i]--;}}}

分析

  1. 时间复杂度：O(Max(N，范围))
  2. 空间复杂度：O(范围)
  3. 稳定性：稳定的排序

基数排序

  1. 开10个大小的空间，分别依次比较个位大小，十位大小和百位大小，最终达到有序，每个空间都是一个队列
在这里插入图片描述

桶排序

  1. 先把数字放入一个范围的区间内进行排序，排好序依次拿出来，最终就有序了
在这里插入图片描述

Read more

《算法题讲解指南：优选算法-模拟》--41.外观数列，42.数青蛙

《算法题讲解指南：优选算法-模拟》--41.外观数列，42.数青蛙

🔥小叶-duck：个人主页 ❄️个人专栏：《Data-Structure-Learning》 《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心 ✨未择之路，不须回头 已择之路，纵是荆棘遍野，亦作花海遨游 目录 41.外观数列 题目链接： 题目描述： 题目示例： 解法（模拟）： 算法思路： C++算法代码： 算法总结及流程解析： 42.数青蛙 题目链接： 题目描述： 题目示例： 解法（模拟+分情况讨论）： 算法思路： C++算法代码： 算法总结及流程解析： 结束语 41.外观数列 题目链接： 38. 外观数列 - 力扣（LeetCode） 题目描述： 题目示例：

By Ne0inhk
MAX30102血氧心率模块讲解二：驱动代码及计算算法

MAX30102血氧心率模块讲解二：驱动代码及计算算法

目录 一、摘要 二、iic库 三、max30102的驱动层函数 1. MAX30102 I2C设备地址  2.向MAX30102寄存器写入数据 3.从MAX30102寄存器读取数据 4.初始化MAX30102传感器  5.重置MAX30102传感器，读取MAX30102的设备ID，清空MAX30102 FIFO缓冲区，启用或禁用MAX30102的低功耗模式 四、max30102应用层函数 1.初始化MAX30102传感器和数据缓冲区的函数 2.常态化读取并计算心率和血氧值的函数 五、MAX30102心率和血氧计算函数 1.心率监测(HR) 2.血氧测量(SpO2) 3.心率计算原理： 4.血氧饱和度(SpO2)计算 5.数据过滤与平均 6.MAX30102心率和血氧计算函数讲解： 代码和资料链接： 一、摘要  第一篇文章有详细讲解MAX30102血氧心率模块引脚定义、

By Ne0inhk
【C语言】排序算法——希尔排序以及插入排序 ——详解！！！

【C语言】排序算法——希尔排序以及插入排序 ——详解！！！

【C语言】排序算法——希尔排序以及插入排序详解 * 前言 * 一 、插入排序 * 1. 视频演示 * 2. 算法思想 * 3. 实现思路 * 4. 代码演示 * 二 、希尔排序 * 1. 视频演示 * 2. 算法思想 * 3. 实现思路 * （1）分组 * （2）预排序 * （3）最终排序 * （4）gap的取值 * 4. 代码演示 * 结语 前言 在学习循环的时候，我们学习到了冒泡排序这个算法 那么，除了冒泡排序，还有什么排序算法呢？ 今天给大家带来的是插入排序以及希尔排序 一 、插入排序 1. 视频演示 首先给大家看一段视频，让大家先看看插入排序是怎么运行的 插入排序演示 2. 算法思想 我们可以从视频里看见，

By Ne0inhk
【算法通关指南：数据结构和算法篇 】栈相关算法题：1. 【模板】栈，2.有效的括号

【算法通关指南：数据结构和算法篇 】栈相关算法题：1. 【模板】栈，2.有效的括号

🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南 》 ✨ 永远相信美好的事情即将发生 文章目录 * 前言 * 一、【模板】栈 * 1.1题目 * 1.2算法原理 * 1.3代码 * 1.3.1 STL版本 * 1.3.2 模拟版本 * 二、有效的括号 * 2.1题目 * 2.2算法原理 * 2.3代码 * 总结与每日励志 前言 本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力ps:

By Ne0inhk