网站 › 『编程语言区』 › 十大排序算法之快速排序

QingYi. 发表于 2021-1-24 09:19

十大排序算法之快速排序

本帖最后由 QingYi. 于 2021-1-24 12:15 编辑


import java.util.Random;

public class partition {
    public static void main(String[] args) {
      int [] arr = {3,3,2,1,4,6,5,9,7,8,1};
      int n = arr.length;
      //拿到一个随机数,避免数组是有序的时候退化成一个链表
      Random rnd = new Random();
      sort(arr,0,n-1,rnd);

      for (int i : arr) {
            System.out.print(i +" ");
      }
    }

    private static void sort(int[] arr, int l, int r, Random rnd) {
      //越界退出
      if (l>=r){
            return;
      }

      int p= part(arr,l,r,rnd);
      // 递归进行排序 and
      sort(arr,l,p-1,rnd);
      sort(arr,p+1,r,rnd);
    }


    private static int part(int[] arr, int l, int r, Random rnd) {
      // 在l-r之间获得一个随机数，并交换一下
      int p = rnd.nextInt(r - l +1) + l ;
      swap(arr, l , p);
      // i如果小于l的话 一直右移j大于l的话 一直左移
      //也就是一边存小于l的 一边存大于l的，分开两个边界
      int i = l + 1, j = r;
      while (true){
            while (i<=j && arr< (arr) ){
                i++;
            }
            while (j>=i && arr> (arr) ){
                j--;
            }
            // 越界退出
            if (i>=j){
                break;
            }
            //到了这里的话 说明arr>l , arr<l 不符合排序规则，交换一下
            swap(arr,i,j);
            i++;
            j--;

      }
      // 循环完之后，把l 和 j放到正确的位置 l的左边都是小于l的数，右边都是大于l的数
      swap(arr,l,j);
      return j;
    }

    private static void swap(int[] arr, int a, int b) {
      int temp = arr;
      arr = arr;
      arr = temp;
    }
}

澹泊明志 发表于 2021-1-24 11:20

package sort;

public class QuickSort {
    public static void quickSort(int[] arr) {
      if (arr == null || arr.length < 2) {
            return;
      }
      quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int begin, int end) {
      if (begin < end) {
            swap(arr, begin + (int) (Math.random() * (end - begin + 1)), end);
            int[] partition = partition(arr, begin, end);
            quickSort(arr, begin, partition - 1);
            quickSort(arr, partition + 1, end);
      }
    }

    private static int[] partition(int[] arr, int begin, int end) {
      int less = begin - 1;
      int more = end;
      while (begin < more) {
            if (arr < arr) {
                swap(arr, ++less, begin++);
            } else if (arr > arr) {
                swap(arr, --more, begin);
            } else {
                begin++;
            }
      }
      swap(arr, more, end);
      return new int[]{less + 1, more};
    }

    private static void swap(int[] arr, int i, int j) {
      int tmp = arr;
      arr = arr;
      arr = tmp;
    }
}

wensanpi 发表于 2021-1-24 09:31

{:1_921:}aaaaaa

mcumail 发表于 2021-1-24 10:02

很好，感谢分享

sige1992 发表于 2021-1-24 10:12

学习了，谢谢分享

来年春风起 发表于 2021-1-24 10:41

收藏学习了

逸帅 发表于 2021-1-24 10:55

你这咋一个注释都没有啊，这可不是一个好习惯{:301_1008:}

QingYi. 发表于 2021-1-24 11:37

逸帅 发表于 2021-1-24 10:55
你这咋一个注释都没有啊，这可不是一个好习惯

哈哈哈哈 随手一打 认真打的时候没人问，索性写完直接放吾爱了

Didor 发表于 2021-1-24 11:52

唉，这些算法考了以后基本上都忘了，得要补补了

alittlebear 发表于 2021-1-24 11:59

本帖最后由 alittlebear 于 2021-1-24 12:02 编辑

时间复杂度好像是nlogn吧{:1_908:}看着这些递归啥的代码就头疼，看不懂哈哈，还是俩for方便

查看完整版本: 十大排序算法之快速排序