快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
不说废话,我们先看代码,然后举个具体例子进行分析。
package chapter7;
import java.util.Arrays;
public class QuickSort {
public void sort(int a[],int l,int r){
if(l<r){
int q=partition1(a,l,r);
sort(a,l,q);
sort(a,q+1,r);
}
}
public void sort(int a[]){
sort(a,0,a.length-1);
}
private int partition1(int a[],int i,int j)
{
int key=a[(i+j)/2];
while(i<j){
while(i<j&&a[i]<key){
i++;
}
while(i<j&&a[j]>key){
j--;
}
if(i<=j){
swap(a,i,j);
j--;
}
}
//System.out.printf("(key=%d,i=%d,j=%d\n,array=%s)\n",key,i,j,Arrays.toString(a));
return i;
}
private void swap(int[] a, int i, int j) {
int t=a[i];
a[i]=a[j];
a[j]=t;
}
public static void main(String[] args) {
int a[]={8,5,7,2,19,3};
System.out.println("Before "+Arrays.toString(a));
QuickSort qs=new QuickSort();
qs.sort(a);
System.out.println("After "+Arrays.toString(a));
}
}
对于数组A[0,r]存在分割点p,使得A[0,p]有序,同时A[p+1,r]有序,并且A[0,p]<=A[p]<=A[p+1,r] 。
我们来看看数组a=[8,5,7,2,19,3]是如何进行快速排序的。
具体代码:
private int partition1(int a[],int i,int j)
{
int key=a[(i+j)/2];
while(i<j){
while(i<j&&a[i]<key){
i++;
}
while(i<j&&a[j]>key){
j--;
}
if(i<=j){
swap(a,i,j);
j--;
}
}
//System.out.printf("(key=%d,i=%d,j=%d\n,array=%s)\n",key,i,j,Arrays.toString(a));
return i;
}
- 获取分割点坐标值i
- 对a[0,i]和a[i+1,length]进行递归排序
令key=a[2]=7
第一趟获取分割点:
- i=0,j=5, a[i]=8,a[j]=3,key=7,因为a[i]>key同时a[j]<key 直接交换i,j的值,j向数组左移动 数组A=[3,5,7,2,19,8]
- i=0,j=4, a[i]=3,a[j]=19,key=7 a[i]<key 那么指针i向右移动 知道i=2
- i=2,j=4, a[i]=7,a[j]=19,key=7 a[i]=key同时a[j]>key ,指针i不移动,指针j继续向左移动
- i=2,j=3, a[i]=7,a[j]=2 ,key=7 a[i]=key同时a[j]<key,因此指针i不移动,指针j继续向左移动,同时交换i,j的值,此时A=[3,5,2,7,19,8]
- i=2,j=2 跳出循环,返回分割点的值为i=2 即完成第一趟分割 。此时A=[3,5,2,7,19,8]
- 由于i=j=2,结束递归条件,函数执行完成。
第二趟获取分割点:
- 此时快速排序递归调用sort(a,0,p) ,p=2 ,获取数组A‘=[3,5,2]
- i=0,j=2,Key=a[1]=5 因为a[i]=3<5 因此 指针i向右移动直到i=1,此时j=2
- i=1,j=2,key=5, a[i]=5,a[j]=2 ,因为a[j]<key,因此交换i,j的值,并将指针j向左移动,此时A’=[3,2,5],A=[3,2,5,7,19,8]
- i=1,j=1,跳出循环,返回分割点的值为i=1,完成第二趟分割。此时A=[3,2,5,7,19,8]
- 由于i=j=1,结束递归条件,函数执行完成。
第三趟获取分割点:
- 此时快速排序递归调用sort(a,0,p),p=1,令数组A2=[3,2]
- i=0,j=1 key=a[0]=3 a[i]=3=key,所以指针i不移动,a[j]=2<key,因此需要交换i,j的值,然后将指针j向左移动,此时A2=[2,3]
- i=0,j=0 跳出循环,返回分割点的值为i=0,完成第三趟分割。此时A=[2,3,5,7,19,8]
- 由于i=j=0,结束递归条件,函数执行完成。
第四趟获取分割点:
- 此时快速排序递归调用sort(a,p+1,r),p=2,令数组A3=[19,8]
- i=4,j=5 ,key=a[4]=19,a[i]=19,因为a[i]=key,因此指针i不移动,a[j]=8<key,因此需要交换i,j的值,同时j向做移动。此时A3=[8,9]
- i=4,j=4 跳出循环,返回分割点i=4,完成第四趟获取分割点。此时A=[2,3,5,7,8,19]
- 由于i=j=4,结束递归条件,函数执行完成。
由此我们可以很清晰的知道快速排序的工作原理,关键函数是获取分割点,同时应该注意边界问题。
欢迎各位拍砖
分享到:
相关推荐
而“算法导论第三版课后答案-2-25章(部分中文).pdf”则是针对该书前25章的部分课后习题解答。课后习题是理解和掌握书本知识的关键,通过解题,读者可以检验自己的理解程度,加深对算法原理的记忆。这份中文解答...
通过深入学习和解决《算法导论》第二十四章的习题,你将能更好地掌握高级算法和数据结构,这对任何IT专业人员来说都是宝贵的技能。记住,实践是检验理论的最好方式,不断练习和应用这些知识,将使你在面对实际问题时...
《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了各种重要的算法,并配以详尽的分析和实例。这份压缩包文件包含了该书第1至16章的部分编程题目的Java实现,对于学习算法和提高编程技能来说,是一个...
总的来说,这份"算法导论第二版课后答案中文完全版"是学习者不可或缺的工具,它能帮助读者更好地理解和掌握《算法导论》中的知识点,提升分析和解决问题的能力,对于准备面试、提升编程技能或者进行学术研究都...
**第七章:快速排序** - **主要内容**:介绍了快速排序算法,这是实际应用中最常用的排序算法之一。 - **关键概念**: - **分区操作**:将数组分为两个子序列的过程。 - **递归调用**:对子序列继续进行快速...
第七章讲述了快速排序算法,这是一种非常高效的排序方法。例如,习题7.1-1至7.1-4介绍了快速排序的基本概念。习题7.2-1至7.2-6则讨论了快速排序的不同变体。习题7.3-1至7.3-2涉及了如何分析快速排序的平均性能。 ##...
在《算法导论》中,知识点涵盖了基础数据结构(如数组、链表、栈、队列、树和图)、排序与搜索算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序、二分查找、哈希表等)、图算法(如最短路径算法Dijkstra、...
第七章 快速排序(Quicksort) 第八章 线性时间中的排序(Sorting in Linear Time) 第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构(Data Structures) 第十章 ...
3. **第4章:分治策略** - 分治是一种将大问题分解为小问题求解的方法,如快速排序、归并排序等高效算法。习题可能涉及如何设计和分析分治算法的效率。 4. **第5章:数据结构** - 数据结构是算法的基础,包括数组、...
### 第7章:快速排序 #### 7.1 快速排序概念 - **7.1-1**至**7.1-4**:介绍了快速排序的基本思想及其算法流程。 #### 7.2 快速排序实例 - **7.2-1**至**7.2-6**:通过具体的实例展示了快速排序算法的工作原理。 #...
#### 第7章:快速排序 - **主要内容**:介绍另一种重要的排序算法——快速排序。 - **重点知识点**: - 快速排序的分治策略。 - 不同划分方法的选择和实现。 - 最优情况、最坏情况和平均情况下的时间复杂度分析...
- **快速排序(Quick Sort)**:章节7讲解了快速排序算法,通过选择一个基准元素,将数组分为小于和大于基准的两部分,递归地进行排序。快速排序平均时间复杂度同样为O(n log n),但在最坏情况下退化为O(n^2)。 ###...
第七章,"图算法",会介绍图的表示方法(邻接矩阵和邻接表),以及Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法、Prim最小生成树算法和Kruskal最小生成树算法等。 第八章,"动态规划",讲解了动态规划...
- **第7章:快速排序** - **主题**:介绍快速排序算法及其变种。 - **核心知识点**:分区操作、递归实现、性能分析。 - **第8章:线性时间排序** - **主题**:讨论在特定条件下可以达到线性时间复杂度的排序算法...
##### 第7章:快速排序 - **知识点**: - 快速排序的基本思想。 - 不同的划分策略对快速排序性能的影响。 - 快速排序的时间复杂度分析。 - **解决方案**: - 了解快速排序的工作原理及其与其他排序算法的区别。 ...