转载 快速排序详细分析
快速排序详细分析
注：REF[n]为参考资料，列于文章结尾。
看了编程珠玑Programming Perls第11章关于快速排序的讨论，发现自己长年用库函数，已经忘了快排怎么写。于是整理下思路和资料，把至今所了解的快排的方方面面记录与此。
纲要
- 算法描述
- 时间复杂度分析
- 具体实现细节
- 划分
- 选取枢纽元
- 固定位置
- 随机选取
- 三数取中
- 分割
- 单向扫描
- 双向扫描
- Hoare的双向扫描
- 改进的双向扫描
- 双向扫描的其他问题
- 选取枢纽元
- 分治
- 尾递归
- 划分
- 参考文献
一、算法描述（Algorithm Description）
快速排序由C.A.R.Hoare于1962年提出，算法相当简单精炼，基本策略是随机分治。
首先选取一个枢纽元（pivot），然后将数据划分成左右两部分，左边的大于（或等于）枢纽元，右边的小于(或等于枢纽元)，最后递归处理左右两部分。
分治算法一般分成三个部分：分解、解决以及合并。快排是就地排序，所以就不需要合并了。只需要划分（partition）和解决（递归）两个步骤。因为划分的结果决定递归的位置，所以Partition是整个算法的核心。
对数组S排序的形式化的描述如下（REF[1]）:
- 如果S中的元素个数是0或1，则返回
- 取S中任意一元素v，称之为枢纽元
- 将S-{v}（S中其余元素），划分成两个不相交的集合：S1={x∈S-{v}|x<=v} 和 S2={x∈S-{v}|x>=v}
- 返回{quicksort(S1) , v , quicksort(S2)}
二、时间复杂度分析（Time Complexity）
快速排序最佳运行时间O(nlogn)，最坏运行时间Ｏ(N^2)，随机化以后期望运行时间O(nlogn)，关于这些任何一本算法数据结构书上都有证明，就不写在这了，一下两点很重要：
- 选取枢纽元的不同, 决定了快排算法时间复杂度的数量级；
- 划分方法的划分方法总是O(n), 所以其具体实现的不同只影响算法时间复杂度的系数。
所以诉时间复杂度的分析都是围绕枢纽元的位置展开讨论的。
三、具体实现细节（Details of Implementaion）
1、划分(Partirion)
void QuickSort(T A[], int p, int q)
{
if (p < q)
{
int q = Partition(A, p, q);
QuickSort(A, p, q-1);
QuickSort(A, q+1, r);
}
}
划分又分成两个步骤：选取枢纽元和按枢纽元将数组分成左右两部分
a.选取枢纽元（Pivot Selection）
固定位置
同样是为了方便，将选取枢纽元单独提出来成一个函数：select_pivot(T A[], int p, int q)，该函数从A[p...q]中选取一个枢纽元并返回，且枢纽元放置在左端（A[p]的位置）。
int select_pivot(T A[], int p, int q)
{
return A[p];
}
但是实际应用中，数据往往是部分有序的，如果仍用两端的元素最为枢纽元，则会产生很不好的划分，使算法退化成O(n^2)。所以要采用一些手段避免这种情况，我知道的有“随机选取法”和“三数取中法”。
随机选取
int select_pivot_random(T A[], int p, int q)
{
int i = randInt(p, q);
swap(A[p], A[i]);
return A[p];
}
其中randInt(p, q)随机返回[p, q]中的一个数，C/C++里可由stdlib.h中的rand函数模拟。
三数取中
即取三个元素的中间数作为枢纽元，一般是取左端、右断和中间三个数，也可以随机选取。（REF[1]）
int select_pivot_median3(T A[], int p, int q)
{
int m = (p + q)/2;
/* swap to ensure A[m] <= A[p] <= A[q] */
if (A[p] < A[m]) swap(A[p], A[m]);
if (A[q] < A[m]) swap(A[q], A[m]);
if (A[q] < A[p]) swap(A[q], A[p]);
return A[p];
}
b.按枢纽元将数组分成左右两部分
虽然说分割方法只影响算法时间复杂度的系数，但是一个好系数也是比较重要的。这也就是为什么实际应用中宁愿选择可能退化成O(n^2)的快速排序，也不用稳定的堆排序（堆排序交换次数太多，导致系数很大）。
常见的分割方法有三种：
单向扫描
int partition(T A[], int p, int q)
{
int x = select_pivot(A, p, q);
int m = p, j;
for (int j = p+1; j <= q; ++j)
/* invariant : A[p＋1...m] < A[p] && A[m+1, i-1] >= x[q] */
if (A[j] <= x)
swap(A[++m], j)
swap(A[p], A[m]);
/* A[p...m-1] < A[m] <= A[m+1...u] */
return m;
顺便废话几句，在看国外的书的时候，发现老外在分析和测试算法尤其是循环时，非常重视不变量（invariant）的使用。确立一个不变量，在循环开始之前和结束之后检查这个不变量，是一个很好的保持算法正确性的手段。
事实上第一种算法需要的交换次数比较多，而且如果采用选取左端元素作为枢纽元的方法，该算法在输入数组中元素全部相同时退化成O(n^2)。第二种方法可以避免这个问题。
双向扫描
int partition(T A[], int p, int q)
{
int x = select_pivot(A, p, q);
int i = p, j = q + 1;
for ( ; ; )
{
do ++i; while (i <= q && A[i] < x);
do --j; while (A[j] > x);
if (i > j) break;
swap(A[i], A[j]);
}
swap(A[p], A[j]);
return j;
}
双向扫描可以正常处理所有元素相同的情况，而且交换次数比单向扫描要少。
Hoare的双向扫描
int partition(T A[], int p, int q)
{
int x = select_pivot(A, p, q);
int i = p - 1, j = q + 1;
for ( ; ; )
{
do --j; while (A[j] > x);
do ++i; while (A[i] < x);
if (i < j) swap(A[i], A[j])
else return j;
}
}
需要注意的是，返回值j并不是枢纽元的位置，但是仍然保证了A[p..j] <= A[j+1...q]。这种方法在效率上于双向扫描差别甚微，只是代码相对更为紧凑，并且用A[p]做哨兵元素减少了内层循环的一个if测试。
改进的双向扫描
int partition(T A[], int p, int q)
{
int x = select_pivot(A, p, q);
int i = p, j = q;
for ( ; ; )
{
while (i < j && A[j] > x) --j;
A[i] = A[j];
while (i < j && A[i] < x) ++i;
A[j] = A[i];
}
A[i] = x; // i == j
return i;
}
这种类似迭代的方法，每次只需一次赋值，减少了内存读写次数，而前面几种的方法一次交换需要三次赋值操作。由于没有哨兵元素，不得不在内层循环里判断i、j是否相交，实际上反而增加了很多内存读取操作。但是由于循环计数器往往被放在寄存器了，而如果待排数组很大，访问其元素会频繁的cache miss，所以用计数器的访问次数换取待排数组的访存是值得的。
关于双向扫描的几个问题
1.内层循环中的while测试是用“严格大于/小于”还是”大于等于/小于等于”。
一般的想法是用大于等于/小于等于，忽略与枢纽元相同的元素，这样可以减少不必要的交换，因为这些元素无论放在哪一边都是一样的。但是如果遇到所有元素都一样的情况，这种方法每次都会产生最坏的划分，也就是一边1个元素，令一边n－1个元素，使得时间复杂度变成O(N^2)。而如果用严格大于/小于，虽然两边指针每此只挪动1位，但是它们会在正中间相遇，产生一个最好的划分，时间复杂度为log(2,n)。
另一个因素是，如果将枢纽元放在数组两端，用严格大于/小于就可以将枢纽元作为一个哨兵元素，从而减少内层循环的一个测试。
由以上两点，内层循环中的while测试一般用“严格大于/小于”。
2.对于小数组特殊处理
void QuickSort(T A[], int p, int q)
{
if (q - p > cutoff) //cutoff is constant
{
int q = Partition(A, p, q);
QuickSort(A, p, q-1);
QuickSort(A, q+1, r);
}
else
InsertionSort(T A[], p, q); //user insertion sort for small arrays
}
二、分治
分治这里看起来没什么可说的，就是一枢纽元为中心，左右递归，实际上也有一些技巧。
1.尾递归（Tail recursion）
void QuickSort(T A[], int p, int q)
{
while (p < q)
{
int m = Partition(A, p, q);
QuickSort(A, p, m-1);
p = m + 1;
}
}
采用这种方法可以缩减堆栈深度，由原来的O(n)缩减为O(logn)。
三、参考文献：
- [1]Mark Allen Weiss. Data Structures and Algorithms Analysis in C++. Pearson Education, Third Edition, 2006.
- [2]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. MIT Press, 2001, Second Edtion, 2001.
- [3]Jon Bently. Programming Pearls. Addison Wesley, Second Edition, 2000.
Aug 27, 2022 09:36:28 PM
Primary School Certificate Exam 2022 was successfully conducted by Directorate of the Primary Education (DPE) is going to announce PSC Result 2022 with Full Mark sheet for all students under Barisal Board, and they have conducted those Grade 5 Public exams between 17th to 24th November 2022 at all centers in the division. Grade 5 Result Barisal Board The Director General of the Directorate of Primary Education (DPE) is going to announce the PSC Result 2022 Barisal Board with full Mark sheet known as Prathomik Somaponi Result 2022 by Barisal Division, Minister of Education will be announced the grade 5 exam result in student wise for all schools under the division with merit and toppers lists also.
Jul 18, 2023 10:33:23 PM
Wenn das Layout des Startbildschirms gesperrt ist, werden Änderungen an jedem Startbildschirm verhindert, nicht nur am ersten oder Standardbildschirm. Sie können weiterhin zwischen Startbildschirmen navigieren; das Gerät wird dadurch nicht gesperrt. android startbildschirm layout entsperren Wenn Sie neue Apps installieren, werden jedoch keine Symbole auf Ihrem Startbildschirm platziert. Bis Ihr Startbildschirm entsperrt ist, sieht es so aus.
Jul 22, 2023 11:32:07 PM
Netflix bietet eine Reihe von Filmen, Fernsehsendungen und Originalinhalten für ein angemessenes monatliches Abonnement. Netflix kann auf Smart TV, Streaming-Geräten oder modernen Spielsystemen mit Internetverbindung angezeigt werden. netflix.com/tv8 Bei einigen Geräten müssen Sie das Gerät aktivieren, bevor Sie sich anmelden. Dies ist üblich bei neuen Geräten oder solchen, die gerade Softwareänderungen erhalten haben.
Aug 22, 2023 07:26:37 PM
Gujarat Board Primary School Academic Year Close in Every Year Month of April, Gujarat Board Elementary School new Academic Year Open in Every Year Month of Jun, Every Year Gujarat State Wise Class More Than 50 Laks of Students Attended, Every Year Primary School Education Department Government of Gujarat Distribution in Textbook in Gujarati / English / Hindi Medium.The Printed Gujarat Class GSSTB 1st Class Book 2024 Textbook 2024 are Distributed Through Cooperative Institutions All over Gujarat. Vendors are Linked to the Distribution of Textbooks with Distributors in each District. Gujarat Board Class Book 2024 are easily Accessible to All Students of This System, This will assist in improving the Quality of Teaching by Understanding the Type of Difficulties Faced by Students.
Nov 01, 2023 06:51:18 PM
For a long time me & my friend were searching for informative blogs, but now I am on the right place guys, you have made a room in my heart!
Nov 06, 2023 10:40:55 PM
You have a good point here! I totally agree with what you have said !! Thanks for sharing your views ... hope more people will read this article
Nov 06, 2023 11:12:58 PM
Admiring the time and effort you put into your blog and detailed information you offer!..
Nov 07, 2023 04:17:22 PM
youre saying and want more, more, MORE! Keep this up,
Nov 07, 2023 09:23:53 PM
Trying to say thank you won't simply be adequate, for the astonishing lucidity in your article. I will legitimately get your RSS to remain educated regarding any updates. Wonderful work and much accomplishment in your business endeavors
Nov 08, 2023 07:18:07 PM
The next time I read a blog, I hope that it doesnt disappoint me as much as this one. I mean, I know it was my choice to read, but I actually thought you have something interesting to say. All I hear is a bunch of whining about something that you could fix if you weren't too busy looking for attention
Nov 09, 2023 02:35:51 PM
I know it was my choice to read, but I actually thought you have something inter
Nov 09, 2023 02:48:25 PM
Nice blog. Found this while searching through
Nov 09, 2023 05:07:13 PM
I think this is an informative post and it is very useful and knowledgeable. Therefore, I would like to thank you for the efforts you have made in writing this article.
Nov 09, 2023 05:13:44 PM
THanks for sharing
Nov 09, 2023 07:51:53 PM
It is a good site post without fail. Not too many people much quality. Good Works!
Nov 09, 2023 08:48:21 PM
There is definately a great deal to know about this subject. I like all of the points you've made
Nov 09, 2023 09:17:48 PM
Very informative post ! There is a lot of information here that can help any business get started with a successful social networking campaign
Nov 12, 2023 05:27:28 PM
Wow, superb blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your site is magnificent, as well as the content!
Nov 13, 2023 04:57:23 PM
Wow, superb blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your site is magnificent, as well as the content!
Nov 14, 2023 04:35:02 PM
솔직히 말해서 스타일로 글을 쓰고 좋은 칭찬을받는 것은 꽤 어렵지만, 너무 차분하고 시원한 느낌으로 해냈고 당신은 일을 잘했습니다. 이 기사는 스타일이 돋보이며 좋은 칭찬을하고 있습니다. 베스트! <a href="https://ajslaos.shop/">머니맨</a>
Nov 14, 2023 08:23:34 PM
This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free
Nov 15, 2023 05:34:40 PM
Hi buddies, it is great written piece entirely defined, continue the good work constantl
Nov 16, 2023 11:00:42 PM
Wow i can say that this is another great article as expected of this blog.Bookmarked this site.. <a href="https://www.bazanos.com/">메이저사이트</a>
Dec 05, 2023 02:36:29 PM
Nice to be visiting your blog once more, it has been months for me. Well this article that ive been waited for therefore long. i want this article to finish my assignment within the faculty, and it has same topic together with your article. Thanks, nice share
Dec 05, 2023 03:32:31 PM
I’ve recently started a site, the information you provide on this site has helped me tremendously. Thanks for all of your time & work.
Dec 05, 2023 03:57:57 PM
The following appears to be like unquestionably fantastic. Almost all these minor points are built by using number of foundation awareness. I enjoy them considerably
Dec 05, 2023 04:06:33 PM
Have you experienced any of the best online verification companies that currently exist? Visit my website now and get various information
Dec 05, 2023 04:19:08 PM
Hello, you used to write excellent, but the last few posts have been kinda boring… I miss your super writings. Past several posts are just a little out of track! come on!
Dec 05, 2023 04:31:39 PM
Admiring the time and effort you put into your website and in depth information you present. It’s good to come across a blog every once in a while that isn’t the same old rehashed information. Wonderful read! I’ve bookmarked your site and I’m adding your RSS feeds to my Google account.
Dec 05, 2023 04:48:01 PM
Water-resistant our wales in advance of when numerous planking.
Dec 05, 2023 05:01:28 PM
Hello, you used to write excellent, but the last few posts have been kinda boring… I miss your super writings. Past several posts are just a little out of track! come on!
Dec 05, 2023 05:03:41 PM
I am glad that it turned out so well and I hope it will continue in the future because it is so worthwhile and meaningful to the community.
Dec 05, 2023 05:37:49 PM
The following appears to be like unquestionably fantastic. Almost all these minor points are built by using number of foundation awareness. I enjoy them considerably
Dec 05, 2023 06:29:33 PM
Great weblog here! Also your web site lots up very fast! What host are you the usage of? Can I am getting your affiliate hyperlink for your host? I want my web site loaded up as fast as yours lol.
Dec 05, 2023 06:31:51 PM
You actually make it look so easy with your performance but I find this matter to be actually something which I think I would never comprehend. It seems too complicated and extremely broad for me. I'm looking forward for your next post, I’ll try to get the hang of it!
Dec 05, 2023 06:52:22 PM
Hey there, You’ve done an incredible job. I will certainly digg it and personally suggest to my friends. I am confident they will be benefited from this site.
Dec 05, 2023 07:03:10 PM
You actually make it look so easy with your performance but I find this matter to be actually something which I think I would never comprehend. It seems too complicated and extremely broad for me. I'm looking forward for your next post, I’ll try to get the hang of it!
Dec 05, 2023 07:22:22 PM
It's evident that you've invested time and thought into your comment, and it greatly enriches the discussion. Thank you for sharing your knowledge and perspective with us.
Dec 05, 2023 07:43:55 PM
This blog is really awesome. At first, I lightly browsed your blog, but the more I read, the more valuable articles I see. I love reading your writing. Many people are looking for topics related to your writing, so it will be very helpful.
Dec 05, 2023 07:50:34 PM
Great weblog here! Also your web site lots up very fast! What host are you the usage of? Can I am getting your affiliate hyperlink for your host? I want my web site loaded up as fast as yours lol.
Dec 05, 2023 08:02:32 PM
This blog is really awesome. At first, I lightly browsed your blog, but the more I read, the more valuable articles I see. I love reading your writing. Many people are looking for topics related to your writing, so it will be very helpful.
Dec 05, 2023 08:23:26 PM
You have performed a great job on this article. It’s very precise and highly qualitative. You have even managed to make it readable and easy to read. You have some real writing talent. Thank you so muc
Dec 05, 2023 08:33:57 PM
This is often likewise a superb subject material i actually fairly seriously favored reviewing. It isn't really everyday we hold possibilities to clear up a dilemma.
Dec 05, 2023 08:39:17 PM
You have performed a great job on this article. It’s very precise and highly qualitative. You have even managed to make it readable and easy to read. You have some real writing talent. Thank you so muc
Dec 05, 2023 09:21:53 PM
I’m honored to obtain a call from a friend as he identified the important tips shared on your site. Browsing your blog post is a real excellent experience. Many thanks for taking into consideration readers at all like me, and I wish you the best of achievements as being a professional domain.
Dec 05, 2023 09:22:41 PM
Wow! This could be one of the most useful blogs we have ever come across on thesubject. Actually excellent info! I’m also an expert in this topic so I can understand your effort.
Dec 05, 2023 09:30:29 PM
Everyone is well aware of the importance of safety when it comes to online sports betting. My website has a lot of useful sports news information, check it out now
Dec 05, 2023 09:34:32 PM
Hey there, You’ve done an incredible job. I will certainly digg it and personally suggest to my friends. I am confident they will be benefited from this site.
Dec 05, 2023 09:51:14 PM
I am glad that it turned out so well and I hope it will continue in the future because it is so worthwhile and meaningful to the community.
Dec 05, 2023 10:03:45 PM
That definitely possibly an amazing organize i always in truth definitely relished checking out. It's not necessarily specifically frequent i always add some choice to identify a selected matter.
Dec 05, 2023 10:06:30 PM
This is often likewise a superb subject material i actually fairly seriously favored reviewing. It isn't really everyday we hold possibilities to clear up a dilemma.
Dec 05, 2023 10:19:44 PM
I came to this site with the introduction of a friend around me and I was very impressed when I found your writing. I'll come back often after bookmarking!
Dec 05, 2023 10:19:47 PM
This is why it is far better that you can pertinent analysis ahead of producing. It will be possible to post greater article using this method.
Dec 05, 2023 10:38:54 PM
Hello – I must say, I’m impressed with your site. I had no trouble navigating through all the tabs and information was very easy to access. I found what I wanted in no time at all. Pretty awesome. Would appreciate it if you add forums or something, it would be a perfect way for your clients to interact. Great job
Dec 05, 2023 10:49:33 PM
Hey there, You’ve done an incredible job. I will certainly digg it and personally suggest to my friends. I am confident they will be benefited from this site.
Dec 05, 2023 10:56:45 PM
In today’s fast-paced and competitive business environment, headhunters play a vital role in helping organizations secure the right talent to lead and drive success. Their expertise, industry knowledge, and extensive networks are invaluable assets in modern talent acquisition. As the business landscape continues to change, the role of headhunters is likely to become even more critical in connecting organizations with top-level candidates
Dec 05, 2023 10:58:31 PM
I am glad that it turned out so well and I hope it will continue in the future because it is so worthwhile and meaningful to the community.
Dec 05, 2023 11:18:59 PM
Normally I don’t read article on blogs, but I would like to say that this write-up very forced me to try and do it! Your writing style has been surprised me. Thanks, quite nice article.
Dec 14, 2023 06:54:19 PM
주목할만한 기사, 특히 유용합니다! 나는 이것에서 조용히 시작했고 더 잘 알게되고 있습니다! 기쁨, 계속해서 더 인상적
Dec 28, 2023 08:42:39 PM
I am hoping the same best effort from you in the future as well. In fact your creative writing skills has inspired me.
Jan 04, 2024 09:37:37 PM
Good to become visiting your weblog again, it has been months for me. Nicely this article that i've been waited for so long. I will need this post to total my assignment in the college, and it has exact same topic together with your write-up. Thanks, good share
Jan 07, 2024 04:25:16 PM
나는 이것을 읽을 것이다. 다시 올게요. 공유해 주셔서 감사합니다. 그리고이 기사는 우리가 현실을 관찰 할 수있는 빛을 제공합니다. 이것은 매우 좋은 것이며 심층적 인 정보를 제공합니다. 이 멋진 기사에 감사드립니다 ..
Jan 09, 2024 01:18:18 AM
JNANABHUMI AP provides a CBSE syllabus for all classes for the academic year 2024 has been designed as per the guidelines of the CBSE Board. The syllabus offers a conceptual background and lays the groundwork for the Class 10 Board exams. jnanabhumiap.in By visiting the page, students will find the downloadable pdf of the reduced CBSE 10th Syllabus along with the deleted portion of the syllabus for each subject. So, students are advised to prepare for the exam, as per the syllabus mentioned here.
Jan 11, 2024 03:09:03 PM
이 기사를 읽었습니다. 이 기사를 만들기 위해 많은 노력을 기울인 것 같습니다. 나는 당신의 일을 좋아합니다.
Jan 15, 2024 05:02:50 PM
Excellent and very exciting site. Love to watch. Keep Rocking.
Jan 15, 2024 10:06:08 PM
This is an excellent post I seen thanks to share it. It is really what I wanted to see hope in future you will continue for sharing such a excellent post.
Jan 15, 2024 10:27:06 PM
Such a very useful article. Very interesting to read this article. I would like to thank you for the efforts you had made for writing this awesome article.
Jan 15, 2024 10:45:49 PM
Wow, that is an thrilling hand-crafted event. It is a splendid enjoyment pastime to make the maximum of some time and also slotxo can be used as a present for one of a kind occasions. It is likewise very famous at this time.
Jan 16, 2024 04:55:03 PM
was surfing the Internet for information and came across your blog. I am impressed by the information you have on this blog. It shows how well you understand this subject.
Jan 16, 2024 05:58:06 PM
Hi, I log on to your new stuff like every week. Your humoristic style is witty, keep it up
Jan 16, 2024 10:07:24 PM
I have read your article, it is very informative and helpful for me. I admire the valuable information you offer in your articles. Thanks for posting it
Jan 20, 2024 08:11:50 PM
Pavzi website is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. pavzi.com We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.