算法入门教程-快速排序

上节我们学习了希尔排序,最后发现是希尔排序最原始的思想还是利用了插入排序,只不过是对它进行了优化,在上篇文章的最后,我们比较了插入法和移位法算法的执行时间,可以看得出天壤之别,今天我们来学习下另外一种算法叫快速排序.

快速排序介绍

快速排序是对冒泡排序的一种改进,其基本的思想是:通过一趟排序对将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分都要小,然后在按此方法对这两部分数据分别进行快速排序,在整个的排序过程中可以采用递归的方式进行,来达到整个数据为有序的.

上述的理论性的东西大家有个大概的理解即可,我们接下来采用图解的方式来完成对它的讲解,首先来看如图所示:

快速排序图解示意图.png

针对上图的过程我们来分析下,假设我有一组无序列表[-9,78,0,23,-567,70],具体的过程如下:

• 首先我们这里假设以0作为基准
• 第一步:从0的左边找到大于0的数,同样的方式在右边找到小于0 的数
• 然后进行两者位置的交换,此刻左右两边是不保证有序性
• 第二步:左边无序列表我们进行递归处理并要保证有序性(从小到大).
• 第三步:右边无序列表我们进行递归处理并要保证有序性(从小到大).
• 最后直到整个列表保证有序性结束我们的算法

看完了图解过程,我们通过代码的方式来实现该算法

代码实现

同样我们就采用上述的无序列表[-9,78,0,23,-567,70]来实现,具体代码如下:

 /**
 *
 * @param arr 待排序的数组
 * @param leftIndex 左索引
 * @param rightIndex 右索引
 */
public static void quickSort(int[] arr,int leftIndex,int rightIndex){
    //定义临时变量来存储我们的索引(数组的下标)
    int lIndex = leftIndex;
    int rIndex = rightIndex;
    //定义一个变量用来存储中间值
    int middleVal = arr[(leftIndex + rightIndex)/2];
    //定义一个临时的变量来存储要交换的值
    int temp = 0;
    //说明:
    //当前这个while循环的目的是我们来找到比middleVal小的值放在它的右边
    //同样找到比middleVal大的值放在它的右边
    //注意:这里采用递归的方式去寻找
    while (lIndex < rIndex){
        //这个while循环的目的是从左边找比middleVal大的值
        while (arr[lIndex] < middleVal){
            lIndex +=1; //从左依次遍历去找
        }
        //这个while循环的目的是从右边开始找比middleVal小的值
        while (arr[rIndex] > middleVal) {
            rIndex -=1; //从右边依次向左开始遍历找
        }
        //当前这个判断条件成立就表示我们左边的值全部小于等于middleVal(也就是按照要求完成了,可能是无序的),而右边的值全部大于middleVal
        if (lIndex >= rIndex){
            break;
        }

        //交换
        temp = arr[lIndex];
        arr[lIndex] = arr[rIndex];
        arr[rIndex] = temp;

        //如果此时 arr[lIndex] == middleVal了,我们需要让rIndex前移一位
        if (arr[lIndex] == middleVal){
            rIndex -=1;
        }
        //如果此刻arr[rIndex] == middleVal了,我们需要让lIndex后移一位
        if (arr[rIndex] == middleVal){
            lIndex +=1;
        }
    }
    //多次递归循环
    //临界情况:
    //如果lIndex == rIndex,我们需要让 lIndex ++,rIndex --,防止栈溢出
    if (lIndex == rIndex){
        lIndex +=1;
        rIndex -=1;
    }

    //向左递归
    if (leftIndex <rIndex){
        quickSort(arr,leftIndex,rIndex);
    }
    //向右递归
    if (rightIndex > lIndex){
        quickSort(arr,lIndex,rightIndex);
    }
}

代码注释很详细,感兴趣的可以看看,我们来看测试结果:

测试结果.png

测试结果来看,我们的代码是没问题的,最后一点,我们最后来看一个问题,通过10W条数据来测试下快速排序的执行时间,测试代码如下:

 int [] arr = new int[100000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)(Math.random() * 100000); //随机生成[0,100000)的数
    }
    Date date1 = new Date();
    SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format = dateFormat.format(date1);
    System.out.println("排序前的时间为:"+format);
    //进行排序
    quickSort(arr,0,arr.length-1);
    Date date2 = new Date();
    SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format2 = dateFormat.format(date2);
    System.out.println("排序后的时间为:"+format2);
    quickSort(arr,0,arr.length-1);

测试结果如下:

时间测试结果.png

可以看得出,很快哈,到底有多快我也不清楚,那么关于它的学习就到这里了.