快速排序算法是在分治算法基础上设计出来的一种排序算法,和其它排序算法相比,快速排序算法具有效率高、耗费资源少、容易实现等优点。
快速排序算法的实现思路是:
真正实现快速排序算法时,我们通常会挑选待排序序列中第一个元素或者最后一个元素作为中间元素。
1) 建立 2 个指针(命名为 lo 和 hi),分别指向序列中第一个元素和倒数第 2 个元素,如下图所示:
2) lo 指针向右移动,当指向的元素不小于 31 时暂停。显然,当前指向的 35 > 31,所以 lo 暂时不移动;
3) hi 指针向左移动,当指向的元素不大于 31 时暂停。显然,当前指向的 26< 31,所以 hi 暂时不移动;
4) 交换 lo 和 hi 所指元素的位置,如下图所示:
5) 重复执行 2~4 步,直至 lo ≥ hi。此时,将 pivot 元素与 lo 所指元素交换位置。下面的动画演示了整个分割的过程:
- /**
- * @author wangli
- * @data 2022/6/28 16:02
- * @Description:
- */
- public class QuickSort {
- public static void main(String[] args) {
- int[] arr={1,4,63,5,7,9,12};
- quickSort(arr,0, arr.length-1);
- System.out.println(Arrays.toString(arr));
- }
- public static void quickSort(int[] arr, int left, int right) {
- //判断传入值是否符合
- if(left>=right){
- return;
- }
- //左右指针
- int l=left;
- int r=right;
- //中心轴pivot
- int pivot=arr[left];
- //临时交换节点
- int temp;
- //判断两个数是否符合在pivot左边的是比他小在pivot右边比他大
- while (l!=r){
- //找到比pivot小的值
- while (arr[r]>=pivot&&l<r){
- r--;
- }
- while (arr[l]<=pivot&&l<r){
- l++;
- }
- //将不符合的两个数交换位置
- temp=arr[l];
- arr[l]=arr[r];
- arr[r]=temp;
- }
- //当l和r相等时,将pivot放到中间,正好实现左边小右边大的
- arr[left]=arr[l];
- arr[l]=pivot;
- //向左边递归排序,直至无法排序为止
- quickSort(arr,left,l-1);
- quickSort(arr,r+1,right);
- }
-
- }