`
kingj
  • 浏览: 425253 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

算法导论学习之第七章-快速排序

 
阅读更多

      快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

      不说废话,我们先看代码,然后举个具体例子进行分析。


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

      第一趟获取分割点:
  1.  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]
  2.  i=0,j=4,  a[i]=3,a[j]=19,key=7  a[i]<key 那么指针i向右移动 知道i=2
  3.  i=2,j=4,  a[i]=7,a[j]=19,key=7 a[i]=key同时a[j]>key ,指针i不移动,指针j继续向左移动
  4.  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]
  5.  i=2,j=2 跳出循环,返回分割点的值为i=2 即完成第一趟分割 。此时A=[3,5,2,7,19,8]
  6. 由于i=j=2,结束递归条件,函数执行完成。
     第二趟获取分割点:
  1. 此时快速排序递归调用sort(a,0,p) ,p=2 ,获取数组A‘=[3,5,2]
  2. i=0,j=2,Key=a[1]=5  因为a[i]=3<5 因此 指针i向右移动直到i=1,此时j=2
  3. 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]
  4. i=1,j=1,跳出循环,返回分割点的值为i=1,完成第二趟分割。此时A=[3,2,5,7,19,8]
  5. 由于i=j=1,结束递归条件,函数执行完成。
    第三趟获取分割点:
  1. 此时快速排序递归调用sort(a,0,p),p=1,令数组A2=[3,2]
  2. i=0,j=1 key=a[0]=3 a[i]=3=key,所以指针i不移动,a[j]=2<key,因此需要交换i,j的值,然后将指针j向左移动,此时A2=[2,3]
  3. i=0,j=0 跳出循环,返回分割点的值为i=0,完成第三趟分割。此时A=[2,3,5,7,19,8]
  4. 由于i=j=0,结束递归条件,函数执行完成。
   第四趟获取分割点:
  1. 此时快速排序递归调用sort(a,p+1,r),p=2,令数组A3=[19,8]
  2. 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]
  3. i=4,j=4 跳出循环,返回分割点i=4,完成第四趟获取分割点。此时A=[2,3,5,7,8,19]
  4. 由于i=j=4,结束递归条件,函数执行完成。    

 

     由此我们可以很清晰的知道快速排序的工作原理,关键函数是获取分割点,同时应该注意边界问题。

    欢迎各位拍砖


分享到:
评论

相关推荐

    算法导论第三版及2-25章部分答案

    而“算法导论第三版课后答案-2-25章(部分中文).pdf”则是针对该书前25章的部分课后习题解答。课后习题是理解和掌握书本知识的关键,通过解题,读者可以检验自己的理解程度,加深对算法原理的记忆。这份中文解答...

    算法导论第二十四章习题解答

    通过深入学习和解决《算法导论》第二十四章的习题,你将能更好地掌握高级算法和数据结构,这对任何IT专业人员来说都是宝贵的技能。记住,实践是检验理论的最好方式,不断练习和应用这些知识,将使你在面对实际问题时...

    算法导论第1-16章编程题答案

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了各种重要的算法,并配以详尽的分析和实例。这份压缩包文件包含了该书第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**:通过具体的实例展示了快速排序算法的工作原理。 #...

    算法导论及课后习题与思考题答案.pdf

    #### 第7章:快速排序 - **主要内容**:介绍另一种重要的排序算法——快速排序。 - **重点知识点**: - 快速排序的分治策略。 - 不同划分方法的选择和实现。 - 最优情况、最坏情况和平均情况下的时间复杂度分析...

    算法导论--教师手册

    - **快速排序(Quick Sort)**:章节7讲解了快速排序算法,通过选择一个基准元素,将数组分为小于和大于基准的两部分,递归地进行排序。快速排序平均时间复杂度同样为O(n log n),但在最坏情况下退化为O(n^2)。 ###...

    算法导论中英文答案详解

    第七章,"图算法",会介绍图的表示方法(邻接矩阵和邻接表),以及Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法、Prim最小生成树算法和Kruskal最小生成树算法等。 第八章,"动态规划",讲解了动态规划...

    算法导论(第二版)teacher's book

    - **第7章:快速排序** - **主题**:介绍快速排序算法及其变种。 - **核心知识点**:分区操作、递归实现、性能分析。 - **第8章:线性时间排序** - **主题**:讨论在特定条件下可以达到线性时间复杂度的排序算法...

    算法导论(课后答案)

    ##### 第7章:快速排序 - **知识点**: - 快速排序的基本思想。 - 不同的划分策略对快速排序性能的影响。 - 快速排序的时间复杂度分析。 - **解决方案**: - 了解快速排序的工作原理及其与其他排序算法的区别。 ...

Global site tag (gtag.js) - Google Analytics