开发者社区> 晓生寒> 正文

数据结构三:排序+二分查找(DataWhale系列)

简介: Datawhale 系列数据结构 Task3.1 排序 3.1.1归并 //采用分治(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全的序列 public static int [] mergeSort(int []arr){ int len =arr.
+关注继续查看

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
InnoDB索引概述,二分查找法,平衡二叉树
索引是应用程序设计和开发的一个重要方面。如果索引太多,应用的性能可能会受到影响;如果索引太少,对查询性能又会产生影响。要找到一个合适的平衡点,这对应用的性能至关重要。 如果知道数据的使用,从一开始就应该在需要处添加索引。
1132 0
Java数据导出(写)Excel文件 解析
  在编程中经常需要使用到表格(报表)的处理主要以Excel表格为主。下面给出用java写入数据到excel表格方法:   1.添加jar文件     java导入导出Excel文件要引入jxl.jar包,最关键的是这套API是纯Java的,并不依赖Windows系统,即使运行在Linux下,它同样能够正确的处理Excel文件。
972 0
Winform中DataGridView绑定IList数据源后的排序的控件
Winform中DataGridView绑定IList数据源后的排序的控件 也是从网上看到的方法,我封装好了 使用方法: 使用方法: IList aaa = new List();aaa = Getr();dataGridView1.
686 0
每日一练(24):在排序数组中查找数字
统计一个数字在排序数组中出现的次数。
15 0
我花10个小时,写出了小白也能看懂的阿里数据中台分析
数据中台被誉为大数据的下一站,由阿里兴起,核心思想是数据共享,2015年阿里提出“大中台,小前台”的策略。2018 年因为“腾讯数据中台论”,中台再度成为了人们谈论的焦点。 2019年,似乎人人都在提数据中台,但却不是所有人都清楚数据中台到底意味着什么。
3922 0
二分查找的平均查找长度详解【转】
来源:http://blog.csdn.net/turne/article/details/50488378 看数据结构书的时候碰上的内容,我自己将它化成关于级数的题,然后自己算的过程,基本就是等比级数和等差级数的混合内容。
2071 0
【数据结构】顺序查找树节点计算思路与遍历详解
【数据结构】顺序查找树节点计算思路与遍历详解
28 0
+关注
晓生寒
大数据开发与数据分析
11
文章
100
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载