java十二种排序算法实现源代码（类）

冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序，堆排序，桶式排序，基数排序 一、冒泡排序(BubbleSort) 1. 基本思想： 　　两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。 2. 排序过程： 　　设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反 复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。 【示例】： 49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97 二、选择排序 1. 基本思想： 　　每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】： 初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97 三、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程：　 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] 五、快速排序（Quick Sort） 1. 基本思想： 　　在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于 基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的 划分过程，直至所有无序子区中的数据元素均已排序为止。 2. 排序过程： 【示例】： 初始关键字 ［49 38 65 97 76 13 27 49］ 一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］ 二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］ 三趟排序之后 13 27 38 49 49 ［65］76 97 最后的排序结果 13 27 38 49 49 65 76 97 各趟排序之后的状态 七、堆排序(Heap Sort) 1. 基本思想： 堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。 2. 堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性： Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2]) 堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（ 称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。 3. 排序过程： 堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字 最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。 【示例】：对关键字序列42，13，91，23，24，16，05，88建堆 十、几种排序算法的比较和选择 1. 选取排序方法需要考虑的因素： (1) 待排序的元素数目n； (2) 元素本身信息量的大小； (3) 关键字的结构及其分布情况； (4) 语言工具的条件，辅助空间的大小等。 2. 小结： (1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。 (2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。 (3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。 (4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比 较"的排序算法，至少需要O(nlog2n)的时间。 (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） 排序算法的时间