上节我们学习了希尔排序,最后发现是希尔排序最原始的思想还是利用了插入排序,只不过是对它进行了优化,在上篇文章的最后,我们比较了插入法和移位法算法的执行时间,可以看得出天壤之别,今天我们来学习下另外一种算法叫快速排序.
快速排序介绍
快速排序是对冒泡排序的一种改进,其基本的思想是:通过一趟排序对将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分都要小,然后在按此方法对这两部分数据分别进行快速排序,在整个的排序过程中可以采用递归的方式进行,来达到整个数据为有序的.
上述的理论性的东西大家有个大概的理解即可,我们接下来采用图解的方式来完成对它的讲解,首先来看如图所示:
快速排序图解示意图.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
可以看得出,很快哈,到底有多快我也不清楚,那么关于它的学习就到这里了.
