算法——快速排序

2022-3-5 diaba 算法 

package com.jiucaiyuan.net.algrithm.sort;
/**
 * <pre>
 * 快速排序
 *  一个数组arr，选择一个数做为基准m，小于等于m的数放在数组左边，大于m的数放在数组右边
 *  左侧递归上述过程
 *  右侧递归上述过程
 *
 *  荷兰国旗问题：  <m,=m,>m
 *
 * 时间复杂度 O(N*logN)，空间复杂度 O(logN)
 * 如果选择的基准数比较偏时，时间复杂度O(N^2)  空间复杂度O(N)
 * </pre>
 * Created by jiucaiyuan on 2022/3/5.
 */

public class QuickSort {
    /**
     * 快速排序算法
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static void quickSort(int[] arr,int l,int r){
        if(l<r){
            swap(arr,l+(int)(Math.random()*(r-l+1)),r);
            //分成左右两块，左侧比某个数小，右侧比某个数大
            int[] p = partition(arr,l,r);
            //对左侧进行快排
            quickSort(arr,l,p[0]);
            //对右侧进行快排
            quickSort(arr,p[1],r);
        }
    }

    /*
     * 对数组进行分区：左侧比
     * @param arr  数组
     * @param l  左元素
     * @param r  右元素
     * @return   小于某个数的有边界和大于某个数的左边界下标
     */
    private static int[] partition(int[] arr, int l, int r) {
        if(arr == null || arr.length<2){
            return new int[]{l,l};
        }
        //小于基准数的右边界
        int less = l-1;
        //大于基准数的左边界
        int more = r;
        while(l<more){
            if(arr[l]<arr[r]){
                swap(arr,++less,l++);
            }else if (arr[l] == arr[r]){
                l++;
            }else{
                swap(arr,l,--more);
            }
        }
        return new int[]{less,more};
    }

    /**
     * 交换两个不相等的数，如果相等，会都变成0
     * @param arr
     * @param l
     * @param r
     */
    private static void swap(int[] arr,int l,int r){
        if(l==r){
            return;
        }
        //交换两个不同数
        arr[l] = arr[l]^arr[r];
        arr[r] = arr[l]^arr[r];
        arr[l] = arr[l]^arr[r];
    }

    public static void main(String[] args){
        int[] arr = {12,5,3,7,3,8,4,3,2,2,6,8,6,0,9,5,3};
        print(arr);
        quickSort(arr, 0,arr.length-1);
        print(arr);
    }
    private static void print(int[] arr) {
        if(arr == null ){
            return;
        }
        for(int a : arr){
            System.out.print(a+"\t");
        }
        System.out.println();
    }
}

« 算法——归并法排序 | Java位运算符»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022