排序——交换类排序（冒泡排序、快速排序）

1.  交换类排序算法的基本思想:

对待排序记录的关键字两两进行比较，只要发现两个记录为逆序就进行交换，直到没有逆序的记录为止。

如果要将整个记录序列调整力递增序列，那么元素之间是递减关系即为逆序。

冒泡排序和快速排序就是典型的交换类排序算法。

2.  冒泡排序

冒泡排序也叫做相邻比逆法，即在扫描待排序元素序列时，顺次比较相邻两个元素的大小，如果逆序就交换位置。

2.1 排序步骤

• 第 1 趟比较第 1 和第 2 个元素，如果逆序就交换，再依次比较第 2 和第 3 个、第 3 和第 4  ...  若是逆序则交换。经过该趟比较和交换，最大的数必然 “沉到” 最后一个元素。
• 第 2 趟用同样的方法，在前面的 n-1 个记录中，依次进行比较和交换，第 2 大的数“沉到”倒数第 2 个元素中。
• 第 i 趟仍用同样方法，在剩下的 n-i+1 个记录中，依次进行比较和交换，第 i 大的数“沉到”倒数第 i 个记录中。
• 重复此过程，直到 i=n-1 最后趟比较完为止。

【注】若在某一趟冒泡排序过程中，没有发现一个逆序，就可以直接结束整个排序过程。

package com.zth.sort;

import java.util.Arrays;

/**
 * @author 时光·漫步
 * 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args){
        Integer [] array1 = {3,2,5,8,4,7,6,9};
        bubbleSort(array1);

        Double[] array2 = {3.3,2.3,5.3,8.3,4.3,7.3,6.3,9.3};
        bubbleSort(array2);

        System.out.println(Arrays.toString(array1));
        System.out.println(Arrays.toString(array2));

    }

    private static <AnyType extends Comparable<? super AnyType>>
    void bubbleSort (AnyType[] array){
        boolean flag = true;
        AnyType temp;
        // 遍历的趟数
        for (int i = 0; (i < array.length - 1) && flag; i++) {
            flag = false;
            for (int j = 0; j < array.length - i-1; j++) {
                if (array[j].compareTo(array[j+1])>0){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = true;
                }
            }
        }
    }
}

2.2  性能分析

3.  快速排序

快速排序采用分治的策略。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序的基本思想为：从待排序列中任意选择一个元素， 以该元素作为枢纽元，小于枢纽元的元素均移动至该记录之前，反之，大于枢纽元的元素均移动至该记录之后。致使一趟排序之后，记录的无序序列  r[ 1... n ]  将分割成左右两个子序列，然后分别对分割所得两个子序列递归地进行快速排序，以此类推，直至每个子序列中只含一个记录为止。

3.1   枢纽元的选取

1.   选择第一个元素作为枢纽元。若果待排序元素是预排序的或反序的，性能将很差。

2.  随机选取枢纽元。虽然这是一种安全的做法，但随机数的生成开销较大。

3.  三数中值分隔法（常用）。使用左端、右端和中间位置的三个元素的中值作为枢纽元。

3.2  快排过程

（图片来源：https://www.cnblogs.com/MOBIN/p/4681369.html）

package com.zth.sort;

import java.util.Arrays;

public class  MyQuickSort{
    public static void main(String[] args){

        int[] array = {3,2,5,8,4,7,6,9};
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    private static void quickSort (int[] array, int left,int right){

        // i、j 记录本趟排序位置的起始和终止点
        int i = left;
        int j = right;
        int pivot  = array[left];

        while (left < right){
            // 从右往左遍历
            while (left < right && array[right] >= pivot )
                right--;
            // 找到比 pivot 小的元素
            array[left] = array[right];

            // 从左往右遍历
            while (left < right && array[left] <= pivot )
                left++;
            // 找到比 pivot 大的元素
            array[right] = array[left];
        }
        // 填入枢纽值
        array[right] = pivot;
        // 至少包含两个待排元素
        if (right-1 >i) quickSort(array,i,right-1);
        if (right+1 < j) quickSort(array,right+1,j);
    }

}

缺点：  传统基准值的选定时每次参照顺序表的第一个元素作为基准值, 但是如果数组为有序的情况下，会大大降低排序效率，退化成冒泡排序时间复杂度升为O(n^2) 。

优化方案：

• 三数中值分隔法。
• 当待排序序列的长度分割到一定大小后，使用插入排序。对于很小且部分有序的数组，快排不如插排好。

代码实现：

package com.zth.sort;

import java.util.Arrays;

/**
 * @author 时光·漫步
 */
public class QuickSort {
    public static int CUTOFF = 5;   // CUTOFF 一般取 10
    public static void main(String[] args){
        Integer [] array = {3,2,5,8,4,7,6,9};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 快排的驱动程序
     */
    public static <AnyType extends Comparable<? super AnyType>>
    void quickSort( AnyType[] array){
        quickSort(array,0,array.length-1);
    }

    private static <AnyType extends Comparable<? super AnyType>> void
    quickSort (AnyType[] array,int left,int right){

        if (left + CUTOFF < right ){

            // 获取枢纽元的值
            AnyType pivot = median3(array,left ,right);
            /**
             * 如果不加 CUOFF 当只含有两个元素时，通过获取 pivot 已经排序完成
             * 如果继续排序则会越界（从 left 开始向左遍历)
             */
            if (left+1 == right){
                return;
            }
            // 开始分区
            int i = left,j = right-1;

            for(; ;){
                // 因为将 pivot 放在了 right-1 ，所以先从左往右搜索
                // 因为获取 pivot 时已在最左、最有分别放了小于、大于 pivot 的元素，所以不会越界

                while (array[++i].compareTo(pivot) <0 ){}
                while (array[--j].compareTo(pivot) >0 ) {}

                if (i < j){
                    swapReferences(array,i,j);
                }else
                    break;
            }

            // 填回枢纽元
            swapReferences(array,i,right-1);

            if (left < i) quickSort(array,left,i-1);
            if (i < right) quickSort(array,i+1,right);
        }
        else
            insertSort(array,left,right);
    }

    /**
     * return median of left,center and right
     * @return 枢纽元的值
     * 选取枢纽元的同时将三个元素中的最小值放在 array[left] 、最大值放在 array[right]
     */
    private static <AnyType extends Comparable<? super AnyType>> AnyType
    median3 (AnyType[] array,int left,int right){

        int center = (left+right)/2;

        if (array[center].compareTo(array[left]) <0)
            swapReferences(array,left,center);
        if (array[right].compareTo(array[left]) < 0)
            swapReferences(array,left,right);
        if (array[right].compareTo(array[center]) < 0)
            swapReferences(array,right,center);

        // 将枢纽元放在 right - 1
        swapReferences(array,center,right-1);

        return array[right-1];

    }

    private static <AnyType extends Comparable<? super AnyType>>
    void swapReferences(AnyType[] array,int left,int right){
        AnyType temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
    private static <AnyType extends Comparable<? super AnyType>>
    void insertSort(AnyType[] array ,int left,int right){

        AnyType temp;
        int j;

        for (int i = left+1; i <= right; i++) {
            temp = array[i];
            for (j = i-1; j >=left && temp.compareTo(array[j])< 0 ; j--) {
                array[j+1] = array[j];
            }
            array[j+1] = temp;
        }
    }
}

3.3  性能分析