数据结构(三)

1.桶排序

标题内容

桶排序思路:
先寻找一个数组的最大值max,之后设置一个大小为max+1的数组,即可以存下max的数组,之后遍历数组,
新数组下标和它相同的把数值+1(初始值为0),之后遍历新数组把值不为0的输出

注意:数组不能有负数,因为没有索引是负数的。建议value:0~200

public class BucketSort {
    public static void main(String[] args){
        int [] arr = {1,2,2,3,5,4};
        bucketSort(arr);
        for(int i : arr)
            System.out.print(i+",");

    }

    public static void bucketSort(int [] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        int max = Integer.MIN_VALUE;//将max定义为整型最小值,方便交换
        for(int i = 0;i< arr.length;i++){//找出数组的最大值 if(arr[i] > max){
                max = arr[i];
            }
        }
        int bucket [] = new int[max+1];//设置一个从0到max的数组
        for(int i = 0;i < arr.length;i++){//将旧数组和新数组的下标联系起来
            bucket[arr[i]]++;
        }
        int j = 0;
        for(int i = 0;i< bucket.length;i++){//遍历新数组值不为0的数,把数组重新输出 while(bucket[i]-- > 0)
                arr[j++] = i;
        }


    }
}

2.荷兰国旗问题

标题内容

荷兰国旗问题:
给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放在数组的中间,
大于num的数放在数组的 右边。要求额外空间复杂度O(1),时间复杂度O(N)。类似于快排
import java.util.Scanner;

public class NederlandFlag {
    public static void main(String[] args) {
        int arr[] = {};
        Scanner sca = new Scanner(System.in);
        int num = sca.nextInt();
        partition(arr, num);
        for (int i : arr) {
            System.out.print(i + ",");
        }

    }

    public static void partition(int[] arr, int num) {
        int less = -1;
        int more = arr.length - 1;
        int l = 0;
        while (l <= more) {//边界值 if (arr[l] > num) {
                swap(arr, l, more--);//more也要参与交换
            } else if (arr[l] < num) {
                swap(arr, ++less, l++);
            } else {
                l++;
            }
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注