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;
    
    }
}