要么改变世界,要么适应世界

算法模板之快速排序

2020-08-24 19:06:00
312
目录

快速排序属于性能较好的排序算法,能够将平均的时间复杂度趋于O(nlogn),而空间复杂度为O(1)

模板代码

public void q_sort(int l, int r, int[] array) {
    if (l >= r) return;
    int i = l, j = i + 1, key = array[l];
    for (; j <= r; j++) {
        if (array[j] < key) {
            i++;
            swap(i, j, array);
        }
    }
    swap(l, i, array);
    q_sort(l, i - 1, array);
    q_sort(i + 1, r, array);
}

public void swap(int i, int j, int[] array) {
    int t = array[i];
    array[i] = array[j];
    array[j] = t;
}

不过JDK自带的Arrays.sort()不香么,除非题目限制不可以使用吧

历史评论
开始评论