用新的代码理解快排算法

理解快排算法新代码关键点对过往看过的快排算法教程的吐槽新代码/* quicksort: sort v[0]..v[n-1] into increasing order */voidQuickSort(intv[],intn){if(n1)return;inti,last0;/* move pivot elem to v[0] */Swap(v,0,rand()%n);for(i1;in;i){if(v[i]v[0]){last;Swap(v,last,i);}}Swap(v,0,last);QuickSort(v,last);QuickSort(vlast1,n-last-1);}关键点随机取一个数作为pivot把pivot放在索引0位置从索引1开始遍历数组遇到能放pivot左边的数则1.扩展左边集合左边pivot左边的数pivot2左边集合尾部与当前数交换完成排序last标记左边集合的尾部索引遍历完成后pivot和左边集合尾部交换位置即lastpivot最后处于索引last位置对pivot左边的数[0,last-1],右边的数[last1,n-1]分别快排全览效率提升点是”一次交换排好2个数“相较冒泡等一次只排好一个数排好在pivot的左边or右边对过往看过的快排算法教程的吐槽以前看过的那些教程代码往往会直接取索引0的数当pivot用i,j来设置2个游标去从数组的两端开始向中间移动直至ij结束遍历最后交换pivot和i,j的相遇位置的数。pivot为什么要取索引0的数为什么要求右端先移动最后换那一下是什么意义怎么就排好了都让人摸不着头脑。而上面的算法来自https://github.com/Heatwave/the-practice-of-programming/blob/master/2.2.quick-sort.clast这个变量的引入以及i从索引1开始遍历数组pivot的随机取用都让一切变得清晰。