Java程序员必知的8大排序.docx

Java程序员必知的8大排序.docx

《Java程序员必知的8大排序.docx》由会员分享，可在线阅读，更多相关《Java程序员必知的8大排序.docx（19页珍藏版）》请在冰点文库上搜索。

Java程序员必知的8大排序

8种排序之间的关系:

1， 直接插入排序

（1）基本思想：

在要排序的一组数中，假设前面（n-1）[n>=2]个数已经是排

好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数

也是排好顺序的。

如此反复循环，直到全部排好顺序。

（2）实例

（3）用java实现

1. package com.njue; 

2.  

3.public class insertSort { 

4.public insertSort（）{ 

5.    inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51}; 

6.    int temp=0; 

7.    for（int i=1;i

8.       int j=i-1; 

9.       temp=a[i]; 

10.       for（;j>=0&&temp

11.       a[j+1]=a[j];                       //将大于temp的值整体后移一个单位 

12.       } 

13.       a[j+1]=temp; 

14.    } 

15.    for（int i=0;i

16.       System.out.println（a[i]）; 

17.} 

18.} 

2，希尔排序（最小增量排序）

（1）基本思想：

算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。

当增量减到1时，进行直接插入排序后，排序完成。

（2）实例：

（3）用java实现

1.public class shellSort { 

2.public  shellSort（）{ 

3.    int a[]={1,54,6,3,78,34,12,45,56,100}; 

4.    double d1=a.length; 

5.    int temp=0; 

6.    while（true）{ 

7.        d1= Math.ceil（d1/2）; 

8.        int d=（int） d1; 

9.        for（int x=0;x

10.            for（int i=x+d;i

11.                int j=i-d; 

12.                temp=a[i]; 

13.                for（;j>=0&&temp

14.                a[j+d]=a[j]; 

15.                } 

16.                a[j+d]=temp; 

17.            } 

18.        } 

19.        if（d==1） 

20.            break; 

21.    } 

22.    for（int i=0;i

23.        System.out.println（a[i]）; 

24.} 

25.} 

3.简单选择排序

（1）基本思想：

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；

然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

（2）实例：

（3）用java实现

1.public class selectSort { 

2.    public selectSort（）{ 

3.        int a[]={1,54,6,3,78,34,12,45}; 

4.        int position=0; 

5.        for（int i=0;i

6.             

7.            int j=i+1; 

8.            position=i; 

9.            int temp=a[i]; 

10.            for（;j

11.            if（a[j]

12.                temp=a[j]; 

13.                position=j; 

14.            } 

15.            } 

16.            a[position]=a[i]; 

17.            a[i]=temp; 

18.        } 

19.        for（int i=0;i

20.            System.out.println（a[i]）; 

21.    } 

22.} 

4，堆排序

（1）基本思想：

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

堆的定义如下：

具有n个元素的序列（h1,h2,...,hn）,当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）（i=1,2,...,n/2）时称之为堆。

在这里只讨论满足前者条件的堆。

由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。

完全二叉树可以很直观地表示堆的结构。

堆顶为根，其它为左子树、右子树。

初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。

然后将根节点与堆的最后一个节点交换。

然后对前面（n-1）个数重新调整使之成为堆。

依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。

所以堆排序有两个函数组成。

一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

（2）实例：

初始序列：

46,79,56,38,40,84

建堆：

交换，从堆中踢出最大数

依次类推：

最后堆中剩余的最后两个结点交换，踢出一个，排序完成。

（3）用java实现

1.import java.util.Arrays; 

2. 

3.public class HeapSort { 

4.     int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51}; 

5.    public  HeapSort（）{ 

6.        heapSort（a）; 

7.    } 

8.    public  void heapSort（int[] a）{ 

9.        System.out.println（"开始排序"）; 

10.        int arrayLength=a.length; 

11.        //循环建堆 

12.        for（int i=0;i

13.            //建堆 

14. 

15.      buildMaxHeap（a,arrayLength-1-i）; 

16.            //交换堆顶和最后一个元素 

17.            swap（a,0,arrayLength-1-i）; 

18.            System.out.println（Arrays.toString（a））; 

19.        } 

20.    } 

21. 

22.    private  void swap（int[] data, int i, int j） { 

23.        // TODO Auto-generated method stub 

24.        int tmp=data[i]; 

25.        data[i]=data[j]; 

26.        data[j]=tmp; 

27.    } 

28.    //对data数组从0到lastIndex建大顶堆 

29.    private void buildMaxHeap（int[] data, int lastIndex） { 

30.        // TODO Auto-generated method stub 

31.        //从lastIndex处节点（最后一个节点）的父节点开始 

32.        for（int i=（lastIndex-1）/2;i>=0;i--）{ 

33.            //k保存正在判断的节点 

34.            int k=i; 

35.            //如果当前k节点的子节点存在 

36.            while（k*2+1<=lastIndex）{ 

37.                //k节点的左子节点的索引 

38.                int biggerIndex=2*k+1; 

39.                //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 

40.                if（biggerIndex

41.                    //若果右子节点的值较大 

42.                    if（data[biggerIndex]

43.                        //biggerIndex总是记录较大子节点的索引 

44.                        biggerIndex++; 

45.                    } 

46.                } 

47.                //如果k节点的值小于其较大的子节点的值 

48.                if（data[k]

49.                    //交换他们 

50.                    swap（data,k,biggerIndex）; 

51.                    //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 

52.                    k=biggerIndex; 

53.                }else{ 

54.                    break; 

55.                } 

56.            }    }