快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采 用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考 试如软考,考研中也常常出现快速排序的身影。
总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话解释,希望对大家理解有帮助,达到快速排序,快速搞定。
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明:挖坑填数+分治法:
先来看实例吧,定义下面再给出(最好能用自己的话来总结定义,这样对实现代码会有帮助)。
以一个数组作为示例,取区间第一个数为基准数。
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
72 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
48 |
85 |
初始时,i = 0; j = 9; X = a[i] = 72
由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。
从 j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当 i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;
数组变为:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
48 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
88 |
85 |
i = 3; j = 7; X=72
再重复上面的步骤,先从后向前找,再从前向后找。
从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;
从i开始向后找,当i=5时,由于i==j退出。
此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。
数组变为:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
48 |
6 |
57 |
42 |
60 |
72 |
83 |
73 |
88 |
85 |
可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
对挖坑填数进行总结
1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。
照着这个总结很容易实现挖坑填数的代码:
int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置 { int i = l, j = r; int x = s[l]; //s[l]即s[i]就是第一个坑 while (i < j) { // 从右向左找小于x的数来填s[i] while(i < j && s[j] >= x) j--; if(i < j) { s[i] = s[j]; //将s[j]填到s[i]中,s[j]就形成了一个新的坑 i++; } // 从左向右找大于或等于x的数来填s[j] while(i < j && s[i] < x) i++; if(i < j) { s[j] = s[i]; //将s[i]填到s[j]中,s[i]就形成了一个新的坑 j--; } } //退出时,i等于j。将x填到这个坑中。 s[i] = x; return i; }
再写分治法的代码:
void quick_sort1(int s[], int l, int r) { if (l < r) { int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[] quick_sort1(s, l, i - 1); // 递归调用 quick_sort1(s, i + 1, r); } }
这样的代码显然不够简洁,对其组合整理下:
//快速排序 void quick_sort(int s[], int l, int r) { if (l < r) { //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) // 从右向左找第一个小于x的数 j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // 递归调用 quick_sort(s, i + 1, r); } }
快速排序还有很多改进版本,如随机选择基准数,区间内数据较少时直接用另的方法排序以减小递归深度。有兴趣的筒子可以再深入的研究下。
注1,有的书上是以中间的数作为基准数的,要实现这个方便非常方便,直接将中间的数和第一个数进行交换就可以了。
转载请标明出处,原文地址:http://blog.csdn.net/morewindows/article/details/6684558
相关推荐
快速排序是一种高效的排序算法,由C.R.A.Hoare在1962年提出。它基于分治策略,但其完整流程可以更准确地描述为“挖坑填数+分治法”。快速排序的核心思想是通过选取一个基准数,将数组分为两部分:一部分的所有元素都...
本书《更多Windows白话经典算法之七大排序第2版》是一部深入浅出讲解七种经典排序算法的著作,旨在帮助读者理解并掌握冒泡排序、直接插入排序、直接选择排序、希尔排序、归并排序、快速排序以及堆排序等基本概念和...
### 白话经典算法之七大排序 #### 一、冒泡排序 冒泡排序是一种简单直观的排序算法,它的基本思想是从第一个元素开始,比较相邻元素的大小,如果前一个元素大于后一个元素则交换它们的位置,这样一轮比较下来,...
《白话经典算法之七大排序》是一本专为初学者设计的算法教程,旨在通过简单易懂的语言,帮助读者深入浅出地理解并掌握七大排序算法。这些排序算法是计算机科学与信息技术领域的基础,对于提升编程能力和解决实际问题...
冒泡排序是最简单的排序算法之一,它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的...
在第一版的基础上新加了对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法的总结篇,方便大家复习,合适作为笔试面试前的复习资料。
《MoreWindows白话经典算法之七大排序》是针对计算机编程中的一个重要主题——排序算法的一份详细解析。排序算法是计算机科学的基础,对于任何处理数据的软件系统来说,无论是数据分析、数据库管理还是图形用户界面...
本文将详细解析七种经典的排序算法:冒泡排序、直接插入排序、直接选择排序、希尔排序、归并排序、快速排序以及堆排序。这些算法对于程序员来说至关重要,无论是在日常开发还是在面试中,都是常被问及的知识点。 1....
本资源"MoreWindows白话经典算法之七大排序(高清版).pdf"提供了一套详尽的排序算法讲解,涵盖了七大经典的排序算法。以下是这些排序算法的详细介绍: 1. 冒泡排序(Bubble Sort): 冒泡排序是一种简单的交换排序,...
以上就是对直接选择排序、希尔排序、归并排序、快速排序以及堆排序这五大经典排序算法的介绍。每种排序算法都有其特点和应用场景,了解它们的工作原理可以帮助我们在实际编程中做出更加合理的选择。接下来的文章中将...
### 数据结构与排序算法详解 ...当数据量较大时,这两种算法的性能会下降,此时应考虑使用更高效的排序算法,如快速排序、归并排序等。在实际应用中,了解各种排序算法的特点,选择最适合当前场景的算法至关重要。
《白话算法(理论联系实际)-初探遗传算法接近完美》是针对计算机科学中的优化算法——遗传算法的一次深入浅出的探讨。遗传算法是一种模拟自然选择和遗传机制的搜索算法,它以其独特的非确定性、全局搜索能力和适应性...
总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话解释,希望对大家理解有帮助,达到快速排序,快速搞定。 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用...
标题中的"白话经典控制理论"告诉我们,本文将采用通俗易懂的语言来介绍控制理论,避免了复杂的数学表达和难以理解的术语,使没有专业背景的读者也能理解控制理论的基本概念。 描述部分进一步强调,本文的目的是普及...
#### 六、快速排序 快速排序是一种高效的排序算法,同样采用分而治之的策略,通过选择一个基准元素来分割数组。 **基本步骤**: 1. 选择一个基准元素。 2. 将小于基准的所有元素放在基准左边,大于基准的所有元素...
基于python实现的机器学习各种经典算法,你能想到的都有基于python实现的机器学习各种经典算法,你能想到的都有基于python实现的机器学习各种经典算法,你能想到的都有基于python实现的机器学习各种经典算法,你能...