排序算法——快速排序

https://blog.csdn.net/weixin_50886514/article/details/119045154

大纲目录
排序算法简介

• 快速排序
• • 一、快速排序法介绍
  • 二、快速排序法示意图
  • 三、左右指针法
  • • 1、左右指针法思路：
    • 2、左右指针法图解
  • 四、填坑法
  • • 1、填坑法思路
    • 2、填坑法图解
  • 五、源码

    快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

1. 选出一个key，一般是最左边或是最右边的。
2. 定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
3. 在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
4. 此时key的左边都是小于key的数，key的右边都是大于key的数
5. 将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序

挖坑法思路与hoare版本(左右指针法)思路类似

1. 选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑.
2. 还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）.

public class QuickSort {
    public static void main(String[] args) {
//        int arr[]  = {8,9,1,7,2,35,4,6,0};
//        quickSort1(arr,0,arr.length-1);
        quickSort2(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));

        int[] arr = new int[80000000];//八千万条数据
        for(int i =0; i < 80000000;i++) {
            arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
        }
        System.out.println("80000条数据排序开始：");
        long start1 = System.currentTimeMillis();
        quickSort1(arr,0,arr.length-1);//左右指针法：7801
//        quickSort2(arr,0,arr.length-1);//填坑法：7533
        long end1 = System.currentTimeMillis();
        System.out.println("80000条数据排序结束：");
        System.out.println("80000条数据排序耗时："+(end1-start1));
    }


    
    public static void quickSort1(int[] arr,int begin,int end){
        if(begin>=end){
            return;
        }
        int left = begin;
        int right = end;
        int key = begin;
        int temp = 0;
        while (begin
            //右边选小
            while (arr[end] >= arr[key] && begin
                end--;
            }
            //左边选大
            while (arr[begin]<=arr[key] && begin 
                begin++;
            }
            //交换位置
            temp = arr[begin];
            arr[begin] = arr[end];
            arr[end] = temp;
        }
        //相遇后交换key和end的位置
        temp = arr[key];
        arr[key] = arr[end];
        arr[end] = temp;
        //更新key的位置
        key = end;
        //递归处理
        quickSort1(arr,left,key-1);
        quickSort1(arr,key+1,right);
    }


    
    public static void quickSort2(int[] arr,int begin,int end){
        if(begin>=end){
            return;
        }
        int left = begin;
        int right = end;
        int key = arr[begin];
        while (begin
            //右边选小
            while (arr[end] >= key && begin
                end--;
            }
            arr[begin] = arr[end];
            //左边选大
            while (arr[begin]<=key && begin 
                begin++;
            }
            arr[end] = arr[begin];
        }
        //每轮过后将key放入最后的坑
        arr[begin] = key;
        //更新key的位置
        int keyi = begin;
        //递归处理
        quickSort1(arr,left,keyi-1);
        quickSort1(arr,keyi+1,right);
    }
}