排序算法

// 选择排序   每次扫描找出最小的那个，放到正确的位置。
    public static int [] sort1(int [] data) {
        if(data == null) {
            return null;
        }

        int minIndex = 0;
        for(int i=0; i<data.length; i++) {
            minIndex = i;

            // 找出最小元素的索引
            for(int j=i+1; j<data.length; j++) {
                if(data[j] < data[minIndex]) {
                    minIndex = j;
                }
            }

            // 放到正确的位置
            if(minIndex != i) {
                int temp = data[i];
                data[i] = data[minIndex];
                data[minIndex] = temp;
            }
        }

        return data;
    }

// 冒泡排序   交换相邻的两个素，每一轮都会将最大的放到后面。
    public static int [] sort2(int [] data) {
        if(data == null) {
            return null;
        }

        boolean flag = false;
        for(int i=1; i<=data.length; i++) {
            for(int j=0; j<data.length - i - 1; j++) {
                if(data[j] > data[j+1]) {
                    int temp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = temp;
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }

        return data;
    }

// 插入排序   将新的元素插入到已排好序的列表中。
    public static int [] sort3(int [] data) {
        if(data == null) {
            return null;
        }

        for(int i=1; i<data.length; i++) {
            int temp = data[i];
            int j = i - 1;
            for(; j>=0; j--) {
                if(data[j] > temp) {
                    data[j+1] = data[j];
                } else {
                    break;
                }
            }
            data[j+1] = temp;
        }

        return data;
    }

// 快速排序   使用分治的思想。
    public static int partition(int [] data, int left, int right) {
        int i = left;
        int j = right;
        int temp = data[i];

        while(i < j) {
            while(i < j && data[j] > temp) {
                j--;
            }
            if(i < j) {
                data[i] = data[j];
//                data[j] = temp;
            }

            while(i < j && data[i] < temp) {
                i++;
            }
            if(i < j) {
                data[j] = data[i];
//                data[i] = temp;
            }

        }
        data[i] = temp;

        return i;
    }
    public static int [] sort(int [] data, int left, int right) {
        if(data == null) {
            return null;
        }

        int dp = 0;
        if(left < right) {
            dp = partition(data, left, right);
            sort(data, left, dp - 1);
            sort(data, dp + 1, right);
        }

        return data;
    }