简单排序——冒泡、选择、插入排序Java算法实现和性能分析

详细还是源码吧，以及其中的注释。

 

 

package zieckey.datastructure.study.sort;

import java.util.Date;

public class ArraySortApp
{
    public static void main( String[] args )
    {
        int maxSize = 20000;
        long beginTime, doneTime;

        // 初始化数组

        ArraySortTest ast = new ArraySortTest( maxSize );
        for ( int i = 0; i < maxSize; i++ )
        {
            long n = (long) ( java.lang.Math.random( ) * maxSize );
            ast.insert( n );
        }
        // 冒泡

//        beginTime = new Date( ).getTime( );

//        ast.bubbleSort( );

//        doneTime = new Date( ).getTime( );

//        System.out.println( "冒泡排序花费时间：" + ( doneTime - beginTime ) + "ms" );


        // 选择

//        beginTime = new Date( ).getTime( );

//        ast.selectSort( );

//        doneTime = new Date( ).getTime( );

//        System.out.println( "选择排序花费时间：" + ( doneTime - beginTime ) + "ms" );


        // 插入

        beginTime = new Date( ).getTime( );
        ast.insertSort( );
        doneTime = new Date( ).getTime( );
        System.out.println( "插入排序花费时间：" + ( doneTime - beginTime ) + "ms" );
    }
}

class ArraySortTest
{
    private long[]    longArray;
    private int        nElems;

    public ArraySortTest( int max )
    {
        longArray = new long[max];
        nElems = 0;
    }

    public void insert( long value )
    {
        longArray[nElems] = value;
        nElems++ ;
    }

    public void display()
    {
        for ( int j = 0; j < nElems; j++ )
            System.out.println( longArray[j] );
    }

    /**
     * 冒泡排序
     * 方法：相邻两元素进行比较，如有需要则进行交换， 每完成一次循环就将最大元素排在最后（如从小到大排序），
     *         下一次循环是将其他的数进行类似操作。 性能：比较次数O(n^2),n^2/2 交换次数O(n^2),n^2/4
     */
    public void bubbleSort()
    {
        int in, out;// 内外循环计数

        for ( out = nElems - 1; out > 0; out-- )
        {
            for ( in = 0; in < out; in++ )
            {
                if ( longArray[in] > longArray[in + 1] )
                {
                    swap( in, in + 1 );
                }
            }
        }
    }

    /**
     * 选择排序
     * 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 顺序放在已排好序的数列的最后，
     *         直到全部待排序的数据元素排完。
     *
     * 性能：比较次数O(n^2),n^2/2
     *         交换次数O(n),n
     *         交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。
     *         但是N比较大时，比较所需的CPU时间占主要地位，
     *         所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。
     */
    public void selectSort()
    {
        int out, in;
        int min; // 最小值的编号

        for ( out = 0; out < nElems - 1; out++ )
        {
            min = out;
            for ( in = out + 1; in < nElems; in++ )
                if ( longArray[in] < longArray[min] )
                    min = in;
            swap( out, min );
        }
    }

    /**
     * 插入排序
     * 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,
     *         从而得到一个新的记录数增1的有序表。
     *
     * 性能：比较次数O(n^2),n^2/4
     *         复制次数O(n),n^2/4
     *         比较次数是前两者的一般，而复制所需的CPU时间较交换少，
     *         所以性能上比冒泡排序提高一倍多，而比选择排序也要快。
     */
    public void insertSort()
    {
        int out, in;
        for ( out = 1; out < nElems; out++ )
        {
            long temp = longArray[out];
            in = out;
            while ( in > 0 && longArray[in - 1] >= temp )
            {
                longArray[in] = longArray[in - 1];
                --in;
            }
            longArray[in] = temp;
        }
    }

    public void swap( int one, int two )
    {
        long temp = longArray[one];
        longArray[one] = longArray[two];
        longArray[two] = temp;
    }

}