给定一个数组,例如[9,6,4,7,8,3,2,1,5]
设置两个列表位数的变量i和j,一个从前面开始向后迭代,一个从后面开始迭代,以第一个基准点9为例,
1.先从后向前找,找出第一个比9小的数字为5
然后从前往后遍历,找出第一个比9大的数字,遍历到末尾也没找到,此时5和9交换位置,现在的列表为[5,6,4,7,8,3,2,1,9]
2.然后以5为基准数,从后往前遍历,找出第一个比5小的数字为1,然后从前往后遍历找出第一个比5大的数字为6,此时1和6替换位置,列表为[5,1,4,7,8,3,2,6,9];j继续向前遍历,找到第一个比5小的数字为2,i继续向后变量,找到第一个比5大的数字为7,此时2和7互换位置,列表为[5,1,4,2,8,3,7,6,9],j继续向前遍历,找到比5小的数字3,i继续向前遍历,找到比5大的数为8,3和8互换位置,此时列表为[5,1,4,2,3,8,7,6,9],此时j继续向前遍历,遍历到了i的位置,然后3和5互换位置,列表为[3,1,4,2,5,8,7,6,9]
3.以5为分割点,前半部分数组为[3,1,4,2],后半部分为[8,7,6,9],
前半部分,以3为基准数,从后往前找到比3小的数为2,从前往后找,找到比3大的数为4,2和4互换位置,列表为[3,1,2,4],继续向前遍历,j遍历到i的位置,将2和3的位置互换列表为[2,1,3,4],然后以2位基准数,从后开始遍历,1和2互换位置,列表为[1,2,3,4]
后半部分,以8为基准数,j从后往前遍历,找出比8小的数,为6,i从前往后遍历,遍历到j的位置未找到比8大的数,此时6和8互换位置,列表为[6,7,8,9]
综上,排序结束,列表为[1,2,3,4,5,6,7,8,9]