比冒泡排序更快的算法（常见的排序算法哪个效率最高）

本文目录

• 常见的排序算法哪个效率最高
• 几种排序算法效率的比较
• 冒泡、直插、选择、快速、希尔、归并排序算法进行比较
• 冒泡排序法和快速排序比较的算法
• 一个无序数组用什么排序方法排序是最快的

常见的排序算法哪个效率最高

快速排序法。

Java的排序算法有哪些？

java的排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序：1.插入排序：直接插入排序、二分法插入排序、希尔排序。

2.选择排序：简单选择排序、堆排序。

3.交换排序：冒泡排序、快速排序。

4.归并排序。

5.基数排序。

java中的算法，一共有多少种，哪几种，怎么分类？

1、算法按实现方式分，有递归、迭代、平行、序列、过程、确定、不确定等。

2、算法按设计范型分，有分治、动态、贪心、线性、图论、简化等。

几种排序算法效率的比较

插入排序，选择排序，交换排序（冒泡），数据结构书上有详细的介绍以下是直接插入排序，选择排序，希尔排序，冒泡排序的算法/*直接插入排序的基本思想是：顺序地把待排序序列中的各个记录按其关键字的大小，插入到已排序的序列的适当位置。*/void InsertSort(elemtype x, int n){int i,j;elemtype s;for(i=0;i《n-1;i ){s = x;j = i;while(j》-1 && s.key《x.key){x;j--;}x=s;}}/*选择排序的基本思想是：不断从待排序的序列中选取关键字最小的记录放到已排序的记录序列的后面，知道序列中所有记录都已排序为止。*/void SelectSort(elemtype x, int n){int i,j,Small;elemtype Temp;for(i=0;i《n-1;i ){Small = i;for(j=i 1;j《n;j ){if(x.key)Small = j;}if(Small!=i){Temp = x;x;x = Temp; }}}/*希尔排序的基本思想是：不断把待排序的记录分成若干个小组，对同一组内的记录进行排序，在分组时，始终保证当前组内的记录个数超过前面分组排序时组内的记录个数。*/void ShellSort(elemtype x, int Number){int i, j, k, m, Span;elemtype s;for(m=0;m《Number;m ){Span = d;for(k=0;k《Span;k ){for(i=k;i《n-Span;i =Span){s = x;j = i;while(j》-1 && s.key《x.key){x;j-=Span;}x = s;}}}}/*冒泡排序的基本思想是：将待排序序列中第一个记录的关键字R1与第二个记录的关键字R2做比较，如果R1》R2，则交换R1和R2的位置，否则不交换；然后继续对当前序列中的第二个记录和第三个记录同样的处理，依此类推。*/void BubbleSort(elemtype x, int n){int i,j,flag=1;elemtype temp;for(i=1;i《n && flag==1;i ){flag=0;for(j=0;j《n-i;j ){if(x.key){flag=1;temp=x;x;x=temp;}}}}

冒泡、直插、选择、快速、希尔、归并排序算法进行比较

(1)冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。 (2)选择排序 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。 (3)插入排序 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 (4)快速排序 快速排序有两个方向，左边的i下标一直往右走，当a 交换的时刻。 (5)归并排序 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。 (6)基数排序 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。 (7)希尔排序(shell) 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。 (8)堆排序 我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2 -1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

冒泡排序法和快速排序比较的算法

打你屁股，这么简单的问题都不认真研究一下。冒泡排序是最慢的排序，时间复杂度是 O(n^2)。快速排序是最快的排序。关于快速排序，我推荐你看看《代码之美》第二章：我编写过的最漂亮的代码。作者所说的最漂亮，就是指效率最高的。--------------------------------摘自《代码之美》---------------当我撰写关于分治（divide-and-conquer）算法的论文时，我发现C.A.R. Hoare的Quicksort算法（“Quicksort”，Computer Journal 5）无疑是各种Quicksort算法的鼻祖。这是一种解决基本问题的漂亮算法，可以用优雅的代码实现。我很喜欢这个算法，但我总是无法弄明白算法中最内层的循环。我曾经花两天的时间来调试一个使用了这个循环的复杂程序，并且几年以来，当我需要完成类似的任务时，我会很小心地复制这段代码。虽然这段代码能够解决我所遇到的问题，但我却并没有真正地理解它。我后来从Nico Lomuto那里学到了一种优雅的划分（partitioning）模式，并且最终编写出了我能够理解，甚至能够证明的Quicksort算法。William Strunk Jr.针对英语所提出的“良好的写作风格即为简练”这条经验同样适用于代码的编写，因此我遵循了他的建议，“省略不必要的字词”（来自《The Elements of Style》一书）。我最终将大约40行左右的代码缩减为十几行的代码。因此，如果要回答“你曾编写过的最漂亮代码是什么？”这个问题，那么我的答案就是：在我编写的《Programming Pearls, Second Edition》(Addison-Wesley)一书中给出的Quichsort算法。在示例2-1中给出了用C语言编写的Quicksort函数。我们在接下来的章节中将进一步地研究和改善这个函数。【示例】 2-1 Quicksort函数void quicksort(int l, int u){ int i, m;if (l 》= u) return; 10swap(l, randint(l, u));m = l;for (i = l+1; i 《= u; i++)if (x)swap(++m, i);swap(l, m);quicksort(l, m-1);quicksort(m+1, u);}如果函数的调用形式是quicksort(0, n-1)，那么这段代码将对一个全局数组x这两个元素。第一次交换操作将会按照均匀分布的方式在l和u之间随机地选择一个划分元素。在《Programming Pearls》一书中包含了对Quicksort算法的详细推导以及正确性证明。在本章的剩余内容中，我将假设读者熟悉在《Programming Pearls》中所给出的Quicksort算法以及在大多数初级算法教科书中所给出的Quicksort算法。如果你把问题改为“在你编写那些广为应用的代码中，哪一段代码是最漂亮的？”我的答案还是Quicksort算法。在我和M. D. McIlroy一起编写的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol. 23, No. 11）中指出了在原来Unix qsort函数中的一个严重的性能问题。随后，我们开始用C语言编写一个新排序函数库，并且考虑了许多不同的算法，包括合并排序（Merge Sort）和堆排序（Heap Sort）等算法。在比较了Quicksort的几种实现方案后，我们着手创建自己的Quicksort算法。在这篇文章中描述了我们如何设计出一个比这个算法的其他实现要更为清晰，速度更快以及更为健壮的新函数——部分原因是由于这个函数的代码更为短小。Gordon Bell的名言被证明是正确的：“在计算机系统中，那些最廉价，速度最快以及最为可靠的组件是不存在的。”现在，这个函数已经被使用了10多年的时间，并且没有出现任何故障。考虑到通过缩减代码量所得到的好处，我最后以第三种方式来问自己在本章之初提出的问题。“你没有编写过的最漂亮代码是什么？”。我如何使用非常少的代码来实现大量的功能？答案还是和Quicksort有关，特别是对这个算法的性能分析。我将在下一节给出详细介绍。2.2 事倍功半Quicksort是一种优雅的算法，这一点有助于对这个算法进行细致的分析。大约在1980年左右，我与Tony Hoare曾经讨论过Quicksort算法的历史。他告诉我，当他最初开发出Quicksort时，他认为这种算法太简单了，不值得发表，而且直到能够分析出这种算法的预期运行时间之后，他才写出了经典的“Quicksoft”论文。我们很容易看出，在最坏的情况下，Quicksort可能需要n2的时间来对数组元素进行排序。而在最优的情况下，它将选择中值作为划分元素，因此只需nlgn次的比较就可以完成对数组的排序。那么，对于n个不同值的随机数组来说，这个算法平均将进行多少次比较？Hoare对于这个问题的分析非常漂亮，但不幸的是，其中所使用的数学知识超出了大多数程序员的理解范围。当我为本科生讲授Quicksort算法时，许多学生即使在费了很大的努力之后，还是无法理解其中的证明过程，这令我非常沮丧。下面，我们将从Hoare的程序开11始讨论，并且最后将给出一个与他的证明很接近的分析。我们的任务是对示例2-1中的Quicksort代码进行修改，以分析在对元素值均不相同的数组进行排序时平均需要进行多少次比较。我们还将努力通过最短的代码、最短运行时间以及最小存储空间来得到最深的理解。为了确定平均比较的次数，我们首先对程序进行修改以统计次数。因此，在内部循环进行比较之前，我们将增加变量comps的值（参见示例2-2）。【示例2-2】 修改Quicksort的内部循环以统计比较次数。for (i = l+1; i 《= u; i++) {comps++;if (x)swap(++m, i);}如果用一个值n来运行程序，我们将会看到在程序的运行过程中总共进行了多少次比较。如果重复用n来运行程序，并且用统计的方法来分析结果，我们将得到Quicksort在对n个元素进行排序时平均使用了1.4 nlgn次的比较。在理解程序的行为上，这是一种不错的方法。通过十三行的代码和一些实验可以反应出许多问题。这里，我们引用作家Blaise Pascal和T. S. Eliot的话，“如果我有更多的时间，那么我给你写的信就会更短。”现在，我们有充足的时间，因此就让我们来对代码进行修改，并且努力编写出更短（同时更好）的程序。我们要做的事情就是提高这个算法的速度，并且尽量增加统计的精确度以及对程序的理解。由于内部循环总是会执行u-l次比较，因此我们可以通过在循环外部增加一个简单的操作来统计比较次数，这就可以使程序运行得更快一些。在示例2-3的Quicksort算法中给出了这个修改。【示例2-3】 Quicksort的内部循环，将递增操作移到循环的外部comps += u-l;for (i = l+1; i 《= u; i++)if (x)swap(++m, i);这个程序会对一个数组进行排序，同时统计比较的次数。不过，如果我们的目标只是统计比较的次数，那么就不需要对数组进行实际地排序。在示例2-4中去掉了对元素进行排序的“实际操作”，而只是保留了程序中各种函数调用的“框架”。【示例2-4】将Quicksort算法的框架缩减为只进行统计void quickcount(int l, int u){ int m;if (l 》= u) return;m = randint(l, u);comps += u-l;quickcount(l, m-1);quickcount(m+1, u);}12这个程序能够实现我们的需求，因为Quichsort在选择划分元素时采用的是“随机”方式，并且我们假设所有的元素都是不相等的。现在，这个新程序的运行时间与n成正比，并且相对于示例2-3需要的存储空间与n成正比来说，现在所需的存储空间缩减为递归堆栈的大小，即存储空间的平均大小与lgn成正比。虽然在实际的程序中，数组的下标（l和u）是非常重要的，但在这个框架版本中并不重要。因此，我们可以用一个表示子数组大小的整数(n)来替代这两个下标（参见示例2-5）【示例2-5】 在Quicksort代码框架中使用一个表示子数组大小的参数void qc(int n){ int m;if (n 《= 1) return;m = randint(1, n);comps += n-1;qc(m-1);qc(n-m);}现在，我们可以很自然地把这个过程整理为一个统计比较次数的函数，这个函数将返回在随机Quicksort算法中的比较次数。在示例2-6中给出了这个函数。【示例2-6】 将Quicksort框架实现为一个函数int cc(int n){ int m;if (n 《= 1) return 0;m = randint(1, n);return n-1 + cc(m-1) + cc(n-m);}在示例2-4、示例2-5和示例2-6中解决的都是相同的基本问题，并且所需的都是相同的运行时间和存储空间。在后面的每个示例都对这些函数的形式进行了改进，从而比这些函数更为清晰和简洁。在定义发明家的矛盾（inventor’s paradox）(How To Solve It, Princeton University Press)时，George Póllya指出“计划越宏大，成功的可能性就越大。”现在，我们就来研究在分析Quicksort时的矛盾。到目前为止，我们遇到的问题是，“当Quicksort对大小为n的数组进行一次排序时，需要进行多少次比较？”我们现在将对这个问题进行扩展，“对于大小为n的随机数组来说，Quichsort算法平均需要进行多少次的比较？”我们通过对示例2-6进行扩展以引出示例2-7。【示例2-7】 伪码：Quicksort的平均比较次数float c(int n)if (n 《= 1) return 0sum = 0for (m = 1; m 《= n; m++)sum += n-1 + c(m-1) + c(n-m)return sum/n如果在输入的数组中最多只有一个元素，那么Quichsort将不会进行比较，如示例2-613中所示。对于更大的n，这段代码将考虑每个划分值m（从第一个元素到最后一个，每个都是等可能的）并且确定在这个元素的位置上进行划分的运行开销。然后，这段代码将统计这些开销的总和（这样就递归地解决了一个大小为m-1的问题和一个大小为n-m的问题），然后将总和除以n得到平均值并返回这个结果。如果我们能够计算这个数值，那么将使我们实验的功能更加强大。我们现在无需对一个n值运行多次来估计平均值，而只需一个简单的实验便可以得到真实的平均值。不幸的是，实现这个功能是要付出代价的：这个程序的运行时间正比于3n（如果是自行参考（self-referential）的，那么用本章中给出的技术来分析运行时间将是一个很有趣的练习）。示例2-7中的代码需要一定的时间开销，因为它重复计算了中间结果。当在程序中出现这种情况时，我们通常会使用动态编程来存储中间结果，从而避免重复计算。因此，我们将定义一个表t，并且按照升序来计算它的值。我们将用N来表示n的最大值，也就是进行排序的数组的大小。在示例2-8中给出了修改后的代码。【示例2-8】 在Quicksort中使用动态编程来计算t = 0for (n = 1; n 《= N; n++)sum = 0for (i = 1; i 《= n; i++)sum += n-1 + tt = sum/n这个程序只对示例2-7进行了细微的修改，即用t来替换c(n)。它的运行时间将正比于N2，并且所需的存储空间正比于N。这个程序的优点之一就是：在程序执行结束时，数组t中将包含数组中从元素0到元素N的真实平均值（而不是样本均值的估计）。我们可以对这些值进行分析，从而生成在Quichsort算法中统计比较次数的计算公式。我们现在来对程序做进一步的简化。第一步就是把n-1移到循环的外面，如示例2-9所示。【示例2-9】 在Quicksort中把代码移到循环外面来计算t = 0for (n = 1; n 《= N; n++)sum = 0for (i = 1; i 《= n; i++)sum += tt = n-1 + sum/n现在将利用对称性来对循环做进一步的调整。例如，当n为4时，内部循环计算总和为：t在上面这些组对中，第一个元素增加而第二个元素减少。因此，我们可以把总和改写为：2 * (t)我们可以利用这种对称性来得到示例2-10中的Quicksort。【示例2-10】 在Quichsort中利用了对称性来计算t = 014for (n = 1; n 《= N; n++)sum = 0for (i = 0; i 《 n; i++)sum += 2 * tt = n-1 + sum/n然而，在这段代码的运行时间中同样存在着浪费，因为它重复地计算了相同的总和。此时，我们不是把前面所有的元素加在一起，而是在循环外部初始化总和并且加上下一个元素，如示例2-11所示。【示例2-11】 在Quicksort中删除了内部循环来计算sum = 0; t = 0for (n = 1; n 《= N; n++)sum += 2*tt = n-1 + sum/n这个小程序确实很有用。程序的运行时间与N成正比，对于每个从1到N的整数，程序将生成一张Quicksort的估计运行时间表。我们可以很容易地把示例2-11用表格来实现，其中的值可以立即用于进一步的分析。在2-1给出了最初的结果行。表2-1 示例2-11中实现的表格输出N Sum t0 0 01 0 02 0 13 2 2.6674 7.333 4.8335 17 7.46 31.8 10.37 52.4 13.4868 79.371 16.921这张表中的第一行数字是用代码中的三个常量来进行初始化的。下一行（输出的第三行）的数值是通过以下公式来计算的：A3 = A2+1 B3 = B2 + 2*C2 C3 = A2-1 + B3/A3把这些（相应的）公式记录下来就使得这张表格变得完整了。这张表格是“我曾经编写的最漂亮代码”的很好的证据，即使用少量的代码完成大量的工作。但是，如果我们不需要所有的值，那么情况将会是什么样？如果我们更希望通过这种来方式分析一部分数值（例如，在20到232之间所有2的指数值）呢？虽然在示例2-11中构建了完整的表格t，但它只需要使用表格中的最新值。因此，我们可以用变量t的定长空间来替代table t的线性空间，如示例2-12所示。【示例2-12】 Quicksoft 计算——最终版本sum = 0; t = 015for (n = 1; n 《= N; n++)sum += 2*tt = n-1 + sum/n然后，我们可以插入一行代码来测试n的适应性，并且在必要时输出这些结果。这个程序是我们漫长学习旅途的终点。通过本章所采用的方式，我们可以证明Alan Perlis的经验是正确的：“简单性并不是在复杂性之前，而是在复杂性之后” ("Epigrams on Programming," Sigplan Notices, Vol. 17, Issue 9)。

一个无序数组用什么排序方法排序是最快的

一个数组A是有序的,一个数组B是无序的.需要按顺序排序为一个数组,我能想到的就是先将无序B的用冒泡排序,再和A用归并排序,A,B的长度都不超过100各位高手,还能提供更高效率的排序算法吗?谢谢了. 答:《/FONT》B用快排吧。A和B的合并使用使用归并。 答:《/FONT》考虑到数组A已经有序，可以遍历数组B中每一个元素，使用binarysearch的方法将元素插入到数组B中。这个算法的时间复杂度应该时O(N*log(N))。 答:《/FONT》O(nlogn)已经是最快的了 答:《/FONT》将无序数组B插入有序数组A，每次插入时，用折半查找确定插入位置。在将A与B合并为新数组C的情形下（即有辅助数组），上述算法的复杂度为：O(len(B)*log(len(A)))(len(X)表示数组X的长度)。 答:《/FONT》binarysearch是logn的复杂度，但是如何完成数组的插入操作？ 答:《/FONT》二分查找再插入的算法复杂度为O(len(B)*log(len(A)len(B)) 答:《/FONT》在这里我们更关心的是数组B的元素个数，数组A的元素个数相对于来说可以看作是常数，所以简单的说，这个算法应该是个O(N*log(N))的算法。 答:《/FONT》该回复于2007-10-0914:24:36被管理员删除 答:《/FONT》该回复于2007-10-0914:24:36被管理员删除 答:《/FONT》首先用快排,然后用归并就可以了 答:《/FONT》MONOLINUX()算法时间是2*O(n)-----------------------------------哟这不是咱们写搜索引擎的大牛嘛连这么一个简单的问题都弄不明白?基于比较的算法是O(nlogn)给个简单的证明如果存在低于O(nlogn)的算法那么对于任何数组B,给一个已排序的A,我们可以得到一个合并A,B且已排序的数组C去掉C中所拥有的A中的元素,这一步显然可以在O(n)内完成,那么我们就得到一个已排序的B,且得到一个复杂度低于O(nlogn)的基于比较的排序算法