java各种排序

Java各种排序

博客分类： 

• Java综合知识

 

Java排序分类为：

 

 * 1.插入排序（直接插入排序、折半插入排序、希尔排序）； 

 * 2.交换排序（冒泡排序、快速排序）； 

 * 3.选择排序（直接选择排序、堆排序）； 

 * 4.归并排序； 

 * 5.基数排序。

 

下面实现代码为：

 

 

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.xiva.baseKnowledge;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


/**
 * 1.插入排序（直接插入排序、折半插入排序、希尔排序）；
 * 2.交换排序（冒泡排序、快速排序）；
 * 3.选择排序（直接选择排序、堆排序）；
 * 4.归并排序；
 * 5.基数排序。
 * @author XIVA
 */
public class SortPractice <T extends Comparable> {

    /**
     * 直接插入排序
     * @Description 在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
            好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
            也是排好顺序的。如此反复循环，直到全部排好顺序
     * @param  array needing to sort
     * @param  direction of sorting, 0 represent desc, 1 represent asc, others don't sorting.
     */
    public void directInsertSort(T[] array, int direction){

        //升序
        if( direction == 1){
            for(int i=0; i< array.length; i++){
                for(int j=0; j< i; j ++){
                    if( array[i].compareTo(array[j]) < 0 ){
                        T temp = array[i];
                        //后移一位
                        for( int k = i; k > j; k--){
                            array[k] = array[k-1];
                        }
                         array[j] = temp;
                        break;
                    }
                }
            }
        }

        //降序
        if( direction == 0){
            for( int i=0; i< array.length; i++ ){
                for(int j=0; j< i; j ++){
                    if( array[i].compareTo(array[j]) > 0 ){
                        T temp = array[i];
                        //后移一位
                        for( int k = i; k > j; k--){
                            array[k] = array[k-1];
                        }
                        array[j] = temp;
                        break;
                    }
                }
            }
        }

    }


    /**
     * 折半插入排序
     * 当第i个数插入时，前面i-i个数都已经排好序了，我们没有必要从第一个数开始比较大小；
     * 我们可以从第(i-i)/2个数开始比较大小，
     * @param array
     * @param direction
     */
    public void binaryInsertSort(T[] array, int direction){

        int index, position, low, high = 0;
        T temp;
        //升序
        if( direction == 1){
            for(int i = 1; i< array.length; i++){
                low  = 0;
                high = i - 1;
                temp = array[i];
                while(low <= high){
                    index = (low + high) >> 1;
                    if( array[i].compareTo(array[index]) > 0 ){
                        low  = index + 1;
                    }else if( array[i].compareTo(array[index]) < 0 ){
                        high = index - 1;
                    }else{
                        break;
                    }
                }
                position = i;
                while(position > low){
                    array[position] = array[position-1];
                    position--;
                }
                array[low] = temp;
            }
        }

    }

    /**
     * 希尔排序
     * 先取一个正整数d1小于n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序;
     * 然后取d2小于d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止
     * @Description
     * @param array 需要排序数组
     * @param direction 0 desc,1 asc;
     */
    public void shellSort(T[] array, int direction){

        int len = array.length;
        int jump = len;
        T temp;
        while( jump > 1){
            jump = jump >> 1;
            for(int i = 0; i < jump; i++){
                //下面属于直接插入排序
                for( int j = i; j < len; j = j + jump){
                    for(int k = i; k < j; k = k + jump){
                       if( direction == 1 ){
                           if( array[j].compareTo(array[k]) < 0 ){
                                temp = array[k];
                                array[k] = array[j];
                                array[j] = temp;
                           }
                       }
                       else{
                           if( array[j].compareTo(array[k]) > 0 ){
                                temp = array[k];
                                array[k] = array[j];
                                array[j] = temp;
                            }
                       }
                    }
                }
            }
        }
    }

    /**
     * 冒泡排序
     *  依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。
     *  然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。
     *  至此第一趟结束，将最大的数放到了最后。
     *  在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），
     *  将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），
     *  第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。
     *  如此下去，重复以上过程，直至最终完成排序。
     * @param array
     * @param direction
     */
    public void bubbleSort( T[] array, int direction ){

        int len = array.length;
        T temp;

            for( int i=0; i < len; i++ ){
                for(int j = i; j < len - 1; j++ ){
                    if ( direction == 1 ){
                        if( array[i].compareTo(array[j + 1]) > 0){
                            temp = array[i];
                            array[i] = array[j + 1];
                            array[j + 1] = temp;
                        }
                    }else if( direction == 0 ){
                        if( array[i].compareTo(array[j + 1]) < 0){
                            temp = array[i];
                            array[i] = array[j + 1];
                            array[j + 1] = temp;
                        }
                    }
                }
            }
    }

    /**
     * 快速排序
     * @Description 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
     * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
     * @param array
     * @param direction , int i,  int j, int direction
     */
    public void quickSort( T[] array, int start, int end ){

        int keyIndex  = start;
        int compIndex = end;
        T temp;
        if( end <= start){
            return;
        }
        while(true){
            if( compIndex  == keyIndex ){
                break;
            }
            if( array[keyIndex].compareTo(array[compIndex] ) > 0 ){
                if( keyIndex < compIndex ){
                    temp = array[keyIndex];
                    array[keyIndex] = array[compIndex];
                    array[compIndex] = temp;
                    //交换keyIndex与compIndex的值
                    keyIndex = keyIndex + compIndex;
                    compIndex = keyIndex - compIndex + 1;
                    keyIndex = keyIndex - compIndex + 1;
                }else{
                    compIndex = compIndex + 1;
                }
            }else if( array[keyIndex].compareTo(array[compIndex]) < 0 ){
                if( keyIndex > compIndex ){
                    temp = array[keyIndex];
                    array[ keyIndex ] = array[ compIndex ];
                    array[ compIndex] = temp;
                    //交换keyIndex与compIndex的值
                    keyIndex = keyIndex + compIndex;
                    compIndex = keyIndex - compIndex - 1;
                    keyIndex = keyIndex - compIndex - 1;
                }else{
                    compIndex = compIndex - 1;
                }
            }else{
                if( keyIndex < compIndex ){
                    //交换keyIndex与compIndex的值
                    keyIndex = keyIndex + compIndex;
                    compIndex = keyIndex - compIndex + 1;
                    keyIndex = keyIndex - compIndex + 1;
                }else{
                    //交换keyIndex与compIndex的值
                    keyIndex = keyIndex + compIndex;
                    compIndex = keyIndex - compIndex - 1;
                    keyIndex = keyIndex - compIndex - 1;
                }
            }
        }

        //递归
        quickSort(array, start, keyIndex - 1 );
        quickSort(array, keyIndex + 1, end );
    }


    /**
     * @Description 直接选择排序
     *  和冒泡排序类似，莫要混淆了
     * 第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R{1}~R[n-1]中选取最小值，与R[1]交换，....，
     * 第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换,
     * 总共通过n-1次,得到一个按排序码从小到大排列的有序序列.
     * 冒泡排序每一次比较都有可能交换值；这个需要记住每一趟最大值或者最小值的位置
     * @param array
     * @param direction
     */
    public void straightSelectSort(T[] array, int direction){

        int len = array.length;
        T mTempData;
        int change_index;
        for( int i = 0; i < len; i++ ){
            mTempData = array[i];
            change_index = i;
            for( int j = i; j < len; j++ ){
                if( mTempData.compareTo(array[j]) > 0){
                    mTempData = array[j];
                    change_index = j;//记住最大值的位置
                }
            }
            array[change_index] = array[i];
            array[i] = mTempData;
        }

    }


    /**
     * 最大堆
     * @param array
     * @param i
     */
    public void maxHeapify( T[] array, int i){

        int left = 2*i+1;
        int right = 2*i+2;
        int max = i;

        //先判断左子节点
        if( left < array.length && array[max].compareTo(array[left]) < 0 ){
            max = left;
        }

        //需要确定右子节点是否存在
        if( right < array.length && array[max].compareTo(array[right]) < 0 ){
            max = right;
        }

        if( max != i ){
            //System.out.println("swap");
            T tmp = array[max];
            array[max] = array[i];
            array[i] = tmp;
            maxHeapify(array, max);
        }
    }


    /**
     * 最小堆
     * @param array
     * @param i
     */
    public void minHeapify( T[] array, int i){

        int left = 2*i+1;
        int right = 2*i+2;
        int max = i;

        //先判断左子节点
        if(  left < array.length && array[max].compareTo(array[left]) > 0 ){
            max = left;
        }

        //需要确定右子节点是否存在
        if( right < array.length && array[max].compareTo(array[right]) > 0 ){
            max = right;
        }

        if( max != i ){
            //System.out.println("swap");
            T tmp = array[max];
            array[max] = array[i];
            array[i] = tmp;
            minHeapify(array, max);
        }
    }



    /**
     * 创建堆
     * 堆从逻辑上讲是一种非线性结构，但实际中我们使用线性结构来存储；堆首先是一个完全二叉树，根节点的值是最大值(最小值)
     * @param array
     */
    public void createHeap( T[] array ){

        int len = (array.length-1)/2;

        for ( int i = len; i >= 0; i-- ){
            //maxHeapify(array, i);
            minHeapify(array, i);
        }
    }

    /**
     * 堆排序
     *
     * @param array
     * @param direction
     */
    public T[] heapSort(T[] array,T[] result, int direction){

        int index = 0;
        int len = array.length;
        //取出堆顶,重复建堆
        for ( int i = len-1; i >= 0; i-- ){
            result[index] = array[0];
            index++;
            array[0] = array[array.length-1];
            array = Arrays.copyOfRange(array, 0, i);
            minHeapify(array, 0);
            //maxHeapify(array, 0);
        }
        return result;
    }

    public void merge ( T[] array, int low, int mid, int high){
        //T[] tempArr = new Object<T>[high - low];
        List<T> tempList = new LinkedList<T>();
        int s1 = low;
        int s2 = mid + 1;
        while( s1 <= mid && s2 <= high ){
            if( array[s1].compareTo(array[s2]) <= 0){
                tempList.add(array[s1++]);
            }else{
                tempList.add(array[s2++]);
            }
        }

        if(s1 <= mid){
            for(int i=s1; i <= mid; i++){
                tempList.add(array[i]);
            }
        }

        if(s2 <= high){
            for(int i=s2; i <= high; i++){
                tempList.add(array[i]);
            }
        }

        Object[] arrayList =  tempList.toArray();
        System.out.println(Arrays.toString(arrayList) + low + ":" + high);
        for (int i=0;i<arrayList.length;i++){
            array[low + i] = (T)arrayList[i];
        }
        tempList.clear();
    }

    /**
     * 归并排序
     * @param array
     * @param low
     * @param high
     */
    public void mergeSort( T[] array,int low, int high){
        //int len = array.length;
        if (low < high){
            mergeSort(array, low, (low + high)/2);
            mergeSort(array, (low + high)/2 + 1, high);
            merge(array, low, (low + high)/2, high);
        }

    }

    public static void main(String[] args){

        SortPractice sort = new SortPractice();

        Integer num01 = new Integer(12);
        Integer num02 = new Integer(13);
        Integer num03 = new Integer(44);
        Integer num04 = new Integer(3);
        Integer num05 = new Integer(13);
        Integer num06 = new Integer(5);
        Integer num07 = new Integer(7);

        Integer[] array = {num01, num02, num03, num04, num05, num06, num07, num04};
        //Integer[] result = new Integer[array.length];
        //sort.directInsertSort(array, 1);
        //sort.binaryInsertSort(array, 1);
        //sort.shellSort(array, 1);
        System.out.println(Arrays.toString(array));
        sort.mergeSort(array, 0, array.length - 1);
        //sort.bubbleSort(array, 1);
        //sort.quickSort(array, 0, array.length - 1);
        //sort.createHeap(array);
        System.out.println(Arrays.toString(array));
        //sort.heapSort(array, result, 1);
        //System.out.println(Arrays.toString(result));
        /*for( int i=0; i < array.length; i++ ){
            System.out.println( array[i] );
        }*/

    }
}

 还有基数排序未实现。