排序算法（六）

浏览数：75 / 时间：2015年06月08日

1. 交换排序—冒泡排序（Bubble Sort）

基本思想：

排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的俩个数依次进行比较

和调整，让较大的数下沉，较小的数往上冒。即：每当俩相邻的数比较后发现他们的排序与排序的要求相反时，就将他们交换。

冒泡排序示例：

算法的实现：

public class BubbleSort2 {

    public static void main(String[] args) {
        int[] a = {12,43,65,72,87,21,98,21,911,679,22,4,1,8,2456,32};
        bubbleSort(a,a.length);
        
        for(int i=0; i<a.length; i++){
            System.out.print(a[i]+" ");
        }
    }
    public static void bubbleSort(int[] a,int n){
        int temp;
        for(int i=0; i<n-1; i++){
            for(int j=0; j<n-1-i; j++){
                if(a[j] > a[j+1]){
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }
}

冒泡排序算法的改进：

对冒泡排序的改进是加入一标志性变量exchange,用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时，并没有数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程，本文提供一下俩种改进算法：

1、设置一标志性变量pos，用于记录每一趟排序过程中最后一交换数据的位置。由于pos位置之后的数据已经按要求排列好了，所以下一趟排序的时候只需要扫描到pos位置即可。

改进后算法如下：

public class BubbleSort3 {

    public static void main(String[] args) {
        int[] a = { 12, 43, 65, 72, 87, 21, 98, 21, 911, 679, 22, 4, 1, 8,
                2456, 32 };
        bubbleSort(a, a.length);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void bubbleSort(int[] a, int n) {
        int i = n - 1; // 初始时，最后位置保持不变
        while (i > 0) {
            int pos = 0; // 每趟开始时，无记录交换
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    pos = j; // 记录交换的位置
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }

            }
            i = pos;// 为下一趟排序作准备
        }
    }
}

2、传统冒泡排序每一趟冒泡排序只能找到一个最大值或者最小值，我们考虑利用在每趟排序中进行正向和反向俩遍的冒泡方法一次可以得到俩个值（最大值和最小值），从而使排序趟数几乎减少一半。

改进后的算法为：

public class BubbleSort4 {

    public static void main(String[] args) {
        int[] a = { 12, 43, 65, 72, 87, 21, 98, 21, 911, 679, 22, 4, 1, 8,
                2456, 32 };
        bubbleSort(a, a.length);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void bubbleSort(int[] a, int n) {
        int low = 0;
        int high = n - 1;
        int temp, j;
        while (low < high) {
            for (j = low; j < high; ++j) { // 正向冒泡，找到最大值
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }

            }
            --high;// 修改high值, 前移一位
            for (j = high; j > low; --j) {// 反向冒泡,找到最小者
                if (a[j] < a[j - 1]) {
                    temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }

            }
            ++low;// 修改low值,后移一位
        }
    }
}