Java各种排序算法参考.pdf

Java各种排序算法参考.pdf

Java 排序算法 1）分类：1）插入排序（直接插入排序、希尔排序）2 ）交换排序（冒泡排序、快速排序）3）选择排序（直接选择排序、堆排序）4 ）归并排序5）分配排序（箱排序、基数排序）所需辅助空间最多：归并排序所需辅助空间最少：堆排序平均速度最快：快速排序不稳定：快速排序，希尔排序，堆排序。 1）选择排序算法的时候1. 数据的规模 ； 2. 数据的类型； 3. 数据已有的顺序 一般来说，当数据规模较小时java比较排序，应选择直接插入排序或冒泡排序。任何排序算法在数据量小时基本体现不 出来差距。 考虑数据的类型，比如如果全部是正整数，那么考虑使用桶排序为最优。考虑数据已有顺序， 快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。数 据量极小，而起已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理 想。而不是所有情况。 3）总结： ——按平均的时间性能来分：1）时间复杂度为O(nlogn) 的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；2 ）时间复杂度为 O(n2) 的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；3）时间复杂度为O(n) 的排序方法只有，基数排序。 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n) 的时间复杂度 ; 而对于快速排 序而言，这是最不好的情况java比较排序Java各种排序算法参考.pdf，此时的时间性能蜕化为O(n2) ，因此是应该尽量避免的情况。简单选择排序、 堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 —— 按平均的空间性能来分（指的是排序过程中所需的辅助空间大小）：1） 所有的简单排序方法( 包括：直接插入、起泡和简单选择) 和堆排序的空间复杂度为O(1) ；2 ） 快速排序为 O(log n ) ，为栈所需的辅助空间 ;3） 归并排序所需辅助空间最多，其空间复杂度为O( );n4 ）链式基数排序需附设队列首尾指针，则空间复杂度为O(rd ) 。 —— 排序方法的稳定性能：1） 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。2 ） 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。3） 对于不稳定的排序方法，只要能举出一个实例说明即可。4 ） 快速排序Java各种排序算法参考.pdf，希尔排序和堆排序是不稳定的排序方法。 4 ）插入排序： 包括直接插入排序，希尔插入排序。 直接插入排序：将一个记录插入到已经排序好的有序表中。1, 数组的第 0个位置没有放数据。2 ，从 第二个数据开始处理：如果该数据比它前面的数据要小，说明该数据要往前面移动。首先将该数据备份放到 的第 0位置当哨兵。然后将该数据前面那个数据后移。然后往前搜索，找插入位置。找到插入位置之后讲第 0位置的那个数据插入对应位置。O(n*n),当待排记录序列为正序时，时间复杂度提高至O(n) 。 希尔排序（缩小增量排序 sort）：先将整个待排记录序列分割成若干个子序列分 别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。面试穿什么，这里找答案！ 插入排序 Java 代码： class {//插入排序：直接插入排序，希尔排序 void t(

){int = . ;for ( int j=2;;j++){if (

j-1

){

=

;// 先保存一下后面的那个

=

j-1

;// 前面的那个后移。int =0;for ( int k=j-2;k=0;k–){if (

){

k+1

=

;} else {=k+1;break ;}}

=

;}}} void (

,int inc){int = . ;for ( int j=inc+1;;j++ ){if (

j-inc

){

=

;// 先保存一下后面的那个int =j;for ( int k=j-inc;k=0;k-=inc){if (

){

k+inc

=

;// 数据结构课本上这个地方没有给出判读，出错：if (k-inc=0){ = k;}} else {=k+inc;break ;}}

=

;}}} (

){int

incs={7,5,3,1};int num= incs. ;int inc=0;for ( int j=0;jnum;j++){inc= incs

;(,inc);}} main(

args) { = new (6);int = 21;

=new

;. out .print( Sort:);for ( int j=1;;j++){

= (int )(.()* 100);. out .print((int )

+);}. out .(); =new (); //.t();.();. out .print(After Sort:);for ( int j=1;. ;j++){. out .print((int )

+);}. out .();} }面试穿什么，这里找答案！ 5）交换排序： 包括冒泡排序，快速排序。 冒泡排序法： 该算法是 专门针对已部分排序的数据进行排序的一种排序算法。如果在你的数据清单中只有 一两个数据是乱序的话，用这种算法就是最快的排序算法。如果你的数据清单中的数据是随机排列的，那 么这种方法就成了最慢的算法了。因此在使用这种算法之前一定要慎重。这种算法的核心思想是扫描数据 清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后java比较排序，交换项目的位置然后继续扫描。重复上面 的操作直到所有的项目都按顺序排好。 快速排序： 通过一趟排序，将待排序记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分 记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。具体做法是：使用两个 指针 low,high,初值分别设置为序列的头，和序列的尾，设置 为第一个记录，首先从high 开始 向前搜索第一个小于 的记录和 所在位置进行交换，然后从low 开始向后搜索第一个大 于 的记录和此时 所在位置进行交换，重复知道low=high 了为止。 交换排序 Java 代码： class { void (

){int = . ;for ( int j=;j0;j–){int end= j;for ( int k=1;kend-1;k++){ tempB=

=

k+1

?

:

k+1

;if (Math. abs(

-tempB)10e-6){

k+1

=tempB;}}}} void (

,int low, int high){if (){int pivot= (,low,high);(,low,pivot-1);(,pivot+1,high);}} int (

,int low, int high){

=

low

;while (){while (

high

=

)–high;

low

=

high

;while (

low

=

)++low;

high

=

low

;}

low

=

; low;} void main(

args) { = new (6);int = 21;

=new

;. out .print( Sort:);for ( int j=1;;j++){

= (int )(.()* 100);. out .print((int )

+);}. out .(); =new (); //.();.(, 1, -1);. out .print( After Sort:);for ( int j=1;. ;j++){. out .print((int )

+);}. out .();} } 6）选择排序： 分为直接选择排序，堆排序 直接选择排序：第 i 次选取 i到 array.-1中间最小的值放在i 位置。 堆排序： 首先，数组里面用层次遍历的顺序放一棵完全二叉树。从最后一个非终端结点往前面调整，直到 到达根结点，这个时候除根节点以外的所有非终端节点都已经满足堆得条件了，于是需要调整根节点使得 整个树满足堆得条件，于是从根节点开始，沿着它的儿子们往下面走（最大堆沿着最大的儿子走，最小堆 沿着最小的儿子走） 。 主程序里面，首先从最后一个非终端节点开始调整到根也调整完，形成一个heap， 然后将heap 的根放到后面去（即：每次的树大小会变化，但是root 都是在 1的位置，以方便计算儿子们 的 index ，所以如果需要升序排列，则要逐步大顶堆。因为根节点被一个个放在后面去了。降序排列则要 建立小顶堆） 代码中的问题：有时候第 2个和第 3个顺序不对（原因还没搞明白到底代码哪里有错） 选择排序 Java 代码： class { void (

){int = . ;for ( int j=1;;j++){int jMin= (,j);(,j,jMin);}} (

,int i, int j){int = . ;if ( ij i=0 j=0){ temp=

=

=temp;}} (

,int i){int = . ;int minJ=1; min= .; ( int j=i;;j++){if (

min){min=

;minJ= j;}} minJ;} (

,int start, int end){if (){ temp=

start

; //这个地方 jend 与课本不同， j=end 会报错：for ( int j=2*start;jend;j *=2){if (j+1end

–

j+1

10e-6){++j;}if (temp=

){break ;}

start

=

;start=j;}

start

=temp;}} (

){int = . ;for ( int i=/2;i0;i–){(,i,);}for ( int i=;i1;–i){(,1,i);(,1,i-1);}} void main(

args){ = new (6);int =9;

=new

;. out .print( Sort:);for ( int j=1;;j++){

= (int )(.()* 100);. out .print((int )

+);}. out .(); =new (); //.();.();. out .print(After Sort:);for ( int j=1;. ;j++){. out .print((int )

+);}. out .();} }面试穿什么，这里找答案！ 7）归并排序： 将两个或两个以上的有序表组合成一个新的有序表。归并排序要使用一个辅助数组，大小跟原数组相同， 递归做法。每次将目标序列分解成两个序列，分别排序两个子序列之后，再将两个排序好的子序列merge 到一起。 归并排序 Java 代码： {

;// 辅助数组 sort(

obj){if (obj ==null ){ (The param can not be null!);} = new

obj.

; // 初始化中间数组(obj, 0, obj.- 1);// 归并排序 = null ; } (

obj,int left,int right){if (left right){int = (left + right) / 2;(obj, left, );(obj, + 1, right);merge(obj, left, , right);} } merge(

obj,int left,int ,int right){int mid = + 1;int third = left;int tmp = left;while (left = mid = right){// 从两个数组中取出小的放入中间数组if (obj

left

-obj

mid

=10e-6){

third++

= obj

left++

;} else {

third++

= obj

mid++

;}}// 剩余部分依次置入中间数组while (mid = right){

third++

= obj

mid++

;}while (left = ){

third++

= obj

left++

;}// 将中间数组的内容拷贝回原数组copy(obj, tmp, right); } copy(

obj,int left,int right) {while (left = right){obj

left

=

left

;left++;}} main(

args) { =new (6);int = 10;

=new

;. out .print( Sort:);for ( int j = 0; j ; j++) {

= (int ) (.() * 100);. out .print((int )

+);}. out .(); =new ();.sort();. out .print