温故而知新---总结常用排序算法（持续更新）

冒泡排序

基本思想：

大的数一点一点推到后面，最终形成排序

代码：

/**
 * 冒泡排序
 * @author wxh
 * @version 1.0
 *
 */
public class Demo1 {

    public static void main(String[] args) {

        int[] data = {9,2,7,19,100,97,63,208,55,78};
        int[] b = bubbleSort( data );
        System.out.println( Arrays.toString( b ) );

    }
    
    public static int[] bubbleSort( int[] data ) {
        int temp = 0;
        int n = data.length;
        for( int i = 0; i < n; i++ ) {
            for( int j = i + 1; j < n; j++ ) {
                if( data[i] > data[j] ) {
                    temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                }
            }
        }
        return data;
    }
    
}

选择排序

基本思想：

每一次遍历都找出最小值，然后把这个值放到前面（跟冒泡相反，冒泡是找出最大值然后放到后面）

代码：

/**
 * 选择排序
 * @author wxh
 * @version 1.0
 *
 */
public class Demo2 {
    
    public static void main(String[] args) {
        
        int[] data = {9,2,7,19,100,97,63,208,55,78};
        int[] d = sort( data );
        System.out.println( Arrays.toString( d ) );
        
    }

    private static int[] sort( int[] data ) {
        
        int temp = 0;
        for( int i = 0; i < data.length; i++ ) {
            int min = i; 
            for( int j = i + 1; j < data.length; j++ ) {
                if( data[j] < data[min] ) {  //如果有小于当前最小值的数值
                    min = j; //将此关键字的下标赋值给min
                }
            }
            if( min != i ) {
                temp = data[i];
                data[i] = data[min];
                data[min] = temp;
            }
        }
        return data;
    }
    
}

插入排序

基本思想：

就是把当前未排序的元素插入到一个新的排序列表中。 一个非常形象的例子就是右手抓取一张扑克牌，并把它插入左手拿着的排好序的扑克里面。插入排序的最坏运行时间是O(n2)。特点是简单，不需要额外的存储空间，在元素少的时候工作得好。

代码：

/**
 * 插入排序
 * @author wxh
 * @version 1.0
 *
 */
public class Demo3 {
    
    public static void main(String[] args) {
        
        int[] data = {9,2,7,19,100,97,63,208,55,78};
        int[] d = sort( data );
        System.out.println( Arrays.toString( d ) );
        
    }

    private static int[] sort( int[] data ) {
        int n = data.length;
        for( int i = 1; i < n; i++ ) { 
            int flag = i; //要比较的位置
            for( int j = i - 1; j >= 0; j-- ) {
                if( data[j] > data[flag] ) { 
                    int temp = data[j];
                    data[j] = data[flag];
                    data[flag] = temp;
                    flag--; //继续向前比较
                }
            }
        }
        
        return data;
    }
    
}

快速排序

基本思想：

代码：

/**
 * 快速排序
 * @author wxh
 * @version 1.0
 * 
 */
public class Demo4 {
    
    private static final int[] data = {9,2,7,19,100,97,63,208,55,78};
    
    public static void main(String[] args) {
        int[] d = sort( 0, data.length-1 );//传入数组第一个元素和最后一个元素
        System.out.println( Arrays.toString( d ) );    
    }
    
    public static int[] sort( int low, int high ) {
        if ( low < high ) {  
            int result = partition( low, high );  
            sort( low, result - 1 );  
            sort( result + 1, high );  
        }  
        return data;  
    }

    private static int partition( int low, int high ) {  
        int key = data[low];  
        while ( low < high ) {  
            while ( low < high && data[high] >= key )  
                high--;  
            data[low] = data[high];  
            while ( low < high && data[low] <= key )  
                low++;  
            data[high] = data[low];  
        }  
        data[low] = key;  
        return low;  
    }  
    
}

归并排序

基本思想：

代码：