常见的排序算法---快速排序算法

2023-12-19 21:42:55

快速排序算法
快排是基于分治的思想来的,快速排序就是在元素序列中选择一个元素作为基准值,每趟总数据元素的两端开始交替排序,将小于基准值的交换的序列前端,大于基准值的交换到序列后端,介于两者之间的位置称为基准值最终的位置。同时序列被划分成两个子序列,再对两个子序列进行排序,这个过程就是递归的过程,直到子序列的长度为1,则完成排序。
模板 洛谷:P1177排序

代码

import java.util.Scanner;

class quickSort {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int arr[]=new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=scanner.nextInt();
        }
        quick(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    public  static  void quick(int [] keys, int begin,int end){
        if (begin>=0&&begin<end&&end<keys.length){
            int i=begin,j=end;
            int x=keys[i];//找到基准元素
            while (i!=j){ //
                while (i<j&&keys[j]>=x){ //从后往前找
                    j--;
                } //直到找到小的数字了
                if (i<j){
                    keys[i++]=keys[j]; //i往后移动一位,讲原来i的位置赋值给j
                }
                while (i<j&keys[i]<=x){ //从前向后寻找较大值移动
                    i++;
                }//找到较大值了
                if (i<j){
                    keys[j--]=keys[i];//讲较大值赋值给j,并且j往前移动一位;
                }
            }
            //当i等于j的时候结束上面的循环 需要重新设置基准值,基准值就是当前的位置

            keys[i]=x;
            quick(keys,begin,j-1);
            quick(keys,i+1,end);
        }

    }
}
时间复杂度 最好 nlogn 最坏on方

快速排序算法并且是不稳地的。

文章来源:https://blog.csdn.net/ngczx/article/details/135092305
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。