/*
* 快速排序学习:
今天我学习了快速排序,顾名思义,快速排序的速度是很快的,平均复杂度是nlogn,我也不知道是怎么算出来的,反正 T(n) = 2T(n/2) + o(n) 这样怎么怎么推到就成了nLogn了,呵呵,有空去学习一下。希望会的人可以教我,我数学太烂了。废话少说,记录一下快速排序的思路:
1.分治的思想,把数组分成两份,两份分成4分,这样分到足够小,就能很好排序咯,然后把他们合起来,排序完成。
2.该分治思想和合并排序思想一样,但是处理上更搞一筹,他是把小的和大的分成两份,这样在最后合并的时候,就不会像合并排序那样还要检查,因为本来就是左边比右边小,所以可以做到原地排序(就是不用申请多余的空间)。
3.如何做好把小和大的分开时关键,我们做的就是以一个数位基准,然后找到这个数的位置。把比他小的放在他的左边,比他大的放在他的右边,这样不就分开了嘛。
4.具体怎么分时一个最关键的地方,本来想用图说明一下,但是自己不会画:作罢,试着语言整理一下,呵呵:
例如,开始把最后一个作为标准,用一个循环j = nBegin j < nEnd一一比较,这样就能判断到底谁比他大,谁比他小咯。
注意:为了能清楚知道区域,所以要用一个变量i来保存它的标志,i的左边是比他小的,i的右边是比他大的。有了这个标志我们就好处理了。比较就好处理咯。
遇到小的,要把他方在i的左边,所以我们把他和i+1的元素交换,因为i+1得元素是大于x的,交换之后i+1就小于x了,这样我们把i也加1,不就有保证了i的左边都比x小,右边都比x大了嘛。呵呵。
遇到大的,不用管他。I也不用变。
比较完了,这时情况就是i的左边都比x小,i的右边都比x大,x在最后面。怎么处理呢?还不简单,有重复一下i + 1与 x交换,这样处理之后,i + 1就是保存的x值,i + 1的右边都比x大,i+1的左边都比x小,哈哈,i+1就是分割点咯。搞定。。
找出分割点后还不分而治之。。分而治之的时候发现分割点是排好的,只需排序nBegin - 分割点-1, 分割点+1 - nEnd 就可以咯。
最后还是截张《算法导论》书中的图:
(quickSortImage.jpg)
*/
/*
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只减少1。快速排序通过一趟扫描,就能确保某个数(以它为基准点吧)的左边各数都比它小,右边各数都比它大。然后又用同样的方法处理它左右两边的数,直到基准点的左右只有一个元素为止。
快速排序是不稳定的,最理想情况算法时间复杂度O(nlog2n),最坏O(n ^2)。
*/
public static void quickSort(int[] array,int start,int end) {
System.out.println("start:"+start+",end:"+end);
if(start<end) {
int key=array[start];//初始化保存基元
int i=start,j;//初始化i,j
for(j=start+1;j<=end;j++) {
if(array[j]<key) {//如果此处元素小于基元,则把此元素和i+1处元素交换,并将i加1,如大于或等于基元则继续循环
int temp=array[j];
array[j]=array[i+1];
array[i+1]=temp;
i++;
}
}
array[start]=array[i];//交换i处元素和基元
array[i]=key;
quickSort(array, start, i-1);//递归调用
quickSort(array, i+1, end);
}
}
分享到:
相关推荐
### 快速排序知识点解析 #### 一、快速排序简介 快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它采用分治策略来把一个序列分为较小和较大的两个子序列,然后递归地...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录...
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
快速排序是一种高效的排序算法,在计算机科学和数学中被广泛研究。其基本原理是分治法策略,即将一组数据分为两个子序列并分别进行排序。快速排序期望的时间复杂度为O(nlogn),但在最坏的情况下,它的时间复杂度可...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),即把一个大问题分解成若干个小问题来解决,最终将小问题的结果合并得到原问题的解。在这...
本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法,通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治策略,通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再...
(1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的...
冒泡排序和快速排序的时间性能 冒泡排序和快速排序是两种常用的排序算法,它们的时间性能是开发者和研究人员所关心的热点话题。在本文中,我们将对冒泡排序和快速排序的时间性能进行深入分析和比较。 冒泡排序是一...
快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔于1960年提出。它采用分治策略来把一个序列分为较小的两个子序列,然后递归地对子序列进行排序,最终合并得到有序序列。快速排序在平均情况下的时间...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它基于分治法的策略,通过选取一个基准值并重新排列数组,将问题分解为较小的部分,然后递归地对这些部分进行排序,最终达到整个序列...
在本文中,我们将深入探讨基于FPGA的并行快速排序算法,特别关注“位宽可设”的特性。这种算法能够高效地处理大量数据,并且在硬件实现上具有很高的灵活性。我们将从以下几个方面来阐述这个主题: 一、快速排序算法...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它基于分治策略,通常比其他O(n^2)时间复杂度的排序算法更快,平均时间复杂度为O(n log n)。在本项目中,“快速排序演示程序/vc++/mfc...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
根据给定文件的信息,我们可以总结出以下关于“数据结构 快速排序 输出每一趟结果”的知识点: ### 一、快速排序的基本概念 快速排序是一种高效的排序算法,采用分治法策略来把一个序列分为较小和较大的两个子序列...
快速排序和冒泡排序是两种常见的排序算法,它们在计算机科学中扮演着重要的角色,特别是在数据处理和优化程序性能方面。本篇文章将深入探讨这两种排序算法的原理、效率以及它们在C#编程语言中的实现。 首先,让我们...