冒泡排序与快速排序详解

常用排序:冒泡排序与快速排序详解。

在排序算法中，冒泡排序和快速排序可以算是排序算法入门必会的两种排序了，今天和大家来分析一下如何快速理解并掌握这两种排序。首先冒泡排序是初学者最常用的排序，所以我们先来详解下冒泡排序。

1.冒泡排序

冒泡排序，看字面意义就是有大泡泡和小泡泡在水中同时上浮，而大的泡泡就上升的快，小的泡泡就上升的相对较慢，从而产生了一定的速度差，这就产生了大的泡泡在小的泡泡上面，也就是按从一定的大小顺序排好了顺序。当然，这里的比喻和冒泡排序有点不同，冒泡排序是针对数值排序，且算法是有稍微的差别。

这里我们使用大家喜欢的java语言来示范，我们取出20个10以内的数字：

int[] sortInts = new int[20];
for (int i = 0; i < 20; i++) {
    int random = (int) (Math.random() * 10);
    sortInts[i] = random;
}

例如我们得到以下数值：

2、8、6、6、6、9、5、1、9、2、7、3、9、8、9、0、9、2、0、6、

下面要对这些数字进行冒泡排序，我们使用的方法是，两两对比，拿数组第一个数值对比第二个数值并把较大的替换到后面，然后是第一个数值对比第三个数值把较大的替换到后面，然后是第一个数值对比第四个数值把较大的替换到后面，直到对比到最后一个，第一轮对比结束。

第一轮对比结果:

0、8、6、6、6、9、5、2、9、2、7、3、9、8、9、1、9、2、0、6、

不难看出，第一个数值我们已经排序完成了，后面进行第二轮排序，我们拿第二个数值开始对比，第二个数值对比第三个数值并把较大的替换到后面，第二个数值对比第四个数值并把较大的替换到后面，直到对比到最后一个，第二轮对比结束。

第二轮对比结果:

0、0、8、6、6、9、6、5、9、2、7、3、9、8、9、2、9、2、1、6、

后面延续这样的对比最终排序完成。上面是理解层面的解释，下面给出代码实现：

    public static void main(String args[]){
        int[] sortInts = new int[20];
        for (int i = 0; i < 20; i++) {
            int random = (int) (Math.random() * 10);
            sortInts[i] = random;
        }
        printArrays(sortInts);
        bubbleSort(sortInts);
    }

    //冒泡排序
    private static void bubbleSort(int[] integers){
        for(int i = 0; i<integers.length-1; i++){
            for(int j=i; j<integers.length; j++){
                if(integers[i] > integers[j]){
                    int temp = integers[i];
                    integers[i] = integers[j];
                    integers[j] = temp;
                }
            }
        }
        printArrays(integers);
    }
    
    private static void printArrays(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + "、");
        }
    }

冒泡排序结果：

0、0、1、2、2、2、3、5、6、6、6、6、7、8、8、9、9、9、9、9、

 

注:本文来自风马博客原创,如有不对之处请留言指出。

2.快速排序

快速排序是冒泡排序的一种优化，稍微比冒泡排序要难理解一点点，快速排序的优点就是快速，缺点是不稳定。

快速排序的原理：

1.取数组中一个数值作为基数.

2.把大于此基数的换到数组的右侧，小于此基数的换到数组的左侧.

3.对换基数与中间数值的位置

4.重复2操作，直到数值数量为1

不难看出4步骤用到了递归方法，快速排序java实现代码如下：

 public static void main(String args[]){
        int[] sortInts = new int[20];
        for (int i = 0; i < 20; i++) {
            int random = (int) (Math.random() * 10);
            sortInts[i] = random;
        }
        printArrays(sortInts);
        fastSort(sortInts,0,sortInts.length-1);
    }

    //快速排序
    private static void fastSort(int[] integers,int left,int right){

        if(left>right){
            return;
        }

        int base = integers[left];
        int i = left;
        int j = right;
        while(i < j){

            while (integers[j]>=base && i<j){
                j--;
            }

            while (integers[i]<=base && i<j){
                i++;
            }

            int temp = integers[i];
            integers[i] = integers[j];
            integers[j] = temp;
        }

        integers[left] = integers[i];
        integers[i] = base;

        fastSort(integers,left,i-1);
        fastSort(integers,i+1,right);

        printArrays(integers);
    }

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

快速排序输出结果如下：

2、5、0、0、4、6、4、2、5、8、2、5、2、0、8、2、1、8、1、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、5、8、6、8、5、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、5、8、6、8、5、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、5、8、6、8、5、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、5、8、6、8、5、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、4、5、6、8、5、8、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、8、8、8、7、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、8、8、8、7、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、

 

总结：冒泡排序和快速排序为入门排序，需理解后再尝试编写，希望读此博客者有所收获。

本文来自风马博客，Renfr原创，如有不对之处请留言指出。

本文地址：https://blog.csdn.net/Renfr/article/details/107064969