いくつかのソートアルゴリズムのJava実装

6589 ワード

問題の説明:
ソートint配列
分析:
現在は次のもののみが含まれます.
BubbleSort()
HeapSort()
InsertionSort()
MergeSort()
QuickSort()
ShellSort()
バケツの並べ替えなどが実現しておらず、完備が待たれています
コード実装:
package self.sort;

/**
 * Created by bwhan on 4/28/15.
 */
public class BubbleSort {
    public static void bubblesort(int[] a){
        boolean done = false;
        int size = a.length;
        while(!done){
            done = true;
            for(int i = 0; i < size - 1; i++){
                if(a[i] > a[i+1]){
                    done = false;
                    int tmp = a[i+1];
                    a[i+1] = a[i];
                    a[i] = tmp;
                }
            }
            size--;
        }
    }
}
package self.sort;

/**
 * Created by bwhan on 4/28/15.
 */
public class HeapSort {
    public static void heapsort(int[] a){
        for(int i = a.length/2; i >= 0; i--)
            percDown(a, i, a.length);
        for(int j = a.length - 1; j > 0; j--){
            int tmp = a[0];
            a[0] = a[j];
            a[j] = tmp;
            percDown(a, 0, j);
        }
    }

    static int leftChild(int i){
        return 2*i + 1;
    }

    static void percDown(int[] a, int i, int n){
        int child;
        int tmp;
        for(tmp = a[i]; leftChild(i) < n; i = child){
            child = leftChild(i);
            if(child != n -1 && a[child] < a[child + 1])
                child++;
            if(tmp < a[child])
                a[i] = a[child];
            else
                break;
        }
        a[i] = tmp;
    }
}
package self.sort;

/**
 * Created by bwhan on 4/28/15.
 * Simple insertion sort.
 * O(N^2)
 **/

public class InsertionSort {
    public static void insertionsort(int[] a){
        for(int i = 1; i < a.length; i++){
            int tmp = a[i];
            int j;
            for(j = i;j>0 && tmp < a[j-1];j--){
                    a[j] = a[j-1];
            }
            a[j] = tmp;
        }
    }
}
package self.sort;

/**
 * Created by bwhan on 4/28/15.
 */
public class MergeSort {
    public static void mergesort(int[] a){
        int[] tmp = new int[a.length];
        mergesort(a, tmp, 0, a.length - 1);
    }

    static void mergesort(int[] a, int[] tmp, int left, int right){
        if(left < right){
            int center  = (left+right)/2;
            mergesort(a, tmp, left, center);
            mergesort(a, tmp, center + 1,right);
            merge(a, tmp, left, center + 1, right);
        }
    }

    static void merge(int[] a, int[] tmp, int leftPos, int rightPos, int rightEnd){
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        while(leftPos <= leftEnd && rightPos <= rightEnd){
            if(a[leftPos] <= a[rightPos])
                tmp[tmpPos++] = a[leftPos++];
            else
                tmp[tmpPos++] = a[rightPos++];
        }

        while(leftPos <= leftEnd)
            tmp[tmpPos++] = a[leftPos++];
        while(rightPos <= rightEnd)
            tmp[tmpPos++] = a[rightPos++];

        for(int i = 0; i < numElements; i++, rightEnd--)
            a[rightEnd] = tmp[rightEnd];
    }
}
package self.sort;

import static self.sort.InsertionSort.insertionsort;

/**
 * Created by bwhan on 4/29/15.
 */
public class QuickSort {
    public static void quicksort(int[] a){
        quicksort(a, 0, a.length - 1);
    }

    static final int median3(int[]a , int left, int right){
        int center = (left + right)/2;
        if(a[center] < a[left]){
            int tmp = a[center];
            a[left] = a[center];
            a[center] = tmp;
        }

        if(a[right] < a[left]){
            int tmp = a[right];
            a[right] = a[left];
            a[left] = tmp;
        }

        if(a[right] < a[center]){
            int tmp = a[right];
            a[right] = a[center];
            a[center] = tmp;
        }

        int temp = a[center];
        a[center] = a[right - 1];
        a[right - 1] = temp;

        return a[right - 1];
    }

    static void quicksort(int[] a, int left, int right){
        if(left + 10 < right){
            int pivot = median3(a, left, right);

            int i = left, j = right - 1;
            for(;;){
                while(a[++i] < pivot){}
                while(pivot < a[--j]){}
                if(i < j){
                    int tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                } else
                    break;
            }

            int tmp = a[i];
            a[i] = a[right - 1];
            a[right - 1] = tmp;

            quicksort(a, left, i - 1);
            quicksort(a, i + 1, right);
        }
        else
            insertionsort(a);
    }
}
package self.sort;

/**
 * Created by bwhan on 4/28/15.
 */
public class ShellSort {
    public static void shellsort(int[] a) {
        for(int gap = a.length/2; gap > 0; gap /= 2)
            for(int i = gap; i < a.length; i++){
                int tmp = a[i];
                int j = i;

                for(; j >= gap && tmp < a[j-gap]; j -= gap)
                    a[j] = a[j - gap];
                a[j] = tmp;
            }
    }
}
package self.sort;

import self.tool.PrintData;

import static self.sort.BubbleSort.bubblesort;
import static self.sort.HeapSort.heapsort;
import static self.sort.InsertionSort.insertionsort;
import static self.sort.MergeSort.mergesort;
import static self.sort.QuickSort.quicksort;
import static self.sort.ShellSort.shellsort;

/**
 * Created by bwhan on 4/28/15.
 */
public class SortTest {
    public static void main(String[] args) {
        int[] a = {9,3,4,5,1,6,8,2,12,14,22,18,3,11};
        insertionsort(a);
        PrintData.printarray(a);

        int[] b = {9,3,4,5,1,6,8,2,12,14,22,18,3,11};
        bubblesort(b);
        PrintData.printarray(b);

        int[] c = {9,3,4,5,1,6,8,2,12,14,22,18,3,11};
        shellsort(c);
        PrintData.printarray(c);

        int[] d = {9,3,4,5,1,6,8,2,12,14,22,18,3,11};
        heapsort(d);
        PrintData.printarray(d);

        int[] e = {9,3,4,5,1,6,8,2,12,14,22,18,3,11};
        mergesort(e);
        PrintData.printarray(e);

        int[] f = {9,3,4,5,1,6,8,2,12,14,22,18,3,11};
        quicksort(f);
        PrintData.printarray(f);


    }
}