quick sort partition example

partition.txt

arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes:  0   1   2   3   4   5   6 

low = 0, high =  6, pivot = arr[h] = 70
初始化, i = -1， i 保存的是最近一次比较比 pivot 值小的index。

遍历 from j = low to high-1
j = 0 : arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0 
arr[] = {10, 80, 30, 90, 40, 50, 70} // i = j, 本身不需要交换

j = 1 : arr[j] > pivot, 什么都不干

j = 2 : arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30 

j = 3 :  arr[j] > pivot, 什么都不干

j = 4 :  arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 和 40 交换
j = 5 : arr[j] <= pivot, do i++ and swap arr[i] with arr[j] 
i = 3 
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 和 50 交换 

遍历结束，因为 j = high - 1

最后 arr[i+1] 和 arr[high] （pivot）交换

arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 和 70 交换