排序算法-快速排序
程序员文章站
2022-07-08 23:03:14
...
一.快速排序的基本原理
快速排序分为以下几步:
第一步:在数组中任意选取一个数作为基准数(pivot)
第二步:通过处理,将数组中大于基准数的数都放在基准数的右边,小于基准数的数都放在基准数的左边。
第三步:通过第二步,对基准数的左右两边再重复第一步和第二步的操作,不断重复,直到区间里只剩下一个或者没有元素为止。
二.快速排序图解
三.快速排序代码(Java)
import javax.swing.plaf.basic.BasicArrowButton;
import java.util.ArrayList;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] array = {9,13,12,3,0,3,21};
qucikSort(array);
System.out.println(Arrays.toString(array));
}
private static void qucikSort(int[] array) {
quickSortDiGui(array,0,array.length-1);
}
private static void quickSortDiGui(int[] array,int left, int right) {
//当left大于right即证明左边或者右边没有元素
//当left等于right即证明只有一个元素不用再比较
if(left >= right){
return;
}
/*
快速排序:
1.选取一个基准点(此处选最左边的元素)
2.将比基准点小的元素放在基准点的左边,将比基准点大的元素放在基准点的右边。最后将基准点与中间的值交换,并且返回基准点的位置
3.一轮结束后,基准点的左边和右边分别一个小的数组重复第二步操作,直到基准点左边或者着右边的元素为1个或者0个(即采用分治方法)
*/
//1.传进来一个数组之后,先进行一次第二步的操作(partition)返回值为mid
int mid = partition(array,left,right);
quickSortDiGui(array,left,mid-1);
quickSortDiGui(array,mid+1,right);
}
private static int partition(int[] array, int left, int right) {
int begin = left;
int end = right;
int pivot = array[left];
while(begin<end){
while(begin < end && array[end] >= pivot){
end--;
}
while(begin < end && array[begin]<= pivot){
begin++;
}
swap(array,begin,end);
}
swap(array,begin,left);
return begin;
}
private static void swap(int[] array, int begin, int end) {
int t = array[begin];
array[begin] = array[end];
array[end] = t;
}
}
四.复杂度分析
五.注意事项(循环必须先执行end--)
如上图,6在左,9在右 我们将6作为基数。
假设从左边开始(与正确程序正好相反)
while (nums[i] <= index && i < j) {
i++;
}
while (nums[j] >= index && j > i) {
j--;
}
按照这个代码逻辑,走一遍,i 就会移动到现在的 数字 7 那个位置停下来,而 j 原来在 数字 9 那个位置
于是,j 也会停留在数字7 那个位置,然后 i == j了,这时候交换基准数和nums[i]
交换后的数组为:7 1 2 6 9
这时候,你会发现问题来了,这结果不对呀!!!
问题在于当我们先从在边开始时,那么 i 所停留的那个位置肯定是大于基数6的
而在上述例子中,为了满足 i<j 于是 j也停留在7的位置,但最后交换回去的时候,7就到了左边
不行,因为我们原本 交换后数字6在边应该是全部小于6,右边全部大于6,但现在不行了。
所以,我们必须从右边开始,也就是从基准数的对面开始。
下一篇: HTML,CSS CSS