【快速排序】基础及代码优化

⭐️ 前言：

快速排序算法的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分均比另一部分记录的关键字小，则可分别对着两部分记录进行排序，以达到整个序列有序的目的。
快速排序其实采用的是分治法的思想：
1.划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列，轴值的位置再划分过程中确定，并且前一个子序列的记录均小于或等于轴值，，后一个子序列中的记录均大于或等于轴值。
2.求解子问题：分别对划分后的每一个子序列递归处理
3.合并：由于对子序列的排序是就地进行的，所以合并不需要进行操作。

1.原始快速排序

原始的快速排序也就是最开始被Tony Hoare提出的算法

基本思想如下：

每次取当前序列第一个值作为轴值

第一次从轴值的远端开始扫描（右端）当右指针扫描到比轴值小的值就和轴值进行交换，然后转换成左指针往右扫描
当左指针扫描到比轴值大的值就和轴值进行交换，然后转换成右指针往左扫描
当左右指针相遇时退出循环，这时候当前序列就被分为两个子序列而且轴值的位置也被确定了
对左右子序列递归上述操作，直到左指针大于等于右指针的时候退出递归

❓存在的问题：

轴值被不断的移动，而轴值在一开始的移动中并没有移动到确定的位置，相当于前面几次对轴值的移动是可以省略的。
轴值的选取过于固定，排序速度的快慢取决于轴值选定在整个序列的位置，如果轴值是当前序列的最大值，那性能就达不到预期的效果（其实不论选第一个还是中间值作为轴值都是不合理的，都可能会出现这样的情况），为了解决这样的问题，我们可以通过取随机数的方式解决取中轴的问题。

package com.divideMethod;

import java.util.Scanner;

public class QuickSort01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[] arr = new int[m];
        sc.nextLine();
        for(int i=0;i=pivot) {
                    //j从右往左扫描
                    j--;
                }
                //将比中枢值小的值和中枢值进行交换
                int temp = arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
                while(i 
2.减少轴值交换优化快速排序 
package com.divideMethod;


import java.util.Arrays;
import java.util.Scanner;

public class QuickSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数组长度：");
        int len = sc.nextInt();
        System.out.println("请输入数组元素：");
        int[] arr = new int[len];
        for (int i=0;i=pivot) {
                    high--;
                }
                while(low 
 3.随机选取轴值优化快速排序 
 
 ❗️随机选取轴值是在第一种上加了一个求随机数的方法，根据这个方法，可以的得到当前序列中的随机的轴值，需要注意的是，轴值得到后，要先把轴值交换到第一个位置（也就是模拟还是取第一个元素为轴值，这样剩下的代码可以直接复用了）
 求随机数记得注意范围的控制 
 
package com.divideMethod;

import java.util.Random;
import java.util.Scanner;

public class QuickSort02 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[] arr = new int[m];
        sc.nextLine();
        for(int i=0;i=pivot) {
                    //j从右往左扫描
                    j--;
                }
                //将比中枢值小的值和中枢值进行交换
                temp = arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
                while(i 0-3 -> 2-5    2-5是最终确定的求随机数范围
        int res = ran.nextInt(high-low)+low;
        return res;
    }
}
 
4.2和3结合优化快速排序 
package com.divideMethod;


import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class QuickSort03 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数组长度：");
        int len = sc.nextInt();
        System.out.println("请输入数组元素：");
        int[] arr = new int[len];
        for (int i=0;i=pivot) {
                    high--;
                }
                while(low

【快速排序】基础及代码优化

Java相关栏目本月热门文章