• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

快速排序

互联网 diligentman 1周前 (11-22) 4次浏览

简介

知名度极高的排序算法,对大数据具有优秀的排序性能,相同复杂度的算法中又相对简单实现。

概念

1.从数组中选取一个元素作为基准。
2.以此基准进行比较,将数组中大于基准的元素放在右边,小于基准的元素方法左边。(例如 arr={8,2,7,1,4} 选取8为基准 继续比较后得到 4,2,1,8,7 基准左边的数字都小于基准,右边都大于基准)
3.进行递归,对基准两边的子序列再进行排序

动图演示:
快速排序

实现

使用Java进行实现
实现此算法需要三个方法分别是入口方法

//入口方法
    public static void quickSort(int []arr) {
        //调用分组方法
        qsort(arr,0,arr.length-1);
    }

分组方法

//分组
    public static void qsort(int []arr,int low,int height) {}

排序的方法

//返回基准
    public static int partition(int []arr,int low,int height) {}

编写分组方法:
分组方法中首先要调用排序方法对数组进行排序排序方法在进行一次排序后会返回基准的下标,基于此下标对基准左右的子序列进行递归。

//当左右两端指向同一个节点时,不再分组
        if(low>=height) {
            return;
        }
        //获得基准
        int pivot=partition(arr,low,height);
        //递归分组
        qsort(arr,low,pivot-1);
        qsort(arr,pivot+1,height);

编写排序方法:
首先创建一个变量pivot存放基准数据,然后开始进行比较,首先从右往左找到比基准小的数据然后进行将其放到左边,再从左往右找到比基准大的数据将其放到右边,最后知道不满足low<height的条件跳出循环,此时low与height应该是相等,将其指向的数据替换成基准pivot,最后返回基准的下标。

    //基准数据
        int pivot=arr[low];
        while(low<height) {
            //将小于基准的数据放到左边
            //当数据大于基准则不动,继续检索下一个
            while(low<height&&arr[height]>=pivot) --height;
            //跳出循环之后说明当前数据小于基准,进行交换
            arr[low]=arr[height];
            //将大于基准的数据放到右边
            //当数据小于基准则不动,继续检索下一个
            while(low<height&&arr[low]<=pivot) ++low;
            arr[height]=arr[low];
        }
        arr[low]=pivot;
        return low;

最后实现:

import java.util.Arrays;

/**
 * 快速排序
 * @author SiDiWen
 *
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array= {87,1,25,76,15,45};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
    //需要三个方法
    //1.分组的方法
    //2.排序的方法
    //3.入口方法
    
    //入口方法
    public static void quickSort(int []arr) {
        qsort(arr,0,arr.length-1);
    }
    
    //分组
    public static void qsort(int []arr,int low,int height) {
        //当左右两端指向同一个节点时,不再分组
        if(low>=height) {
            return;
        }
        //获得基准
        int pivot=partition(arr,low,height);
        //递归分组
        qsort(arr,low,pivot-1);
        qsort(arr,pivot+1,height);
    }
    //返回基准
    public static int partition(int []arr,int low,int height) {
        //基准数据
        int pivot=arr[low];
        while(low<height) {
            //将小于基准的数据放到左边
            //当数据大于基准则不动,继续检索下一个
            while(low<height&&arr[height]>=pivot) --height;
            //跳出循环之后说明当前数据小于基准,进行交换
            arr[low]=arr[height];
            //将大于基准的数据放到右边
            //当数据小于基准则不动,继续检索下一个
            while(low<height&&arr[low]<=pivot) ++low;
            arr[height]=arr[low];
        }
        arr[low]=pivot;
        return low;
    }
}

总结

稳定性

快速排序是不稳定的排序,无法保证相等的数据不会互换位置。

适用场景

大部分情况下都适用,尤其数据量大时。


程序员灯塔
转载请注明原文链接:https://www.wangt.cc/2020/11/%e5%bf%ab%e9%80%9f%e6%8e%92%e5%ba%8f/
喜欢 (0)