各类排序算法的解析及java实现

添加时间:2013-7-25 点击量:

　　排序一向以来都是让我很头疼的事，以前上《数据布局》打酱油去了，全部学期下来才勉强能写出个冒泡排序。因为下半年要筹办工作了，也知道排序算法的首要性（据说是口试必问的常识点），所以又花了点时候从头研究了一下。

　　排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，若是排序过程中须要应用外存，则称为外排序。下面讲的排序都是属于内排序。

　　内排序有可以分为以下几类：

　　（1）、插入排序：直接插入排序、二分法插入排序、希尔排序。

　　（2）、选择排序：简单选择排序、堆排序。

　　（3）、互换排序：冒泡排序、快速排序。

　　（4）、归并排序

　　（5）、基数排序

一、插入排序

•思惟：每步将一个待排序的记录，按其次序码大小插入到前面已经排序的字序列的合适地位，直到全部插入排序完为止。

•关键题目：在前面已经排好序的序列中找到合适的插入地位。

•办法：

–直接插入排序

–二分插入排序

–希尔排序

①直接插入排序（从后向前找到合适地位后插入）

　　1、根蒂根基思惟：每步将一个待排序的记录，按其次序码大小插入到前面已经排序的字序列的合适地位（从后向前找到合适地位后），直到全部插入排序完为止。

　　2、实例

　　3、java实现

 1 package com.sort;

 2 

 3 public class 直接插入排序 {

 4 

 5     public static void main（String[] args） {

 6         int[] a={49，38，65，97，76，13，27，49，78，34，12，64，1};

 7         System.out.println（排序之前：）;

 8         for （int i = 0; i < a.length; i++） {

 9             System.out.print（a[i]+ ）;

10         }

11         //直接插入排序

12         for （int i = 1; i < a.length; i++） {

13             //待插入元素

14             int temp = a[i];

15             int j;

16             /for （j = i-1; j>=0 && a[j]>temp; j--） {

17                 //将大于temp的往后移动一位

18                 a[j+1] = a[j];

19             }/

20             for （j = i-1; j>=0; j--） {

21                 //将大于temp的往后移动一位

22                 if（a[j]>temp）{

23                     a[j+1] = a[j];

24                 }else{

25                     break;

26                 }

27             }

28             a[j+1] = temp;

29         }

30         System.out.println（）;

31         System.out.println（排序之后：）;

32         for （int i = 0; i < a.length; i++） {

33             System.out.print（a[i]+ ）;

34         }

35     }

36 

37 }

　　4、解析

　　直接插入排序是稳定的排序。关于各类算法的稳定性解析可以参考http://www.cnblogs.com/Braveliu/archive/2013/01/15/2861201.html

　　文件初态不应时，直接插入排序所花费的时候有很大差别。若文件初态为正序，则每个待插入的记录只须要斗劲一次就可以或许找到合适的地位插入，故算法的时候错杂度为O（n），这时好的景象。若初态为反序，则第i个待插入记录须要斗劲i+1次才干找到合适地位插入，故时候错杂度为O（n2），这时最坏的景象。

　　直接插入排序的均匀时候错杂度为O（n2）。

②二分法插入排序（按二分法找到合适地位插入）

　　1、根蒂根基思惟：二分法插入排序的思惟和直接插入一样，只是找合适的插入地位的体式格式不合，这里是按二分法找到合适的地位，可以削减斗劲的次数。

　　2、实例

　　3、java实现

 1 package com.sort;

 2 

 3 public class 二分插入排序 {

 4     public static void main（String[] args） {

 5         int[] a={49，38，65，97，176，213，227，49，78，34，12，164，11，18，1};

 6         System.out.println（排序之前：）;

 7         for （int i = 0; i < a.length; i++） {

 8             System.out.print（a[i]+ ）;

 9         }

10         //二分插入排序

11         sort（a）;

12         System.out.println（）;

13         System.out.println（排序之后：）;

14         for （int i = 0; i < a.length; i++） {

15             System.out.print（a[i]+ ）;

16         }

17     }

18 

19     private static void sort（int[] a） {

20         for （int i = 0; i < a.length; i++） {

21             int temp = a[i];

22             int left = 0;

23             int right = i-1;

24             int mid = 0;

25             while（left<=right）{

26                 mid = （left+right）/2;

27                 if（temp<a[mid]）{

28                     right = mid-1;

29                 }else{

30                     left = mid+1;

31                 }

32             }

33             for （int j = i-1; j >= left; j--） {

34                 a[j+1] = a[j];

35             }

36             if（left != i）{

37                 a[left] = temp;

38             }

39         }

40     }

41 }

　　4、解析

　　当然，二分法插入排序也是稳定的。

　　二分插入排序的斗劲次数与待排序记录的初始状况无关，仅依附于记录的个数。当n较大时，比直接插入排序的最大斗劲次数少得多。但大于直接插入排序的最小斗劲次数。算法的移动次数与直接插入排序算法的雷同，最坏的景象为n2/2，好的景象为n，均匀移动次数为O（n2）。

③希尔排序

　　1、根蒂根基思惟：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有间隔为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1反复上述的分组和排序，直至所取的增量dt=1（dt<dt-l<…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。该办法本质上是一种分组插入办法。

　　2、实例

　3、java实现

 1 package com.sort;

 2 

 3 //不稳定

 4 public class 希尔排序 {

 5 

 6     

 7     public static void main（String[] args） {

 8         int[] a={49，38，65，97，76，13，27，49，78，34，12，64，1};

 9         System.out.println（排序之前：）;

10         for （int i = 0; i < a.length; i++） {

11             System.out.print（a[i]+ ）;

12         }

13         //希尔排序

14         int d = a.length;

15         while（true）{

16             d = d / 2;

17             for（int x=0;x<d;x++）{

18                 for（int i=x+d;i<a.length;i=i+d）{

19                     int temp = a[i];

20                     int j;

21                     for（j=i-d;j>=0&&a[j]>temp;j=j-d）{

22                         a[j+d] = a[j];

23                     }

24                     a[j+d] = temp;

25                 }

26             }

27             if（d == 1）{

28                 break;

29             }

30         }

31         System.out.println（）;

32         System.out.println（排序之后：）;

33         for （int i = 0; i < a.length; i++） {

34             System.out.print（a[i]+ ）;

35         }

36     }

37 

38 }

　　4、解析

　　我们知道一次插入排序是稳定的，但在不合的插入排序过程中，雷同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

　　希尔排序的时候机能优于直接插入排序，原因如下：

　　（1）当文件初态根蒂根基有序时直接插入排序所需的斗劲和移动次数均较少。

　　（2）当n值较小时，n和n2的差别也较小，即直接插入排序的好时候错杂度O（n）和最坏时候错杂度0（n2）差别不大。

　　（3）在希尔排序开端时增量较大，分组较多，每组的记录数量少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐削减，而各组的记录数量逐渐增多，但因为已经按di-1作为间隔排过序，使文件较接近于有序状况，所以新的一趟排序过程也较快。

　　是以，希尔排序在效力上较直接插人排序有较大的改进。

　　希尔排序的均匀时候错杂度为O（nlogn）。

二、选择排序

•思惟：每趟从待排序的记录序列中选择关键字小记录放置到已排序表的最前地位，直到全部排完。

•关键题目：在残剩的待排序记录序列中找到最小关键码记录。

•办法：

–直接选择排序

–堆排序

①简单的选择排序

　　1、根蒂根基思惟：在要排序的一组数中，选出小一个数与第一个地位的数互换；然后在剩下的数傍边再找小与第二个地位的数互换，如此轮回到倒数第二个数和最后一个数斗劲为止。

　　2、实例

　　3、java实现

 1 package com.sort;

 2 

 3 //不稳定

 4 public class 简单的选择排序 {

 5 

 6     public static void main（String[] args） {

 7         int[] a={49，38，65，97，76，13，27，49，78，34，12，64，1，8};

 8         System.out.println（排序之前：）;

 9         for （int i = 0; i < a.length; i++） {

10             System.out.print（a[i]+ ）;

11         }

12         //简单的选择排序

13         for （int i = 0; i < a.length; i++） {

14             int min = a[i];

15             int n=i; //最小数的索引

16             for（int j=i+1;j<a.length;j++）{

17                 if（a[j]<min）{  //找出小数

18                     min = a[j];

19                     n = j;

20                 }

21             }

22             a[n] = a[i];

23             a[i] = min;

24             

25         }

26         System.out.println（）;

27         System.out.println（排序之后：）;

28         for （int i = 0; i < a.length; i++） {

29             System.out.print（a[i]+ ）;

30         }

31     }

32 

33 }

　4、解析

　　简单选择排序是不稳定的排序。

　　时候错杂度：T（n）=O（n2）。

②堆排序

　　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 package com.sort;

 2 //不稳定

 3 import java.util.Arrays;

 4 

 5 public class HeapSort {

 6     public static void main（String[] args） {

 7         int[] a={49，38，65，97，76，13，27，49，78，34，12，64};

 8         int arrayLength=a.length;  

 9         //轮回建堆  

10         for（int i=0;i<arrayLength-1;i++）{  

11             //建堆  

12             buildMaxHeap（a，arrayLength-1-i）;  

13             //互换堆顶和最后一个元素  

14             swap（a，0，arrayLength-1-i）;  

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

16         }  

17     }

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

19     public static void buildMaxHeap（int[] data， int lastIndex）{

20          //从lastIndex处节点（最后一个节点）的父节点开端 

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

22             //k保存正在断定的节点 

23             int k=i;

24             //若是当前k节点的子节点存在  

25             while（k2+1<=lastIndex）{

26                 //k节点的左子节点的索引 

27                 int biggerIndex=2k+1;

28                 //若是biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在

29                 if（biggerIndex<lastIndex）{  

30                     //若果右子节点的值较大  

31                     if（data[biggerIndex]<data[biggerIndex+1]）{  

32                         //biggerIndex老是记录较大子节点的索引  

33                         biggerIndex++;  

34                     }  

35                 }  

36                 //若是k节点的值小于其较大的子节点的值  

37                 if（data[k]<data[biggerIndex]）{  

38                     //互换他们  

39                     swap（data，k，biggerIndex）;  

40                     //将biggerIndex付与k，开端while轮回的下一次轮回，从头包管k节点的值大于其阁下子节点的值  

41                     k=biggerIndex;  

42                 }else{  

43                     break;  

44                 }  

45             }

46         }

47     }

48     //互换

49     private static void swap（int[] data， int i， int j） {  

50         int tmp=data[i];  

51         data[i]=data[j];  

52         data[j]=tmp;  

53     } 

54 }

　　4、解析

　　堆排序也是一种不稳定的排序算法。

　　堆排序优于简单选择排序的原因：

　　直接选择排序中，为了从R[1..n]中选出关键字小记录，必须进行n-1次斗劲，然后在R[2..n]中选出关键字小记录，又须要做n-2次斗劲。事实上，后面的n-2次斗劲中，有很多斗劲可能在前面的n-1次斗劲中已经做过，但因为前一趟排序时未保存这些斗劲成果，所今后一趟排序时又反复履行了这些斗劲操纵。

　　堆排序可经由过程树形布局保存项目组斗劲成果，可削减斗劲次数。

　　堆排序的最坏时候错杂度为O（nlogn）。堆序的均匀机能较接近于最坏机能。因为建初始堆所需的斗劲次数较多，所以堆排序不合适于记录数较少的文件。

三、互换排序

①冒泡排序

　　1、根蒂根基思惟：在要排序的一组数中，对当前还未排好序的局限内的全部数，自上而下对相邻的两个数依次进行斗劲和调剂，让较大的数往下沉，较小的往上冒。即：每当两相邻的数斗劲后发明它们的排序与排序请求相反时，就将它们互换。

　　2、实例

　　3、java实现

 1 package com.sort;

 2 

 3 //稳定

 4 public class 冒泡排序 {

 5     public static void main（String[] args） {

 6         int[] a={49，38，65，97，76，13，27，49，78，34，12，64，1，8};

 7         System.out.println（排序之前：）;

 8         for （int i = 0; i < a.length; i++） {

 9             System.out.print（a[i]+ ）;

10         }

11         //冒泡排序

12         for （int i = 0; i < a.length; i++） {

13             for（int j = 0; j<a.length-i-1; j++）{

14                 //这里-i主如果每遍历一次都把大i个数沉到最底下去了，没有须要再调换了

15                 if（a[j]>a[j+1]）{

16                     int temp = a[j];

17                     a[j] = a[j+1];

18                     a[j+1] = temp;

19                 }

20             }

21         }

22         System.out.println（）;

23         System.out.println（排序之后：）;

24         for （int i = 0; i < a.length; i++） {

25             System.out.print（a[i]+ ）;

26         }

27     }

28 }

　　4、解析

　　冒泡排序是一种稳定的排序办法。　

•若文件初状为正序，则一趟起泡就可完成排序，排序码的斗劲次数为n-1，且没有记录移动，时候错杂度是O（n）

•若文件初态为逆序，则须要n-1趟起泡，每趟进行n-i次排序码的斗劲，且每次斗劲都移动三次，斗劲和移动次数均达到最大值∶O（n2）

•起泡排序均匀时候错杂度为O（n2）

②快速排序

　　1、根蒂根基思惟：选择一个基准元素，凡是选择第一个元素或者最后一个元素，经由过程一趟扫描，将待排序列分成两项目组，一项目组比基准元素小，一项目组大于便是基准元素，此时基准元素在其排好序后的正确地位，然后再用同样的办法递归地排序划分的两项目组。

　　2、实例

　　3、java实现

package com.sort;



//不稳定

public class 快速排序 {

    public static void main（String[] args） {

        int[] a={49，38，65，97，76，13，27，49，78，34，12，64，1，8};

        System.out.println（排序之前：）;

        for （int i = 0; i < a.length; i++） {

            System.out.print（a[i]+ ）;

        }

        //快速排序

        quick（a）;

        System.out.println（）;

        System.out.println（排序之后：）;

        for （int i = 0; i < a.length; i++） {

            System.out.print（a[i]+ ）;

        }

    }



    private static void quick（int[] a） {

        if（a.length>0）{

            quickSort（a，0，a.length-1）;

        }

    }



    private static void quickSort（int[] a， int low， int high） {

        if（low<high）{ //若是不加这个断定递归会无法退出导致客栈溢出异常

            int middle = getMiddle（a，low，high）;

            quickSort（a， 0， middle-1）;

            quickSort（a， middle+1， high）;

        }

    }



    private static int getMiddle（int[] a， int low， int high） {

        int temp = a[low];//基准元素

        while（low<high）{

            //找到比基准元素小的元素地位

            while（low<high && a[high]>=temp）{

                high--;

            }

            a[low] = a[high]; 

            while（low<high && a[low]<=temp）{

                low++;

            }

            a[high] = a[low];

        }

        a[low] = temp;

        return low;

    }

}

　　4、解析

　　快速排序是不稳定的排序。

　　快速排序的时候错杂度为O（nlogn）。

　　当n较大时应用快排斗劲好，当序列根蒂根基有序时用快排反而不好。

四、归并排序

　　1、根蒂根基思惟:归并（Merge）排序法是将两个（或两个以上）有序表归并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列归并为整体有序序列。

　　2、实例

　　3、java实现

 1 package com.sort;

 2 

 3 //稳定

 4 public class 归并排序 {

 5     public static void main（String[] args） {

 6         int[] a={49，38，65，97，76，13，27，49，78，34，12，64，1，8};

 7         System.out.println（排序之前：）;

 8         for （int i = 0; i < a.length; i++） {

 9             System.out.print（a[i]+ ）;

10         }

11         //归并排序

12         mergeSort（a，0，a.length-1）;

13         System.out.println（）;

14         System.out.println（排序之后：）;

15         for （int i = 0; i < a.length; i++） {

16             System.out.print（a[i]+ ）;

17         }

18     }

19 

20     private static void mergeSort（int[] a， int left， int right） {

21         if（left<right）{

22             int middle = （left+right）/2;

23             //对左边进行递归

24             mergeSort（a， left， middle）;

25             //对右边进行递归

26             mergeSort（a， middle+1， right）;

27             //归并

28             merge（a，left，middle，right）;

29         }

30     }

31 

32     private static void merge（int[] a， int left， int middle， int right） {

33         int[] tmpArr = new int[a.length];

34         int mid = middle+1; //右边的肇端地位

35         int tmp = left;

36         int third = left;

37         while（left<=middle && mid<=right）{

38             //从两个数组中拔取较小的数放入中心数组

39             if（a[left]<=a[mid]）{

40                 tmpArr[third++] = a[left++];

41             }else{

42                 tmpArr[third++] = a[mid++];

43             }

44         }

45         //将残剩的项目组放入中心数组

46         while（left<=middle）{

47             tmpArr[third++] = a[left++];

48         }

49         while（mid<=right）{

50             tmpArr[third++] = a[mid++];

51         }

52         //将中心数组复制回原数组

53         while（tmp<=right）{

54             a[tmp] = tmpArr[tmp++];

55         }

56     }

57 }

　　4、解析

　　归并排序是稳定的排序办法。

　　归并排序的时候错杂度为O（nlogn）。

　　速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，然则各子项相对有序的数列。

五、基数排序

　　1、根蒂根基思惟：将所有待斗劲数值（正整数）同一为同样的数位长度，数位较短的数前面补零。然后，从最低位开端，依次进行一次排序。如许从最低位排序一向到高位排序完成今后，数列就变成一个有序序列。

　　2、实例

　　3、java实现

 1 package com.sort;

 2 

 3 import java.util.ArrayList;

 4 import java.util.List;

 5 //稳定

 6 public class 基数排序 {

 7     public static void main（String[] args） {

 8         int[] a={49，38，65，97，176，213，227，49，78，34，12，164，11，18，1};

 9         System.out.println（排序之前：）;

10         for （int i = 0; i < a.length; i++） {

11             System.out.print（a[i]+ ）;

12         }

13         //基数排序

14         sort（a）;

15         System.out.println（）;

16         System.out.println（排序之后：）;

17         for （int i = 0; i < a.length; i++） {

18             System.out.print（a[i]+ ）;

19         }

20     }

21 

22     private static void sort（int[] array） {

23         //找到最大数，断定要排序几趟

24         int max = 0;

25         for （int i = 0; i < array.length; i++） {

26             if（max<array[i]）{

27                 max = array[i];

28             }

29         }

30         //断定位数

31         int times = 0;

32         while（max>0）{

33             max = max/10;

34             times++;

35         }

36         //建树十个队列

37         List<ArrayList> queue = new ArrayList<ArrayList>（）;

38         for （int i = 0; i < 10; i++） {

39             ArrayList queue1 = new ArrayList（）;

40             queue.add（queue1）;

41         }

42         //进行times次分派和收集

43         for （int i = 0; i < times; i++） {

44             //分派

45             for （int j = 0; j < array.length; j++） {

46                 int x = array[j]％（int）Math.pow（10， i+1）/（int）Math.pow（10， i）;

47                 ArrayList queue2 = queue.get（x）;

48                 queue2.add（array[j]）;

49                 queue.set（x，queue2）;

50             }

51             //收集

52             int count = 0;

53             for （int j = 0; j < 10; j++） {

54                 while（queue.get（j）.size（）>0）{

55                     ArrayList<Integer> queue3 = queue.get（j）;

56                     array[count] = queue3.get（0）;

57                     queue3.remove（0）;

58                     count++;

59                 }

60             }

61         }

62     }

63 }

　　4、解析

　　基数排序是稳定的排序算法。

　　基数排序的时候错杂度为O（d（n+r）），d为位数，r为基数。

总结：

一、稳定性:

　稳定：冒泡排序、插入排序、归并排序和基数排序

　　不稳定：选择排序、快速排序、希尔排序、堆排序

二、均匀时候错杂度

　　O（n^2）:直接插入排序，简单选择排序，冒泡排序。

　　在数据范围较小时（9W内），直接插入排序，简单选择排序差不久不多。当数据较大时，冒泡排序算法的时候价格高。机能为O（n^2）的算法根蒂根基上是相邻元素进行斗劲，根蒂根基上都是稳定的。

　　O（nlogn）:快速排序，归并排序，希尔排序，堆排序。

　　此中，快排是好的，其次是归并和希尔，堆排序在数据量很大时结果明显。

三、排序算法的选择

　　1.数据范围较小

　　（1）待排序列根蒂根基序的景象下，可以选择直接插入排序；

　　（2）对稳定性不作请求宜用简单选择排序，对稳定性有请求宜用插入或冒泡

　　2.数据范围不是很大

　　（1）完全可以用内存空间，序列混乱无序，对稳定性没有请求，快速排序，此时要付出log（N）的额外空间。

　　（2）序列本身可能有序，对稳定性有请求，空间容许下，宜用归并排序

　　3.数据范围很大

　　（1）对稳定性有求，则可推敲归并排序。

　　（2）对稳定性没请求，宜用堆排序

　　4.序列初始根蒂根基有序（正序），宜用直接插入，冒泡

参考材料:

　　http://blog.csdn.net/without0815/article/details/7697916

　　http://gengning938.blog.163.com/blog/static/128225381201141121326346/

原来，再大的房子，再大的床，没有相爱的人陪伴，都只是冰冷的物质。而如果身边有爱人陪伴，即使房子小，床小，也觉得无关紧要，因为这些物质上面有了爱的温度，成了家的元素。—— 何珞《婚房》#书摘#

分享到：

相关文章

按版本划分

按功能划分

企业管理软件

各类排序算法的解析及java实现