不多说了。接下来，我们马上进入本文的主题，排序算法。众所周知，快速排序算法是排序算法中的重头戏。因此，本文从快速排序入手。--------------------------------------------------1.快速排序算法的基本特点时间复杂度：O(n*lgn)最差：O(n^2)空间复杂度：O(n*lgn)不稳定。快速排序是一种排序算法，对于包含n个数字的输入数组，平均时间为O(nlgn)，最坏情况为O(n^2)。通常是排序的最佳选择。因为，基于比较的排序最快也只能达到O(nlgn)。2.快速排序算法说明算法导论，第7章快速排序是基于分而治之的模式。对一个典型的子数组A[p...r]进行排序的分而治之过程分为三个步骤：1.分解：将A[p..r]分成两个（可能为空的）子数组A[p。.q-1]和A[q+1..r]使得A[p..q-1]<=A[q]<=A[q+1..r]2.解决方案：对子进行排序-数组A[p..q-1]和A[q+1..r]通过递归调用快速排序。3.合并。3、快速排序算法版本一：QUICKSORT(A,p,r)ifpA[j]exchangeA[i+1]<->A[r]returni+1ok，我们举一个具体完整的例子。对以下数组进行快速排序，28713564(pivot)one,ip/j28713564(pivot)j指的是2<=4，所以i++,i也指的是2，2和2互换，原数组不变。j向后移动，直到指向1。第二，j（指向1）<=4，所以i++i指向8，所以8和1交换。数组变为：ij217835643.j向后移动，指向3，3<=4，所以i++i指向7，所以7和3交换。数组变为：ij21387564四、j继续向后移动，发现没有小于4的数，于是执行到最后一步，即上面的PARTITION(A,p,r)本节第7行代码。因此i往后移动一个单位，指向8ij21387564A[i+1]<->A[r]，也就是8和4互换，所以数组最后变成如下form,21347568ok，第一次快速排序完成。4将整个数组分成两部分，213,7568，然后分别对这两部分进行递归排序。ip/j213(主元)2和2互换，不变，然后1和1互换，还是不变，***，3和3互换，不变，最后，3和213，分分成两部分，21，3。然后21，递归排序，最后的结果变成123.7568(pivot)，7,5,6,都小于8，所以*第一次，它还是7568，但是这时候8把7568分成756，8.[756->576->567]然后756，递归排序，最后的结果变成了5678。ok，所有的过程，所有的分析都完成了。***，看我画的图：QuickSortAlgorithmVersion2不过这个版本不再选择数组的最后一个元素（如上***版本）作为主要元素，而是选择数组中的*数组的第一个元素是枢轴。/********************************************************//*函数功能：快速排序算法*//*函数参数：结构类型表指针变量tab*//*整型变量左右边界下标*//*函数返回值：空*//*文件名：quicsort.c函数名：quicksort()*//****************************************************/voidquicksort(table*tab,intleft,intright){inti,j;if(leftr[0]=tab->r[i];//这次准备按照最左边元素的值划分，先保存它的值do{while(tab->r[j].key>tab->r[0].key&&ir[i].key=tab->r[j].key;i++;}//将第j个元素放到左边，并重置iwhile(tab->r[i].keyr[0].key&&ir[j].key=选项卡->r[i].key;j--;}//将第i个元素放在右边并重新设置j}while(i!=j);tab->r[i]=tab->r[0];//将标准值放到最后的位置，本次除法结束quicksort(tab,left,i-1);//在标准值的左半部分递归调用此函数quicksort(tab,i+1,right);//在标准值的右半边递归调用这个函数}}----------------好的，让我们使用与上面相同的数组来应用快速排序的第二个版本算法，演示一下这个排序过程：这次以数组的第一个元素2为基准。2(primary)8713564请仔细看：28713564i-><-j(findbig)(findsmall)1.jj找到第一个小于21的元素,1被赋值（覆盖并重置）到i指向的元素2得到：1873564ijII,ii找到第一个大于28的元素，8被赋值（覆盖并重置）到j指向的元素(NULL<-8)1783564i<-j3.jj继续向左移动。在遇到i之前，没有找到小于2的元素，就结束了。***，添加了枢轴2。***快速排序后数组变为：12783564第二遍，783564i-><-j(找大)(找小)1,jj找4,小于枢轴7，将4赋值给7的位置得到：48356i->j2.ii找到第一个大于78的元素，8覆盖j指向的元素（NULL）43568ij46358i->ji遇到j并结束。第三趟：463578...下面，分析原理，一致，略过。***的结果如下图所示：12345678相信经过以上内容的具体分析，你一定明白了。***，贴一下我画的这个排序过程的图：完成。1月5日添加。OK，以上两种算法，你只需要了解一种即可。--------------------------------------------------------五、快速排序的最坏情况和最快情况。最坏的情况发生在划分过程产生的两个区域分别包含n-1个元素和一个0元素时，即假设算法在每次递归调用过程中发生，这种划分是不对称的。那么除法的代价就是O(n)，因为递归调用一个大小为0的数组后，返回的是T(0)=O(1)。该估计方法的运行时间可以递归表示为：T(n)=T(n-1)+T(0)+O(n)=T(n-1)+O(n)。可以证明T(n)=O(n^2)。因此，如果在算法的每一层递归上分区都是最大不对称的，则算法的运行时间为O(n^2)。也就是说，快速排序算法的最坏情况并不比插入排序好。此外，当数组完全排序时，快速排序会在O(n^2)时间内运行。而同样情况下，插入排序的运行时间为O(n)。//注意，请注意理解这句话。我们说排序的时间复杂度只针对一个元素。//意思是向一个有序序列中插入一个元素需要n个时间。我们来证明，在最快的情况下，即在PARTITION可能的最平衡划分中，得到的每个子问题都不能大于n/2。因为其中一个子问题的大小是|_n/2_|。另一个子问题的大小为|-n/2-|-1。在这种情况下，快速排序要快得多。因为，T(n)<=2T(n/2)+O(n)。可以证明T(n)=O(nlgn)。直观上，quicksort是一个递归数，其中PARTITION总是产生9:1除法，总运行时间为O(nlgn)。子问题的大小显示在每个节点中。每层的成本显示在右侧。每层包含一个常量c。===============================================请思考你自己的以下版本对应的是上面的哪个版本？HOARE-PARTITION(A,p,r)x←A[p]i←p-1j←r+1whileTRUEdorepeatj←j-1untilA[j]≤xrepeati←i+1untilA[i]≥xifi=u)return;swap(l,randint(l,u));m=l;for(i=l+1;i<=u;i++)if(x[i]
