java数据结构

Question

看到排序 有点看不懂希尔排序，划分，快速排序，求解释

Answer 1

[code="java"]package sorts;

import java.util.Stack;

//对int数组进行快排的类
public class QuickSort {

private int[] data;// 待排序数组

public QuickSort(int[] para) {
    this.data = para;
}

// 划分方法，类内使用
private int partition(int i, int j) {
    int pivot = this.data[i];// 关键值
    while (true) {
        for (; this.data[j] >= pivot && i < j; --j);
        if (i == j) {
            break;
        }
        this.data[i] = this.data[j];
        for (; this.data[i] <= pivot && i < j; ++i);
        if (i == j) {
            break;
        }
        this.data[j] = this.data[i];
    }
    this.data[i] = pivot;// 还原关键值的位置
    return i;
}

// 递归快排
private void recur(int low, int high) {
    int pivotpos; // 划分后的基准记录的位置
    if (low < high) {// 仅当区间长度至少为2时才排序
        pivotpos = this.partition(low, high); // 对R[low..high]做划分
        this.recur(low, pivotpos - 1); // 对左区间递归排序
        this.recur(pivotpos + 1, high); // 对右区间递归排序
    }
}

// 递归快排结果
public void sort_recur() {
    this.recur(0, this.data.length - 1);
}

// 非递归快排
public void sort() {
    Stack<Integer> stack = new Stack<Integer>();
    int start = 0;
    int end = this.data.length - 1;
    int pivot;
    while (true) {
        if (end > start) {
            pivot = this.partition(start, end);
            if (end > pivot + 1) {// 后一段入栈
                stack.push(end);
                stack.push(pivot + 1);
            }
            end = pivot - 1;
            if (stack.empty()) {
                break;// 退出函数
            }
        } else {// 结果出栈
            start = stack.pop();
            end = stack.pop();
        }
    }
}

// 测试代码
public static void main(String[] args) {
    int a[] = new int[] { 9, 8, 23, 1, 6, 5, 11, 43, 4, 13 };
    // new QuickSort(a).partition(0, a.length-1);
    // new QuickSort(a).sort_recur();
    new QuickSort(a).sort();
    for (int i : a) {
        System.out.println(i);
    }
}

}
[/code]

带注释的毕竟好懂些