vlambda博客
学习文章列表

On the March-附快速排序和堆排序代码

It's a special month for me in 2021.
二月还能借着过年这个大背景玩玩闹闹吃吃喝喝,三月真是不走寻常路。听说过求职的金三银四,没想到金三已经到了结尾。
做科研的时候在想——找了实习就好了;找实习的时候在后悔,还是做科研看起来更轻松一些。
简历从二月底准备到三月初,拿着简历1.0被电话面试问得猝不及防,第二天回过神来修改了简历做出第二版,现在手里的第二版专业技能也不突出。推销自己对我来说真的好难,过往的经历都没有好好记录下来,再次复盘的时候要花费很多时间。以及,很多面试问题根本没想过回答,面试的时候雷区蹦迪,终止于二面。
第一次做测评内心紧张和激动,在后来的测评中,心情逐渐平静。毕竟,这是最简单的一部分了。后面的笔试和面试哪个不比测评复杂。
第一次做笔试,笔试前一晚刚刚学会Scanner读取输入,第一题思路简单,但是数据处理那里卡了一刻钟还多,留给第二题的时间只有5min,根本来不及写。甚至还提前交了卷。
第一次面试,也是很紧张,面试前浏览面经,熟悉简历上写的技能。本以为自己在面试前有时间能够学会简历上写的稍微进阶的技能,结果时间还是来不及。每次面试都有新的知识盲区,每次笔试也有新的知识盲区。胆子大到写“熟悉操作系统”,找CS的同学了解了一下,操作系统的课程要学两个学期,当代面试无知者无畏的典型代表是我了。
第一次收到感谢信,释然了。因为那场面试的表现并不理想,但是面试的体验很不错。又找到了新的知识盲区。以及,coding能力不够。
认识的同学陆陆续续找到实习,我还在池子里等着被捞。不到一个月的时间准备用来找实习确实有点仓促了,慢慢来吧。
最后的最后,在健身房混迹了小三年后,虽然没有训练痕迹、还是会被卖课,但是舞蹈的团课我能跟上啦!
知女莫如母——高中的时候就因为别人刷试卷很快,我却因为作业写不完哭唧唧。我妈说,按照自己的节奏就好了,一步一步踏踏实实走,做的题少没关系,做过的就要掌握。进一寸有一寸的惊喜。按着你的步调慢慢来吧,毕竟最后的目标是高考。

看了很多遍快速排序和堆排序之后终于能写了。
快速排序:
import java.util.*;/**quickSortinput:3 2 4 5 1output:[1, 2, 3, 4, 5]*/public class quickSort0330{    public static void main(String[] args){    Scanner scanner = new Scanner(System.in);    String str = scanner.nextLine();    String[] s = str.trim().split(" ");    int n = s.length;    int[] arr = new int[n];    for(int i = 0;i < n;i++){       arr[i] = Integer.parseInt(s[i]);     }     quickSort(arr,0,n - 1);     System.out.println(Arrays.toString(arr));    }    private static void quickSort(int[] arr,int lo,int hi){      if(lo >= hi) return;      int pivot = partition(arr,lo,hi);      quickSort(arr,lo,pivot - 1);      quickSort(arr,pivot + 1,hi);    }    private static int partition(int[] arr,int lo,int hi){      Random random = new Random();      int pivotIndex = random.nextInt(hi - lo + 1) + lo;      int pivotValue = arr[pivotIndex];      swap(arr,pivotIndex,hi);      int savedPosition = hi;      hi--;      while(lo <= hi){        if(arr[lo] > pivotValue){        swap(arr,lo,hi);        hi--;        }else{        lo++;        }      }      swap(arr,lo,savedPosition);      return lo;    }    private static void swap(int[] arr,int i,int j){     int tmp = arr[i];     arr[i] = arr[j];     arr[j] = tmp;    }}
手动分割线

堆排序:
import java.util.*;/*3 2 4 1 5[1, 2, 3, 4, 5]
*/public class heapSort0330{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); String[] s = str.trim().split(" "); int n = s.length; int[] arr = new int[n]; for(int i = 0;i < n;i++){ arr[i] = Integer.parseInt(s[i]); }
heapSort(arr); System.out.println(Arrays.toString(arr)); } private static void heapSort(int[] arr){ int n = arr.length; for(int i = n / 2 - 1;i >= 0;i--){ adjustHeap(arr,i,n); } for(int j = n - 1;j > 0;j--){ swap(arr,0,j); adjustHeap(arr,0,j); } } private static void adjustHeap(int[] arr,int i,int n){ int tmp = arr[i]; for(int k = i * 2 + 1;k < n;k = k * 2 + 1){ if(k + 1 < n && arr[k] < arr[k + 1]){ k++; } if(arr[k] > tmp){ swap(arr,i,k); i = k; } else{ break; } } } private static void swap(int[] arr,int i,int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}

下个月希望能掌握Dijkstra,回溯(n皇后)和动态规划基本模板吧。还有BFS和DFS。