Datawhale 系列数据结构
Task3.1 排序
3.1.1 归并
- // 采用分治 (Divide and Conquer) 的一个非常典型的应用. 将已有序的子序列合并, 得到完全的序列
- public static int [] mergeSort(int []arr){
- int len =arr.length;
- if(len<2){
- return arr;
- }
- int [] left=Arrays.copyOfRange(arr,0,len/2);
- int [] right=Arrays.copyOfRange(arr,len/2,len);
- return merge(mergeSort(left),mergeSort(right));
- }
- public static int [] merge(int [] left,int [] right){
- int llen=left.length;
- int rlen=right.length;
- int[] res=new int[llen+rlen];
- int li=0,ri=0,rei=0;
- while (llen-li>0 && rlen-ri>0) {
- if (left[li] <= right[ri]) {
- res[rei++]=left[li++];
- } else {
- res[rei++]=right[ri++];
- }
- }
- while (llen-li>0) {
- res[rei++]=left[li++];
- }
- while (rlen-ri>0) {
- res[rei++]=right[ri++];
- }
- return res;
- }
3.1.2 快速排序
- /* 快速排序使用分治法来把一个 list 分为两个子 list:
- * 从数列中跳出一个元素, 称为 "基准"(pivot)
- * 重新排序数列, 所有元素比基准小的摆放在基准前面, 所有比基准大的放在基准后面. 在这个分区推出后, 该基准就处于数列的中间位置. 这个称为分区操作.
- * 递归的, 把小于基准值元素的子数列和大于基准值元素的子数列排序
- */
- public static int partition(int []array,int lo,int hi){
- // 固定的切分方式
- int key=array[lo];
- while(lo<hi){
- while(array[hi]>=key&&hi>lo){// 从后半部分向前扫描
- hi--;
- }
- array[lo]=array[hi];
while(array[lo]<=key&&hi>lo){从前半部分向后扫描
- lo++;
- }
- array[hi]=array[lo];
- }
- array[hi]=key;
- return hi;
- }
- public static void sort(int[] array,int lo ,int hi){
- if(lo>=hi){
- return ;
- }
- int index=partition(array,lo,hi);
- sort(array,lo,index-1);
- sort(array,index+1,hi);
- }
3.1.3 插入
- public static int [] insertionSort(int []arr){
- for(int i=0;i<arr.length;i++){
- for(int j=i;j>0;j--){
- if(arr[j]<arr[j-1]){
- int temp=arr[j];
- arr[j]=arr[j-1];
- arr[j-1]=temp;
- }
- }
- }
- return arr;
- }
3.1.4 冒泡
- public static int [] bubbleSort(int [] arr){
- for(int i= 0;i<arr.length-1;i++){
- for(int j=0;j<arr.length-1-i;j++){
- if(arr[j]>arr[j+1]){
- int temp =arr[j];
- arr[j]=arr[j+1];
- arr[j+1]=temp;
- }
- }
- }
- return arr;
- }
3.1.5 选择
- public static int [] selectionSort(int [] arr){
- int min = 0;
- for(int i=0;i<arr.length-1;i++){
- for(int j=i+1;j<arr.length-1;j++){
- min = arr[i];
- if(arr[j]<min){
- min=arr[j];
- arr[j]=arr[i];
- arr[i]=min;
- }
- }
- }
- return arr;
- }
3.1.6 堆排序(选做)
- /* 堆排序分为三个步骤:
- * 创建最大堆
- * 确保最大堆中父节点的值比子节点的值都大
- * 将根节点与最后一个叶子节点比较, 择其大者剔除出堆, 再重复第 2,3 步.
- * 第二步是整个堆排序的关键.
- */
- public static void maxHeapify(int[] array, int heapsize, int i){
- int l = 2*i + 1;
- int r = 2*i + 2;
- int large = i;
- if (l <heapsize && array[i] < array[l]) {
- large = l;
- }else {
- large = i;
- }
- if (r < heapsize && array[large] < array[r]) {
- large = r;
- }
- if (large != i) {
- int temp = array[i];
- array[i] = array[large];
- array[large] = temp;
- // 因为将最大值和父节点交换了位置, 新的子节点并不能保证一定是比它的子节点大
- // 所以需要递归, 确定交换的子节点比它的子节点都大
- // 而没有动的子节点是不需要进行递归的, 因为它的数值没有变, 如果之前满足最大堆条件, 现在就还是满足的
- maxHeapify(array, heapsize, large);
- }
- }
- // 创建堆
- public static void buildMaxHeap(int[] array){
- int heapsize = array.length;
- for (int i = heapsize/2; i>= 0; i--) {
- maxHeapify(array,heapsize,i);
- }
- }
- public static void heapSort(int[] array){
- int heapsize = array.length;
- for (int i = heapsize - 1; i> 0; i--) {
- if (array[i] <array[0]) {
- int temp = array[0];
- array[0] = array[i];
- array[i] = temp;
- heapsize --;
- maxHeapify(array, heapsize, 0);
- }
- }
- }
3.1.8 编程实现 O(n) 时间复杂度内找到一组数据第 K 大元素
- // 采用堆排序的方法
- // 在创建最小堆, 只创建 K 个元素
- public static void maxHeapify(int[] array, int size, int i) {
- int left = 2 * i + 1;
- int right = 2 * i + 2;
- int small = i;
- if (left < size) {
- if (array[small]> array[left]) {
- small = left;
- }
- }
- if (right <size) {
- if (array[small]> array[right]) {
- small = right;
- }
- }
- if (small != i) {
- int temp = array[small];
- array[small] = array[i];
- array[i] = temp;
- maxHeapify(array, size, small);
- }
- }
- public static void buildHeap(int[] array, int size) {
- for (int i = size - 1; i>= 0; i--) {
- maxHeapify(array, size, i);
- }
- }
- public static int findKByHeap(int[] array, int k) {
- buildHeap(array, k);
- for (int i = k + 1; i <array.length; i++) {
- if (array[i]> array[0]) {
- int temp = array[i];
- array[i] = array[0];
- array[0] = temp;
- maxHeapify(array, k, 0);
- }
- }
- return array[0];
- }
TASK3.2 查找
3.2.1 实现一个有序数组的二分查找
- // 默认数组是有序数组
- public static int biSearch(int [] arr, int target){
- int r = arr.length-1;
- int l = 0;
- int mid=r/2;
- while(l<=r){
- mid=(l+r)/2;
- if(arr[mid]==target)
- return mid;
- else if(arr[mid]>target)
- r=mid;
- else
- l=mid;
- }
- return -1;
- }
3.2.2 实现模糊二分查找算法(比如大于等于给定值的第一个元素)
- // 模糊二分查找, 返回大于等于给定值的第一个值的下标
- public static int blurrySearch(int [] arr, int target){
- int r = arr.length-1;
- int l = 0;
- int mid=r/2;
- while(l<=r){
- mid=(l+r)/2;
- if(arr[mid]==target)
- return mid;
- else if(arr[mid]>target)
- r=mid-1;
- else
- l=mid+1;
- }
- return r+1;
- }
- 3.2.3 Sqrt(x)(x 的平方根)
- class Solution {
- public int mySqrt(int x) {
- if(x==1) return 1;
- int min=0;
- int max = x;
- while(max-min>1){
- int m=(max+min)/2;
- if(x/m<m) max=m;
- else min = m;
- }
- return min;
- }
- }
来源: https://yq.aliyun.com/articles/702770