プログラマーが知っておくべき8大経典の内部ソート---java版

package paixu;

public class paixu {

    public static void main(String[] args) {
        sort qs = new sort();
        int i[] = { 49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51 };
        qs.quiteSort(i, 0, i.length - 1);
//      qs.bubblesort(i);
//      int[] spans = {5,3,1};
//      qs.shellSort(i, spans);
//      qs.insertSort(i);
//      qs.selectSort(i);
//      qs.heapSort(i);
//      qs.mergeSort(i, 0, i.length - 1);
//      qs.radixSort(i, 10);
        for (int data : i) {
            System.out.print(data + " ");
        }
    }
}
/*       8     
 *     ：    &  
 *     ：    & 
 *     ：  &  
 *     
 *     
 */
class sort {
    /*     
     *      ，
     *       ，     ，
     *                 */
    public void quiteSort(int data[], int low, int hight) {
        if (low < hight) {
            int pivotpos = partition(data, low, hight);
            quiteSort(data, low, pivotpos - 1);
            quiteSort(data, pivotpos + 1, hight);
        }
    }
    private int partition(int[] data, int low, int high) {//      low     
        int pivot = data[low];
        while (low < high) {
            while (low < high && pivot <= data[high]) {//      povite ，     ，    
                high--;
            }
            data[low] = data[high];
            while (low < high && data[low] <= pivot) { //        povite ，    ，    
                low++;
            }
            data[high] = data[low];
        }
        data[low] = pivot;
        return low;
    }
    
    /*     
     *     ,        ,
     *             。
     *    , ;   , */
    public void bubblesort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            boolean exchange = false;
            for (int j = 0; j < data.length - i; j++) {
                if (data[j] > data[j + 1]) { //   
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    exchange = true;
                }
            }
            if (!exchange)
                break;
        }
    }
    
    /*     
     *       ，
     *        ：5，3，1，
     *      ：     1，      */
    public void shellSort(int[] data, int[] spans) {
        for (int i = 0; i < spans.length; i++) { //       
            int span = spans[i];
            for (int j = 0; j < span; j++) {//     
                for (int k = j + span; k < data.length; k = k + span) { //     
                    int temp = data[k];
                    int pre = k - span;
                    while (pre >= 0 && data[pre] > temp) {
                        data[pre + span] = data[pre];
                        pre = pre - span;
                    }// end while
                    data[pre + span] = temp;
                }// end for
            }
        }// end for
    }// end shellSort

    /*       
     *        ，
     *              */
    public void insertSort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int tmp = data[i];
            if (tmp < data[i - 1]) {
                int j = i - 1;
                for (; j >= 0 && data[j] > tmp; j--) {
                    data[j + 1] = data[j];
                }
                data[j + 1] = tmp;
            }
        }
    }

    /*       
     *                 ，
     *               */
    public void selectSort(int[] data) {//          
        for (int i = 0; i < data.length; i++) {
            int k = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[k] > (data[j])) {
                    k = j; //        
                }
            }
            if (k != i) {
                int temp = data[i];
                data[i] = data[k];
                data[k] = temp;
            }
        }
    }

    /*    
     *          ，
     *         ，
     *          ，
     *     ，
     *     */
    public void heapSort(int[] data) {
        buildHeap(data);
        for (int i = data.length - 1; i > 0; i--) {
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            heapify(data, 0, i - 1);
        }
    }
    private void buildHeap(int[] data) {
        for (int i = data.length / 2; i >= 0; i--) {
            heapify(data, i, data.length - 1);
        }
    }
    private void heapify(int[] data, int low, int high) {
        int temp = data[low];
        for (int large = 2 * low + 1; large <= high; large *= 2) {
            if (large < high && data[large] < data[large + 1]) {
                large++;
            }
            if (temp >= data[large]) {
                break;
            }
            data[low] = data[large];
            low = large;
        }
        data[low] = temp;
    }

    /*     
     *               ，
     *                   */
    public void mergeSort(int[] data, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2; //       
            mergeSort(data, left, center); //          
            mergeSort(data, center + 1, right); //          
            merge(data, left, center, right); //   
        }
    }
    private void merge(int[] data, int left, int center, int right) {
        int[] tmpArr = new int[data.length];
        int mid = center + 1;
        int index = left; // index         
        int tmp = left;
        while (left <= center && mid <= right) { //                  
            tmpArr[index++] = (data[left] <= data[mid]) ? data[left++] : data[mid++];
        }
        while (mid <= right) { //             
            tmpArr[index++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[index++] = data[left++];
        }
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }

    /*     
     *                  ，
     *          ，
     *         */
    public void radixSort(int[] data, int d) {//d=10^(n-1),n        
        int k = 0;
        int n = 1;

        int[][] temp = new int[data.length][data.length];
        int[] order = new int[data.length];

        while (n <= d) {
            for (int i = 0; i < data.length; i++) {
                int lsd = ((data[i] / n) % 10);
                temp[lsd][order[lsd]] = data[i];
                order[lsd]++;
            }

            for (int i = 0; i < data.length; i++) {
                if (order[i] != 0) {
                    for (int j = 0; j < order[i]; j++) {
                        data[k] = temp[i][j];
                        k++;
                    }
                    order[i] = 0;        //  
                }
            }
            n *= 10;    //        
            k = 0;        //  
        }
    }
}