方法1

CAR Hoare引入了分区逻辑(如下所示),这是在学校教授的,

low = pivot = 0;
i = 1;
j = high = listSize-1;

while (true) {
    while (a[i] <= a[pivot] && (i < high)) {
        i = i + 1;
    }
    while (a[j] >= a[pivot] && (j > low)) {
        j = j - 1; 
    }

    if (i >= j)
        break;
    swap(a[i], a[j])
}

swap(a[j], a[pivot]); // pivot element is positioned(once)
return j;

方法2

为了基本上尽量让它稳定的排序,而是j指向最后一个索引(listSize-1),如果j点listSize/2(即mid),那么, …