µ¥Á´±í°æÍ°ÅÅÐò

public class BucketSort implements AscSortInterface {

    @Override
    public int[] sortAsc(int[] arr) {
        if (null == arr || arr.length <= 1){
            return arr;
        }

        // how many buckets
        int minVal = Arrays.stream(arr).min().getAsInt();
        int maxVal = Arrays.stream(arr).max().getAsInt();
        int bucketSize = 100;
        int bucketCount = (maxVal - minVal) / bucketSize + 1;
        MyLinkedList[] buckets = new MyLinkedList[bucketCount];

        // fill buckets
        for (int val : arr) {
            int bucketIndex = (val - minVal) / bucketSize;
            appendToBucket(buckets, bucketIndex, val);
        }

        // sort buckets
        for (int i = 0; i < buckets.length; i++) {
            MyLinkedList bucket = buckets[i];
            if (bucket == null) {
                continue;
            }

            buckets[i] = MyLinkedListUtil.sortLinkedListAsc(bucket);
        }

        // collect
        int index = 0;
        for (MyLinkedList bucket : buckets) {
            if (bucket == null) {
                continue;
            }

            ListNode node = bucket.getFirst();
            do {
                arr[index++] = node.getData();
                node = node.getNext();
            }while (node != null);
        }

        return arr;
    }

    private void appendToBucket(MyLinkedList[] buckets, int bucketIndex, int val) {
        MyLinkedList bucket = buckets[bucketIndex];
        if (bucket == null) {
            buckets[bucketIndex] = new MyLinkedList();
        }

        buckets[bucketIndex].append(new ListNode(val));
    }
}

public class MyLinkedListUtil {
    public static MyLinkedList sortLinkedListAsc(MyLinkedList list) {
        if (list.getFirst() == null) {
            return list;
        }

        MyLinkedList resultList = new MyLinkedList();
        ListNode listNode = sortLinkedListAsc(list.getFirst());
        resultList.append(listNode);
        return resultList;
    }

    private static ListNode sortLinkedListAsc(ListNode head) {
        // length
        int len = 0;
        ListNode nodeTmp = head;
        while (nodeTmp != null){
            len++;
            nodeTmp = nodeTmp.getNext();
        }

        // bubble
        for (int i = 0; i < len; i++) {
            int innnerStopCount = len - i;
            ListNode pre = null;
            ListNode cur = head;
            while (innnerStopCount >= 0 && cur != null){
                ListNode next = cur.getNext();
                if (next == null){
                    break;
                }else {
                    if (next.getData() < cur.getData()){
                        if (pre == null){
                            // cur is head, switch cur and next then next as head
                            cur.setNext(next.getNext());
                            next.setNext(cur);
                            head = next;
                        }else{
                            // switch cur and next
                            pre.setNext(next);
                            cur.setNext(next.getNext());
                            next.setNext(cur);
                        }
                        pre = next;
                        // cur remains
                    }else{
                        pre = cur;
                        cur = next;
                    }

                }
            }
        }

        return head;
    }
}