桶排序实现

Question

我想优化我的代码的性能和精细调整的逻辑。

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Collections;
import java.util.Comparator;

/**
 * Created by ShrivasA on 1/30/2015.
 */
/* Take an Element and Apply the following conditions:
    1. The element should not already be there.
    2. The element should have an element which is last element-1 otherwise create a new one.
    3. in case the element is eligible in all the lists add the element in the list which has least number of elements.
 */
public class TeamFormation {

    /**
     * Bucket sort
     * @param array array to be sorted
     * @param bucketCount number of buckets
     * @return array sorted in ascending order
     */
    public static int[] bucketSort(int[] array, int bucketCount) {
        if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
        if (array.length <= 1) return array; //trivially sorted

        int high = array[0];
        int low = array[0];
        for (int i = 1; i < array.length; i++) { //find the range of input elements
            if (array[i] > high) high = array[i];
            if (array[i] < low) low = array[i];
        }
        double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket

        ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) { //initialize buckets
            buckets[i] = new ArrayList();
        }

        for (int i = 0; i < array.length; i++) { //partition the input array
            buckets[(int)((array[i] - low)/interval)].add(array[i]);
        }

        int pointer = 0;
        for (int i = 0; i < buckets.length; i++) {
            Collections.sort(buckets[i]); //mergeSort
            for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
                array[pointer] = buckets[i].get(j);
                pointer++;
            }
        }
        return array;
    }



    public static void main(String[] args) {

        Scanner scanInput = new Scanner(System.in);
        int testCases = scanInput.nextInt();
        //long startTime=0;
        //System.out.println("The Input given is:::"+testCases);
        StringBuilder result = new StringBuilder();
        TeamFormation tm= new TeamFormation();
        try {
               // Thread t1= new Thread();
                //t1.wait(2000);
                while (testCases > 0) {
                //Scanner inputTeam = (new Scanner(System.in));
               // startTime= System.currentTimeMillis();
                Integer lng = scanInput.nextInt();
                if(lng!=0){
                int[] sortArray= new int[lng];
                    long stime=System.currentTimeMillis();
                    for (int i = 0; i < lng; i++) {
                    Integer test = scanInput.nextInt();
                    //System.out.println(test);
                    sortArray[i] = test;
                }
                tm.bucketSort(sortArray,lng);
                //Arrays.sort(sortArray);
                //long etime=System.currentTimeMillis();
                //System.out.println("Time to prepare and sort Array::"+(etime-stime));
                //long stTime = System.currentTimeMillis();
                List<List> lst = new ArrayList<List>(5);
                int len = sortArray.length;
                    //System.out.println("Array Size::::"+len);
                for (int i = 0; i < len; i++) {
                    long test = sortArray[i];
                    if (lst.size() == 0) {
                        List l1 = new ArrayList(5);
                        //if(l1.contains())
                        //l1[i]=test;
                        l1.add(test);
                        lst.add(l1);
                    } else {
                        List<List> temp = new ArrayList<List>(lst);
                        for (List strlist : temp) {
                            if (!strlist.contains(test) && strlist.contains(test - 1)) {
                                strlist.add(test);
                                lst.add(strlist);
                                test = 0;
                            }
                        }
                        //lst.toArray();
                        if (test != 0) {
                            List<Long> l2 = new ArrayList<Long>(5);
                            l2.add(test);
                            lst.add(l2);
                        }
                    }

                    Collections.sort(lst, new Comparator<List>() {
                        public int compare(List a1, List a2) {
                            return a1.size() - a2.size(); // assumes you want smallest to biggest
                        }
                    });
                }
                result.append((lst.get(0)).size() + "\n");
                //long enTime=System.currentTimeMillis();
               // System.out.println("Time taken for second Half process::"+(enTime-stTime));
            }else{
                    result.append(0+"\n");
                }
                testCases--;
            }
        } catch (Exception ex) {
            ex.printStackTrace();
        }
        System.out.println(result);
        //long endTime= System.currentTimeMillis();
        //System.out.println("The total time taken is:::"+(endTime-startTime));
    }

}

Answer 1

注释掉的代码是死代码，应该删除，以提高可读性。

使用正确的缩进将增加可读性。

while (testCases > 0) { Integer lng = scanInput.nextInt(); if(lng!=0){ int[] sortArray= new int[lng]; long stime=System.currentTimeMillis(); for (int i = 0; i < lng; i++) { Integer test = scanInput.nextInt(); sortArray[i] = test; }

看上去很奇怪，看上去很难读

            while (testCases > 0) {
                Integer lng = scanInput.nextInt();
                if(lng!=0){
                    int[] sortArray= new int[lng];
                    long stime=System.currentTimeMillis();
                    for (int i = 0; i < lng; i++) {
                        Integer test = scanInput.nextInt();
                        sortArray[i] = test;
                    }

看上去可读性更强。您的IDE将有某种键盘快捷方式来自动格式化源代码。

您应该始终针对接口编写代码，而不是针对具体的实现编写代码。

ArrayList buckets[] =新ArrayListbucketCount；

应该是

List<Integer> buckets[] = new ArrayList[bucketCount];  

对单行{}语句也使用大括号if语句，可以减少代码出错的可能性。

变量的声明应尽可能接近它们的使用。

双区间=((双)(高-低+1)/bucketCount；//范围单桶ArrayList buckets[] =新的ArrayListbucketCount；for (int i= 0；i< bucketCount；i++) {//初始化桶桶我=新的ArrayList()；} for (int i= 0；i< array.length；i++) {//分区输入数组桶[(Int)((数组我-低)/interval)].add(数组我)；}

应该是

ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; i++) { //initialize buckets
    buckets[i] = new ArrayList();
}

double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
for (int i = 0; i < array.length; i++) { //partition the input array
    buckets[(int)((array[i] - low)/interval)].add(array[i]);
}

你应该让你的变量有喘息的空间。

双区间=((双)(高-低+ 1))/bucketCount；

应该是

double interval = ((double) (high - low + 1)) / bucketCount;