排序算法

package com;  
public class Sort {  
    private static int[] list = {7,3,4,1,9,2,8,5,6,0,5};  
    /** 
     * 冒泡排序, O(n^2) 
     */ 
    private static void bubble(){  
        for (int i = 0; i< list.length ; i++){  
            for (int j= 0; j< list.length -i -1; j++){  
                if (list[j] > list[j+1]){  
                    int tmp = list[j];  
                    list[j] = list[j+1];  
                    list[j+1] = tmp;  
                }  
            }  
        }  
    }  
    /** 
     * 简单选择排序, O(n^2) 
     * 将要排序的对象分成两部分，一部分是已排序的，一部分是未排序的，从未排序的部分选择最小的，并放入已排序部分的最后一个 
     */ 
    private static void selection(){  
        for (int i = 0; i< list.length; i++){  
            int position = i;  
            for (int j =i + 1; j< list.length; j++){  
                if (list[position] > list[j]){  
                    position = j;  
                }  
            }  
            int tmp = list[i];  
            list[i] = list[position];  
            list[position] = tmp;  
        }  
          
    }  
    /** 
     * 直接插入排序, O(n^2) 
     * 将数据分为两部分，从后面部分依次取出数据，插入前面部分（插入后的前面这部分有序） 
     */ 
    private static void insertion(){  
        for (int i=1; i<list.length; i++){  
            int j = i -1 ;  
            int tmp = list[i];  
            while(list[j] > tmp){  
                list[j+1] = list[j];  
                j--;  
                if (j<0) break;  
            }  
            list [j+1] = tmp ;  
        }  
    }  
    /** 
     * 快速排序, O(n*log n) 
     * 属于一种优化冒泡排序 
     * 定义一个枢轴，使得在其之前的都小于它之后的都大于等于它，然后按这个法则在枢轴两边递归运算；枢轴一般取第一个元素 
     */ 
    private static void quickSort(int low, int high){  
        if (low < high){  
            int p = partition(low,high);  
            quickSort(low, p-1);  
            quickSort(p+1, high);  
        }  
    }  
    /** 
     * 将序列划分为2个子序列，并返回枢轴元素位置；其中，枢轴元素前的元素都小于枢轴元素，后的都大于枢轴元素 
     */ 
    private static int partition(int low, int high){  
        int pivot = list[low];  
        while(low < high){  
            while(low < high && list[high] >= pivot) high --;  
            list[low] = list[high];  
            while(low < high && list[low] <= pivot) low ++;  
            list[high] = list[low];  
        }  
        list[low] = pivot;  
        return low;  
    }  
    /** 
     * 希尔排序，又称“缩小增量排序”，是改进的直接插入排序方式 
     * 时间复杂度依赖于步长序列，如当步长序列为delta[k]=2^(t-k+1) - 1,时间复杂度O(n^1.5) 
     * 本例，我们选择步长序列为:{5,3,1} 
     */ 
    private static void shell(){  
        int[] step = {5,3,1};  
        for (int i:step)  
            shellInsert(i);  
    }  
    private static void shellInsert(int deltaK){  
        for (int i=deltaK; i<list.length; i++){  
            if (list[i]<list[i-deltaK]){  
                int tmp = list[i];  
                int j = i - deltaK;  
                for (;j>=0 && tmp < list[j]; j-=deltaK ){  
                    list[j + deltaK] = list[j];  
                }  
                list[j+deltaK] = tmp ;  
            }  
        }  
    }  
      
    public static void main(String[] args) {  
        bubble();  
//      selection();  
//      insertion();  
//      quickSort(0, list.length -1);  
//      shell();  
        for (int x:list)  
            System.out.print(x+" ");  
    }  
 
}