快速排序的思想
- 在一个无序的数组中,取最后的一个数字为基准值,在经过一次排序后,使得改无效而的数组中,小于基准值的在左侧,等于基准值的在中间,大于基准值的在右侧。
- 假设一个无序数组为
那么他经过排序后的结果应该为:
具体实现过程:
在排序的时候,我们每次都取最后一个元素为基准值,创建p1指向无序数组元素的前一个位置,创建p2指向无序数组的最后元素的后一个位置。
第一次排序,首先i指向第一个元素,判断当前元素是和基准值的大小
大小的比较分为三种情况:
第一种:该元素 < 基准值,则该元素与p1指向的前一个元素交换,p1++,i++
第二种:该元素 = 基准值,测i++
第三种:该元素 > 基准值,测该元素与p2指向的后一个元素交换,p2–,i不变
例如:当前 [i] 的值为4 < 基准值 则符合第一种情况
移动之后,当前的[i] 的值为5 = 基准值 ,则符合第二种情况
移动之后,[i] 的值为 7 ,则符合第三种情况
移动之后,[i] = 5 ,则符合第二种情况
移动之后,[i] = 5 ,符合第二种情况
移动之后,[i] = 3 ,符合第一种情况
移动之后,i == p2 ,结束循环。 - 对于这一次循环来说,开始的基准值为最后一个元素,到循环结束之后,小于基准值的在侧,等于基准值的在中间,大于基准值的在右侧。相当与在这次遍历的过程,我们把等于基准值的一批数固定了位置。搞定了一批数。接下来只需要对左边的和右边的进行排序,重复此过程。最后就会把所有的数的位置固定下来。当所有的数的位置都固定下来了,那么就可以说这个数组使有序的了。
- p1 和 p2 指向的是什么呢,指的是小于基准值 和 大于基准值的范围,当出现符合条件的数,就把该数放到里面去。
- 结束循环的条件: 因为p2 指向的是 大于 基准值的边界,当 i 的下标 等于 p2 的时候,自然就没有继续遍历的必要了。
代码实现(java)
/**
* 快速排序算法
*/
public class QuickSort {
public static void quickSort(int[] array){
if (array == null || array.length < 2) {
return; //array为空或者该数组元素为一,没有排序的意义
}
quickSort(array, 0, array.length - 1);
}
private static void quickSort(int[] array, int l, int r) {
if ( l >= r){
return; //数据不合法,退出程序
}
//要向使l --> r中有序,先找到一个基准数,取数组的最后一个数为基准数
int num = array[r];
//找到基准数在数组中的位置,使得 < 基准数的在左边 ,等于基准数的在中间, > 基准数的在右边。
int[] index = quick_sort(array, l, r,num); //此时中间的 = sum的已经拍好序了
quickSort(array,l,index[0]); //使左边的有序
quickSort(array,index[1],r); //使右边的有序
}
private static int[] quick_sort(int[] array, int l, int r, int num) {
//找到基准数在数组中的位置,使得 < 基准数的在左边 ,等于基准数的在中间, > 基准数的在右边。
int p1 = l - 1;
int p2 = r + 1;
while (l < p2) {
if (array[l] < num){
//1.第一种情况,如果小于num的时候,将该元素与 < 范围的前一个交换,i++
int temp = array[l];
array[l] = array[p1 + 1];
array[p1 + 1] = temp;
l++;
p1++;
}else if (array[l] == num){
//2.第二种情况,如果[l]==sum的时候,l++
l++;
}else {
//3.第三种情况,如果[l] > sum的时候,[l] 与 > 范围的前一个元素交换
int temp = array[l];
array[l] = array[p2 - 1];
array[p2 - 1] = temp;
p2--;
}
}
return new int[]{p1,p2}; //此时中间的 = sum的已经拍好序了、
}
public static void main(String[] args) {
int[] array = new int[]{1,5,3,6,3,5,8,10,3};
quickSort(array);
for (int i : array) {
System.out.println(i);
}
}
}
版权声明:本文为qq_56330528原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。