当前位置： 首页 > news >正文

常见算法的总结与实现思路

news 2025/4/29 8:55:35

前言

hello，我是Maybe。昨天和今天花了两天左右的时间。把常见的排序算法都学完了，自己也实现了一遍。感觉收获满满，但是过程是艰辛的。下面我将分享代码和思维导图，希望可以帮助到大家。

思维导图(含注意事项，实现思路，含算法的总结(如时间复杂度，稳定性））

代码如下(按思维导图的顺序)

public class Sort {public void zhijiecharu(int[] arr){for(int i=1;i<arr.length;i++){int tmp=arr[i];int j=i-1;for(;j>=0;j--){if(arr[j]>tmp){arr[j+1]=arr[j];}else{arr[j+1]=tmp;break;}}arr[j+1]=tmp;}}public void xierpaixu(int [] arr){int gap=arr.length;while(gap>1){//gap的最后取值一定要是0gap=gap/2;xierpaixu1(arr,gap);}}public void xierpaixu1(int[] arr,int gap){for(int i=gap;i<arr.length;i=i+gap){int tmp=arr[i];int j=i-gap;for(;j>=0;j=j-gap){if(arr[j]>tmp){arr[j+gap]=arr[j];}else{arr[j+gap]=tmp;break;}}arr[j+gap]=tmp;}}public void swap(int[] array,int i,int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}public void xuanzepaixu(int[] array){for(int i=0;i<array.length;i++){int minIndex=i;for(int j=i+1;j<array.length;j++){if(array[j]<array[minIndex]){minIndex=j;}}swap(array,i,minIndex);}}public void xuanzepaixu1(int[] array){int left=0;int right=array.length-1;while(left<right){int minIndex=left;int maxIndex=left;for(int i=left+1;i<array.length;i++){if(array[i]<array[minIndex]){minIndex=i;}if(array[i]>array[maxIndex]){maxIndex=i;}}swap(array,left,minIndex);//注意当left=maxIndex时if(left==maxIndex){maxIndex=minIndex;}swap(array,maxIndex,right);left++;right--;}}public void createHeap(int[] array){//创建堆for(int parent=(array.length-1-1)/2;parent>=0;parent--){siftDown(array,parent,array.length);}}private void siftDown(int[] array, int parent, int length) {//创建大根堆int child=2*parent+1;while(child<length-1){//找左右子树最大值if(child+1<length-1&&array[child]<array[child+1]){child++;}if(array[parent]<array[child]){swap(array,parent,child);child=parent;child=2*child+1;}else{break;}}}public void Heapsort(int[] array){//从小到大排，必须要是大根堆createHeap(array);int end=array.length-1;while(end>0){swap(array,0,end);//则最后一个元素一定是最大的siftDown(array,0,end);end--;}}public void bubble_sort(int[] array){for(int i=0;i<array.length-1;i++){boolean flg=false;for(int j=0;j<array.length-1-i;j++){if(array[j]>array[j+1]){swap(array,j,j+1);flg=true;}}if(!flg){break;}}}public void quicksort(int[] array){quick(array,0,array.length-1);}private void quick(int[] array, int start, int end) {//1.递归终止条件if(start>=end){return;}if(end-start+1<=3){//这里直接使用快直接插入处理了zhijiecharuRange(array,start,end);return;}//使用三数取中法优化int minIndex=getMid(array,start,end);swap(array,start,minIndex);int pivot=wakong(array,start,end);
//        int pivot=hoare(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}private int getMid(int[] array, int left, int right) {int minindex=(left+right)/2;if(array[left]<array[right]){if(array[minindex]<array[left]){return left;}else if(array[minindex]>array[right]){return right;}else{return minindex;}}else{if(array[minindex]>array[left]){return left;}else if(array[minindex]<array[right]){return right;}else{return minindex;}}}private void zhijiecharuRange(int[] array, int start, int end) {for(int i=start+1;i<=end;i++){int tmp=array[i];int j=i-1;for(;j>=start;j--){if(array[j]>array[i]){array[i]=array[j];}else{array[i]=tmp;break;}}array[j+1]=tmp;}}private int wakong(int[] array, int left, int right) {int tmp=array[left];while(left<right){while(left<right&&array[right]>=tmp){//注意 这里面也要写left<right,防止越界right--;}array[left]=array[right];while(left<right&&array[left]<=tmp){left++;}array[right]=array[left];}array[left]=tmp;return left;}private int hoare(int[] array,int left,int right){int tmp=array[left];int tmpLeft=left;while(left<right){while(left<right&&array[right]>=tmp){right--;}while(left<right&&array[left]<=tmp){left++;}//等两个找到才换，与挖空法注意区分swap(array,left,right);}swap(array,tmpLeft,left);return left;}public static void mergeSort(int[] array) {mergeSortTmp(array,0,array.length-1);}private static void mergeSortTmp(int[] array,int left,int right) {//先分解，再合并while(left>=right){return;}int mid=(left+right)/2;mergeSortTmp(array,left,mid);mergeSortTmp(array,mid+1,right);//合并数组merge(array,left,mid,right);}private static void merge(int[] array, int left, int mid, int right) {int[] tmp=new int[right-left+1];int k=0;int s1=left;int e1=mid;int s2=mid+1;int e2=right;//确保两个数组都有元素和防止越界while(s1<=e1&&s2<=e2){if(array[s1]>array[s2]){tmp[k++]=array[s2++];}else{tmp[k++]=array[s1++];}}//因为可能有多个元素//则s2的元素全都放置到了tmp数组里面while(s1<=e1){tmp[k++]=array[s1++];}while(s2<=e2){tmp[k++]=array[s2++];}//讲tmp数组写到array里面for(int i=0;i<k;i++){array[i+left]=tmp[i];}}public void jishupaixu(int[] array){//1.在待排序的元素中找出数组的最大值和最小值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];}}//创建count数组去计数//遍历待排序的数组，计数放入count中int len=max-min+1;int[] count=new int[len];for(int i=0;i<array.length;i++){int index=array[i]-min;count[index]++;}//依次遍历计数数组int index=0;for(int i=0;i<len;i++){while(count[i]!=0){array[index]=i+min;index++;count[i]--;}}}}

import java.util.Arrays;public class Test {public static void main(String[] args) {int[] array={99,93,92,97,98,99,96,95};Sort sort=new Sort();
//        sort.zhijiecharu(array);System.out.println(Arrays.toString(array));sort.jishupaixu(array);System.out.println(Arrays.toString(array));}
}

结语 

希望可以帮助到大家。see U~~

 

 

 

http://www.xdnf.cn/news/199567.html

相关文章：

  • 【补题】ACPC Kickoff 2025 F. Kinan The Bank Robber
  • tensor 的计算操作
  • C#核心知识
  • Allegro23.1新功能之如何解冻动态铜皮操作指导
  • Druid监控sql导致的内存溢出
  • [Windows] MousePlus 5.5.9
  • 盈飞无限再出重磅新品 AI版质量智能双星璀璨
  • QML文件中如何创建QML对象并打开
  • 机器学习day3 - KNN的api调用
  • Vue3 项目中 Pinia 与 JavaScript 循环依赖问题深度解析
  • 三小时快速上手TypeScript之接口
  • SoapUi测试1——REST（WebAPi、Json协议/HTTP、Post通讯方式）接口测试
  • 【AI 工业应用 】AI大模型在工业领域(CAD等)的前景与实战
  • 1.8空间几何与场论
  • OpenGL进阶系列21 - OpenGL SuperBible - blendmatrix 例子学习
  • [26] cuda 应用之 nppi 实现图像格式转换
  • 企业 AD 域安全10大风险场景解析
  • Redis常用数据结构解析：从原理到实战应用
  • Python（14）推导式
  • Linux文件的一般权限
  • 2799. 统计完全子数组的数目
  • [Spring] Sentinel详解
  • Linux常见基础命令
  • i/o复用函数的使用——epoll
  • jclasslib 与 BinEd 结合的二进制分析技术指南
  • 【计算机系统结构】第四章
  • 利用EMQX实现单片机和PyQt的数据MQTT互联
  • 数据库系统概论|第三章：关系数据库标准语言SQL—课程笔记6
  • 计算机基础—（九道题）
  • 云上玩转DeepSeek系列之六：DeepSeek云端加速版发布，具备超高推理性能