排序sort算法

2021/02/26 leetcode 算法
如果文章图片无法显示,可尝试配置host:修复Github图片资源无法显示问题

一、快速排序

image-20210226155041152

直到两个数相遇,基数和相遇位置进行交换,一次快排完成

image-20210226155108512

上代码:

java http://beangogo.cn/assets/images/artcles/2021-02-26-排序sort算法.assets

/**
 * 快速排序
 */
public class QuickSort {
    public static  void swap (int arr[],int i, int j){
        if(arr[i]!=arr[j]){
            arr[i]=arr[i]^arr[j];
            arr[j]=arr[i]^arr[j];
            arr[i]=arr[i]^arr[j];
        }
    }
    // 递归使用快速排序,对arr[l...r]的范围进行排序
    public static void QuickSort(int[] arr,int l,int r){
        if(l>=r) return;
        int p = partition(arr,l,r);
        QuickSort(arr,l,p-1);
        QuickSort(arr,p+1,r);
    }
    //一次快速排序过程,返回两个指针相遇的位置
    private static int partition(int[] arr, int left, int right) {
        //获取三个元素:基数,左指针,右指针
        int key = arr[left];
        int i = left ;
        int j = right;
        while(i!=j){
            while (arr[j]>=key && i<j) j--;
            while (arr[i]<=key && i<j) i++;
            swap(arr,i,j);
        }
        swap(arr,left,j);
        return j;
    }
   
    public static void main(String[] args) {
        int [] arr ={6,1,4,5,9,10,6,6};
        QuickSort(arr,0,arr.length-1);
        System.out.println(arr);
    }
}

python版



公众号:豆仔gogo

golang、算法、后端知识、面试手册

豆仔gogo

Search

    公众号:豆仔gogo

    豆仔gogo

    Post Directory