2020/07/16

package com.example;

import java.util.Objects;

public class HAHA20200715 {
    public static void main(String[] args) {
        Integer[] integers = new Integer[1000];
        for (int i = 0, len = integers.length; i < len; i++) {
            integers[i] = (int) ( Math.random() * 10 );
        }

        QSort qSort = new QSort(integers);
        qSort.work();
        System.out.println(qSort.toString());
    }
}

class QSort {
    private Element[] elements;
    public QSort (Integer...integers) {
        Objects.requireNonNull(integers);

        this.elements = new Element[integers.length];
        for (int i = 0, len = this.elements.length; i<len; i++) {
            this.elements[i] = new Element(integers[i]);
        }
    }

    public void swap (int a, int b) {
        Element tmp = this.elements[a];
        this.elements[a] = this.elements[b];
        this.elements[b] = tmp;
    }

    public void work () {
        int leftBorder = 0;
        int rightBorder = this.elements.length - 1;

        sort(leftBorder, rightBorder);
    }

    public void sort (int leftBorder, int rightBorder) {
        if (leftBorder >= rightBorder) return;
        int benchmark = partition(leftBorder, rightBorder);
        sort(leftBorder, benchmark - 1);
        sort(benchmark + 1, rightBorder);
    }

    public int partition (int leftBorder, int rightBorder) {
        Element benchmark = this.elements[leftBorder];
        int i = leftBorder, j = rightBorder + 1;

        while (true) {
            while (benchmark.compareTo(this.elements[++i]) >= 0) 
                if (i >= rightBorder) break;
            while (benchmark.compareTo(this.elements[--j]) <= 0)
                if (j <= leftBorder) break;
            if (i >= j) break;
            swap(i, j);
        }
        swap(leftBorder, j);
        return j;
    }

    @Override
    public String toString () {
        StringBuilder buf = new StringBuilder();
        for (Element e : this.elements) {
            if (buf.length() != 0) {
                buf.append("],[").append(e.getE());
            } else {
                buf.append(e.getE());
            }
        }
        return "[" + buf.toString() + "]";
    }
}

class CommonSort {
    public static void sort(int leftBorder, int rightBorder, Element[] elements) {
        for (int i = 1; i < elements.length; i++) {
            Element tmp = elements[i];

            int j = i;
            while (j > 0 && elements[j - 1].compareTo(tmp) > 0) {
                elements[j] = elements[j - 1];
                j--;
            }
            if (j != i) {
                elements[j] = tmp;
            }
        }
    }
}

class Element implements Comparable<Element>{
    private Integer e;

    public Element(Integer e) {
        this.e = e;
    }

    public Integer getE() {
        return e;
    }

    public void setE(Integer e) {
        this.e = e;
    }

    @Override
    public int compareTo(Element o) {
        return -this.e.compareTo(o.getE());
    }
}

本文地址：https://blog.csdn.net/luhuidong1/article/details/107375735