必须掌握的八种排序（5-6）--冒泡排序，快速排序

5、冒泡排序

（1）基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

（2）理解图

（3）代码实现

/**
 * 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，
 * 如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，
 * 也就是说该数列已经排序完成。
 * 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 * 步驟：
 *    1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
      2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
      3、针对所有的元素重复以上的步骤，除了最后一个。
      4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 * @author Administrator
 *
 */
public class bubbleSort {
    public bubbleSort() {
        int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35,
                25, 53, 51 };
        int temp = 0;
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < a.length; i++)
            System.out.println(a[i]);
    }
}

（1）基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

（2）理解图

（3）代码实现

/**
 * 快速排序是其基本思想是基本思想是，通过一趟排序将待排记录分隔成独立的两部分，
 * 其中一部分记录的关键字均比另一部分的关键字小，
 * 则可分别对这两部分记录继续进行排序，以达到整个序列有序。
 * 步驟：
 *   1、从数列中挑出一个元素，称为 "基准"（pivot），
     2、重新排序数列，所有元素比基准值小的摆放在基准前面，
        所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，
        该基准就处于数列的中间位置。这个称为分区（partition）操作。
     3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 * @author Administrator
 *
 */
public class QuickSort {

    public  void sort(){
        int a[] = { 11, 33, 44, 2, 0, 1, 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17,
                18, 23, 34, 15, 35, 25, 53, 51, 90 };

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

    }
    /**
     *
     * @param a  待排序数组
     * @param low  可以看做低位助手
     * @param high 可以看做高位助手
     * 低助手是用来找比基准位大的数
     * 高助手是用来找比基准位小的数   这样就可以看做两个助手在活动
     */
    private  void quickSort(int[] a, int low, int high) {
        int start=low;//起始位置 0；
        int end=high; //结束位置
        int base=a[low]; //基准数 ：一般是第一位
        int tempIndex=low; //找到的符合要求的位置：因为要把它的值付给基准数所在位置 所以要记录该位置 可以看做是助手移动到的位置
        while(low<high){
            //高助手从右向左找一个比基准位小的数 找到后给到低助手当前所在位置
            //没有找到的话 高助手向前移动一位
            while(low<high&&base<=a[high]){
                high--;
            }
            //找到时 把找到的数赋值给低助手所在位置
            a[low]=a[high];
            tempIndex=high;//记录当前助手位置

            //然后低助手从左向右找一个比基准数大的数 ，找到后给到高助手当前所在位置
            //没有找到的话 低助手向后移动一位
            while(low<high&&base>=a[low]){
                low++;
            }
            //找到后赋值给高助手当前所在位置
            a[high]=a[low];
            tempIndex=low;//记录当前助手位置

            //直到循环结束  -->低助手和高助手重叠 就把基准数赋到当前中轴重叠位置
            a[tempIndex]=base;

        }
        //以上第一次排序结束  把数列分成了前后两个部分
        //最后在对上面前后两个部分数列 分别递归
        if(low-start>1){//前部分至少有两个数据
            quickSort(a,0,low-1);
        }
        if(end-high>1){
            quickSort(a,high+1,end);
        }
    }

    public static void main(String[] args) {
        QuickSort q=new QuickSort();
        q.sort();
    }

}