排序 - 天天看点

冒泡排序：

package cn.edu.hdu.chenpi.plib;

import java.util.Arrays;

public class App {

    public static void main(String[] args) {
        Integer[] arr = { 49, 38, 65, 97, 76, 13, 27, 49 };

        for (int i = 0; i < arr.length - 1; i++) {
            //用于提前结束判断
            boolean changeFlag = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    changeFlag = true;
                }
            }
            if (changeFlag == false)
                break;
            System.out.println("第" + (i + 1) + "次:" + Arrays.asList(arr));
        }
        System.out.println(Arrays.asList(arr));
        ;
    }
}

快速排序：

package cn.edu.hdu.chenpi.plib;

public class App {

    public static void main(String[] args) {
        int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49 };
        App.quickSort(arr, 0, arr.length - 1);
        for (int t : arr) {
            System.out.println(t);
        }
    }

    public static int trip(int[] arr, int begin, int end) {
        int c = arr[begin];
        int i = begin, j = end;
        //最后一个空位
        int index = 0;
        while (i < j) {
            //从后往前找
            while (i < j && arr[j] >= c) {
                j--;
            }
            arr[i] = arr[j];
            index = j;
            i++;

            if (i >= j) break;
            
            //从前往后找
            while (i < j && arr[i] <= c) {
                i++;
            }
            arr[j] = arr[i];
            index = i;
            j--;

        }

        arr[index] = c;

        //打印一趟排序后的结果
        for (int t : arr) {
            System.out.print(t + " ");
        }
        System.out.println(index);
        return index;
    }

    public static void quickSort(int[] arr, int begin, int end) {
        if (begin < end) {
            int middle = App.trip(arr, begin, end);

            App.quickSort(arr, begin, middle - 1);
            App.quickSort(arr, middle + 1, end);
        }
    }
}

选择排序：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

插入排序：已排序+未排序两部分，从已排序后面找一个值，插入到已排序，依次下去。。。

希尔排序：

归并排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

堆排序：

　　n个元素的序列{k1，k2，…,kn}当且仅当满足下列关系之一时，称之为堆。

　　情形1：ki <= k2i 且ki <= k2i+1 （最小化堆或小顶堆）

　　情形2：ki >= k2i 且ki >= k2i+1 （最大化堆或大顶堆）

若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。

@Author 风一样的码农

@HomePageUrl http://www.cnblogs.com/chenpi/