java排序算法有多少种

[魔芋有多少种吃法各位好！请告诉我魔芋的多少种吃法啊！谢谢了！]美味魔芋冬瓜汤”的制作方法：（非常简单） 1：准备葱、姜、蒜切成片；冬瓜切成丁；黄瓜半根切成丁；海米5个、植物油2汤匙； 2：把植物油放到锅里烧热，后放海米，把海米炸以下再放葱、姜、蒜在锅...+阅读

java排序算法有多少种

算法和语言无关吧，语言只是把具体的算法实现出来而已。据我了解的排序算法11-13种。排序算法嘛主要就是个思想而已。不同的算法时间复杂度不一样，空间复杂度也不一样，当然执行的效率也不一样。当然采用哪种算法还取决于你要实现什么样的功能。就好比说：要同时尽快的找出最大最小，或者尽快的找出最值的位置等等。冒泡排序（bubble sort） — O(n2)

鸡尾酒排序（Cocktail sort，双向的冒泡排序） — O(n2)

插入排序（insertion sort）— O(n2)

桶排序（bucket sort）— O(n)；需要 O(k) 额外记忆体

计数排序（counting sort） — O(n+k)；需要 O(n+k) 额外记忆体

归并排序（merge sort）— O(n log n)；需要 O(n) 额外记忆体

原地归并排序 — O(n2)

二叉树排序（Binary tree sort） — O(n log n)；需要 O(n) 额外记忆体

鸽巢排序（Pigeonhole sort） — O(n+k)；需要 O(k) 额外记忆体

基数排序（radix sort）— O(n·k)；需要 O(n) 额外记忆体

Gnome sort — O(n2)

Library sort — O(n log n) with high probability，需要（1+ε）n 额外记忆体不稳定

选择排序（selection sort）— O(n2)

希尔排序（shell sort）— O(n log n) 如果使用最佳的现在版本

Comb sort — O(n log n)

堆排序（heapsort）— O(n log n)

Smoothsort — O(n log n)

快速排序（quicksort）— O(n log n) 期望时间， O(n2) 最坏情况；对於大的、乱数串列一般相信是最快的已知排序

等。

各种排序算法实现和比较

展开全部

1、堆排序定义 n个关键字序列Kl,K2，…，Kn称为堆，当且仅当该序列满足如下性质（简称为堆性质）：

（1） ki≤K2i且ki≤K2i+1 或

（2）Ki≥K2i且ki≥K2i+1(1≤i≤ ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。关键字序列（10,15,56,25,30,70）和（70,56,30,25,15,10）分别满足堆性质

（1）和

（2），故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。

2、大根堆和小根堆根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆。注意： ①堆中任一子树亦是堆。 ②以上讨论的堆实际上是二叉堆（Binary Heap），类似地可定义k叉堆。

3、堆排序特点堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。

4、堆排序与直接插入排序的区别直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，可减少比较次数。

5、堆排序堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。

（1）用大根堆排序的基本思想 ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区 ② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key ③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 …… 直到无序区只有一个元素为止。

（2）大根堆排序算法的基本操作： ① 初始化操作：将R[1..n]构造为初始堆； ② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。注意： ①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 ②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

（3）堆排序的算法： void HeapSort(SeqIAst R) { //对R[1..n]进行堆排序，不妨用R[0]做暂存单元 int i; BuildHeap(R)； //将R[1-n]建成初始堆 for(i=n;i1;i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。 R[0]=R[1];R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换 Heapify(R,1,i-1)； //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 } //endfor } //HeapSort (4) BuildHeap和Heapify函数的实现因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。 ① Heapify函数思想方法每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。＂筛选法＂调整堆 R[low]的左、右子树（若存在）均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key,R[2low+1].key)）交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树（若存在）仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为＂筛选法＂。具体的算法 ②BuildHeap的实现要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。显然只有一个结点的树是堆，而在完全二叉树中，所有序号的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为， -1，…，1的结点作为根的子树都调整为堆即可。具体算法。

5、大根堆排序实例对于...

常用的数据排序算法有哪些各有什么特点

排序简介排序是数据处理中经常使用的一种重要运算，在计算机及其应用系统中，花费在排序上的时间在系统运行时间中占有很大比重；并且排序本身对推动算法分析的发展也起很大作用。目前已有上百种排序方法，但尚未有一个最理想的尽如人意的方法，本章说明常用的如下排序方法，并对它们进行分析和比较。

1、插入排序（直接插入排序、折半插入排序、希尔排序）；

2、交换排序（起泡排序、快速排序）；

3、选择排序（直接选择排序、堆排序）；

4、归并排序；

5、基数排序；学习重点

1、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；

2、掌握插入排序（直接插入排序、折半插入排序、希尔排序）、交换排序（起泡排序、快速排序）、选择排序（直接选择排序、堆排序）、二路归并排序的方法及其性能分析方法；

3、了解基数排序方法及其性能分析方法。排序（sort）或分类所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。其确切定义如下：输入：n个记录R1,R2，…，Rn，其相应的关键字分别为K1,K2，…，Kn。输出：Ril,Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。（或Ki1≥Ki2≥…≥Kin）。 1.被排序对象--文件被排序的对象--文件由一组记录组成。记录则由若干个数据项（或域）组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字（Key）。注意：在不易产生混淆时，将关键字项简称为关键字。 2.排序运算的依据--关键字用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。关键字的选取应根据问题的要求而定。【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用＂准考证号＂作为关键字。若要按照考生的总分数排名次，则需用＂总分数＂作为关键字。排序的稳定性当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。注意：排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。排序方法的分类 1.按是否涉及数据的内、外存交换分在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序（简称内排序）；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。注意： ① 内排序适用于记录个数不很多的小文件 ② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。 2.按策略划分内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。排序算法分析 1.排序算法的基本操作大多数排序算法都有两个基本的操作：

（1）比较两个关键字的大小；

（2）改变指向记录的指针或移动记录本身。注意：第

（2）种基本操作的实现依赖于待排序记录的存储方式。 2.待排文件的常用存储方式

（1）以顺序表（或直接用向量）作为存储结构排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）

（2）以链表作为存储结构排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表（或链式）排序；

（3）用顺序的方式存储待排序的记录，但同时建立一个辅助表（如包括关键字和指向记录位置的指针组成的索引表）排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。 3.排序算法性能评价

（1）评价排序算法好坏的标准评价排序算法好坏的标准主要有两条： ① 执行时间和所需的辅助空间 ② 算法本身的复杂程度

（2）排序算法的空间复杂度若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O

(1)，则称之为就地排序（In-PlaceSou）。非就地排序一般要求的辅助空间为O(n)。

(3) 排序算法的时间开销大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。文件的顺序存储结构表示 #define n l00 //假设的文件长度，即待排序的记录数目 typedef int KeyType； //假设的关键字类型 typedef struct{ //记录类型 KeyType key； //关键字项 InfoType otherinfo；//其它数据项，类型InfoType依赖于具体应用而定义 }RecType; typedef RecType SeqList[n+1];//SeqList为顺序表类型，表中第0个单元一般用作哨兵注意：若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。【例】关键字为字符串时，可定义宏＂#define LT(a,b)(Stromp((a),(b))