赞
踩
有如下数列:
第一个操作的对象是数列中的所有的数字。
选择一个数字作为排序的基数。这个数字被称为pivot。
pivot通常随机选择一个数字。为了方便起见,我们选择最右边的数字作为pivot。
为了清楚起见,我们将在pivot上做一个标记。
接下来,在最左边的数字上标记,称为左标记。同理,在最右边的数字上标记,称为右标记。
我们将左边的标记向右移动。,直到左标记达到的数超过了pivot所标记的数字时,停止移动。
这一次,因为8>=6而停止了移动。
然后,将右标记向左移动。当右标记达到小于的数字时,停止移动。
这一次,由于4<6,右标记停止了移动。
当左右侧标记停止时,将左右标记所指的数字进行交换。
交换之后,再次将左标记向右移动。
和之前一样,当左边的标记移动到大于或等于pivot的数字时停止移动。
这一次,由于9>=6,标记停止移动。
继续将右标记向左移动。
当右标记碰撞到左标记时也会停止移动。
如果左右都停止了,并标记在同一位置上,就将这个数字和pivot的数字交换。
将有左右侧标记的数字认为已排序完成。
这就完成了第一次操作。
通过一系列的操作,我们就把比pivot的数字小的数字放在了pivot的左边,同理,右面是比它大的数字。
然后,我们递归地将这个数列分成左右区,进行同样一系列的操作即可。
接下来,我们将操作左区的数列,
我们依旧建立3个标记。和之前一样进行操作。
在递归进行上述操作后,会得到部分排序的数列:
对左区进行操作。如果操作的数列只有一个数字,则认为它已经完成了排序。
第二轮将对右区的数列进行操作。
同样,建立3个标记。
将左标记向右移动。
当左标记和右标记碰撞时,即左标记撞击右标记,是不会停止移动的,它在这方面与右标记不同。当左标记达到数列的最右边时才停止移动。这意味着pivot数字是这个区的最大的数字。
接下里,移动右标记。
但如果它被路过的左标记所标记,则完成操作并不进行移动。
如果左标记已达到数列的最右边时,pivot数字被认为已排序完成,并完成这一轮的操作。
此后,重复相同的操作,直到所有的数字完成排序。
所以,我们必须特别注意:
不注意这点,会犯很多错误。
#include <iostream> template <class T> int getSizeOfArray(T& bs){ return sizeof(bs)/ sizeof(bs[0]); } /* * Method swapData can swap two data by index from initial array. * swapData方法可以通过初始数组的索引将所指数据交换。 */ void swapData(int *qs,int one,int another){ int cup = 0; cup = qs[one]; qs[one] = qs[another]; qs[another] = cup; } /* * Method quickSort can sort array by QuickSort. * quickSort可以利用快速排序算法将数组排序。 */ void quickSort(int *qs,int startIndex,int endIndex){ //非单位区间进行分治 if(startIndex<endIndex){ //设置pivot(这个本身是个随机数,为了方便写算法,先用最右边的数) int pivot = endIndex;//初始化基数 int leftIndex = startIndex;//初始化当前分治区域的左索引 int rightIndex = pivot-1;//初始化当前分治区域的右索引 int drFlag = 0;//分治标记,因算法使用while循环,需要中断标记 while(leftIndex<=rightIndex && drFlag!=1){//当左索引越位右索引或分治标记亮起,退出循环 //左标记启动 while(qs[leftIndex]<qs[pivot]&&leftIndex!=pivot){//当左索引找到一个大于等于基数的数或到达最右索引时,停止 leftIndex++; } //右标记启动 while(qs[rightIndex]>qs[pivot]&&leftIndex<rightIndex){//当右索引找到一个小于等于基数当数或被左索引标记过时,停止 rightIndex--; } if(leftIndex==rightIndex){//当左索引与右索引重合时,当前数据与基数交换位置,实现分区(左区均小于等于基数,右区均大于等于基数) //将撞击索引的数字与pivot索引的数字交换 swapData(qs,leftIndex,pivot); drFlag = 1;//下一步进行分治,亮起分治标记,退出while循环 } else if(leftIndex<rightIndex){ //左标记右标记数字交换 swapData(qs,leftIndex,rightIndex); leftIndex++;//继续移动 } } //左区分治 quickSort(qs,startIndex,leftIndex-1); //右区分治 quickSort(qs,rightIndex+1,endIndex); } } int main() { using namespace std; //2,3,5,1,0,8,6,9,7 int qs[] = {2,3,5,1,0,8,6,9,7}; int size = getSizeOfArray(qs); cout<< "原数列:"; for(int i = 0;i<size;i++) { cout<< qs[i] << " "; } cout<< "\n" << "快速排序后:"; quickSort(qs,0,size-1); for(int i = 0;i<size;i++) { cout<< qs[i] << " "; } return 0; }
这里为方便起见,我们假设算法Quick_Sort的范围阈值为1(即一直将线性表分解到只剩一个元素),这对该算法复杂性的分析没有本质的影响。
我们先分析函数qucikSort的性能,该函数对于确定的输入复杂性是确定的。观察该函数,我们发现,对于有n个元素的确定输入L[p…r],该函数运行时间显然为θ(n)。
"
这里的算法分析有点复杂,作者引用了书中的分析。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。