排序算法

blueantelope

/**
* Copytright (c) blueantelope, 2008 All rigths reserved.
*  算法研究之用
*/
package org.blueantelope.mysrc.Arithmetic;
/**
*  排序算法
* @author blueantelope
* @version 0.1
* @since 2008-05-13
*/
public class SortClass {
    private static final int[] unSort = {4, 6, 8, 2, 3, 1, 5, 7, 9, 12, 11}; // 未排序内容
   
    /**
     *  复制未排序的数组而得到新的数组
     * @return 未排序的数组
     */
    private static int[] getArray() {
        int[] sort = new int[unSort.length];
        System.arraycopy(unSort, 0, sort, 0, sort.length);
        
        return sort;
    }
   
    /**
     *  交换两个数组元素的位置
     * @param array 需要排序的数组
     * @param m,n 交换的数组下标
     */
    private static void swap(int[] array, int m, int n) {
        int temp = array[m];
        array[m] = array[n];
        array[n] = temp;
    }
   
    /**
     *  冒泡排序
     * @return 排序结果
     */
    public static int[] BubbleSort() {
        int[] sort = getArray();
        int length = sort.length;
        int count = 0;
        
        for (int m=0; mlength; m++) {
            for (int n=(length-1); n>m; n--) {
                if (sort[n]  sort[n-1]) {
                    swap(sort, n, n-1);
                    count++;
                }
            }
        }
        System.out.print("执行了" + count + "次");
        
        return sort;
    }
   
    /**
     *  插入排序
     * @return 排序结果
     */
    public static int[] InsertSort() {
        int[] sort = getArray();
        int length = sort.length;
        int count = 0;
        
        for (int m=1; mlength; m++) {
            for (int n=m; (n>0)&&(sort[n]sort[n-1]); n--) {
                swap(sort, n, n-1);
                count ++;
            }
        }
        System.out.print("执行了" + count + "次");
        
        return sort;
    }
   
    /**
     *  选择排序
     * @return 排序结果
     */
    public static int[] SelectSort() {
        int[] sort = getArray();
        int length = sort.length;
        int count =0;
        
        for (int m=0; mlength; m++) {
            int index = m;
            for (int n=(length-1); n>m; n--) {
                if (sort[n]  sort[index]) {
                    index = n;
                }
            }
            count++;   
            swap(sort, m, index);
        }
        System.out.print("执行了" + count + "次");
        
        return sort;
    }
   
    /**
     *  快速排序, 主程序
     * @return 排序结果
     */
    public static int[] mainQuickSort() {
        int[] sort = getArray();
        int length = sort.length;
        
        QuickSort(sort, 0, length-1);
        
        return sort;
    }
   
    /**
     *  快速排序, 定义pivot中枢为开始位置
     * 分两个区域递归排序, 小于中枢和大于中枢
     * @param sort 排序数组
     * @param first 排序区起始位置
     * @param last 排序区终止位置
     */
    private static void QuickSort(int[] sort, int first, int last) {
        int pivot = 0; // 中枢的位置,可以处定义
        
        if (first  last) {
            pivot = partition(sort, first, last);
            QuickSort(sort, first, pivot-1);
            QuickSort(sort, pivot+1, last);
        }
    }
   
    /**
     *  快速排序, 定义分区
     * @param sort 排序数组
     * @param first 排序区起始位置
     * @param last 排序区终止位置
     * @return 中枢位置
     */
    private static int partition(int[] sort, int first, int last) {
        int pivotValue = sort[first];
        
        int last1 = first;
        for (int m=(first+1); m=last; m++) {
            if (sort[m]  pivotValue) {
                ++last1;
                swap(sort, m, last1);
            }
        }
        swap(sort, last1, first); //改变中枢位置
        
        return last1;
    }
   
    /**
     *  归并排序, 主程序
     * @return 排序结果
     */
    public static int[] mainMergeSort() {
        int[] sort = getArray();
        int length = sort.length;
        
        MergeSort(sort, 0, length-1);
        
        return sort;
    }
   
    /**
     *  归并排序, 两个区域递归找中值后合并两个区域
     * @param sort 排序数组
     * @param frist 排序区起始位置
     * @param last 排序区终止位置
     */
    private static void MergeSort(int[] sort, int first, int last) {
        if (first  last) {
            int mid = (first+last) / 2;
            MergeSort(sort, first, mid);
            MergeSort(sort, mid+1, last);
            Merge(sort, mid, first, last);
        }
    }
   
    /**
     *  归并排序, 合并两个区域, 需增加一个同样大小的临时数组
     * @param sort 排序数组
     * @param mid 排序中间位置
     * @param first 排序区起始位置
     * @param last 排序区终止位置
     */
    private static void Merge(int[] sort, int mid, int first, int last) {
        int[] temp = new int[sort.length];
        
        int first1 = first;
        int last1 = mid;
        int first2 = mid + 1;
        int last2 = last;
        int index = first1;
        
        /**
         *  将数值小的区域放入临时数组前半部份
         */
        while ( (first1 = last1) && (first2 = last2) ) {
            if ( sort[first1]  sort[first2] ) {
                temp[index] = sort[first1];
                first1++;
            } else {
                temp[index] = sort[first2];
                first2++;
            }
            index++;
        }
        
        /**
         *  将数值大的区域放入临时数组前半部份
         */
        while ( first1 = last1 ) {
            temp[index] = sort[first1];
            first1++;
            index++;
        }
        while( first2 = last2 ) {
            temp[index] = sort[first2];
            first2++;
            index++;
        }
        
        /**
         *  将临时数组写回数组中
         */
        for (index=first; index=last; index++) {
            sort[index] = temp[index];
        }
    }
   
    /**
     *  控制台显示数组元素
     * @param sort 需输出的数组
     */
    public void OutputArray(int[] sort) {
        for (int n=0; nsort.length; n++) {
            System.out.printf("%3d", sort[n]);
        }
        System.out.println("");
    }
   
    public static void main(String[] args) {
        System.out.print("冒泡排序: ");
        new SortClass().OutputArray(SortClass.BubbleSort());
        
        System.out.print("插入排序: ");
        new SortClass().OutputArray(SortClass.InsertSort());
        
        System.out.print("选择排序: ");
        new SortClass().OutputArray(SortClass.SelectSort());
        
        System.out.print("快速排序: ");
        new SortClass().OutputArray(SortClass.mainQuickSort());
        
        System.out.print("归并排序: ");
        new SortClass().OutputArray(SortClass.mainMergeSort());
    }
   
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/1816/showart_687011.html