排序算法总结(基于Java实现)

前言

下面会讲到一些简单的排序算法(均基于java实现),并给出实现和效率分析。

使用的基类如下:

注意:抽象函数应为public的,我就不改代码了

  1. public abstract class Sortable {
  2. protected String LABLE="排序算法";
  3. //比较两个数(使用了Integer中sort的源码)
  4. protected int compare(int x, int y) {
  5. return (x < y) ? -1 : ((x == y) ? 0 : 1);
  6. }
  7. //同上,不过返回改为bool
  8. protected boolean less(int x,int y){
  9. return compare(x,y) <0;
  10. }
  11. //交换数组中的两个值
  12. protected void exch(int[] a,int i,int j){
  13. Integer temp = a[i];
  14. a[i] = a[j];
  15. a[j] = temp;
  16. }
  17. //子类需要实现的排序算法
  18. public abstract void sort(int[] a);
  19. public String getLABLE() {
  20. return LABLE;
  21. }
  22. }

冒泡排序

最常见的,毕竟老师教给我们的的第一种排序算法。实现起来很简单,不过实际应用很少(正常情况下),复杂度O(n²)。

原理

趟一趟的比,每一趟中,循环剩余的数,和后一个进行比较,若比它小则交换。这样一趟下来最小的在第一个,最大的在最后一个。总共比n-1趟。

实现

  1. import com.anxpp.sort.base.Sortable;
  2. /**
  3. * 最简单的冒泡排序
  4. *
  5. * @author anxpp.com
  6. * 原理:比较相邻两个元素,从第一对开始比较一直到最后一对,若顺序不对就交换(感觉就像冒泡一样)。
  7. * 一趟比较后,最大(或最小)的会位于最后的位置,然后再以类似方式比较前面的元素。
  8. */
  9. public class BubbleSort extends Sortable {
  10. public BubbleSort(){
  11. super.LABLE = "冒泡排序";
  12. }
  13. @Override
  14. public void sort(int[] a) {
  15. for(int i=0;i<a.length-1;i++){
  16. for(int j=0;j<a.length-1-i;j++){
  17. if(less(a[j+1],a[j])){
  18. exch(a,j,j+1);
  19. }
  20. }
  21. }
  22. }
  23. }

优化

上面的算法,无论的你的数据怎么样,始终都要比n²次,效率很低。若你的数据局部有序,经过几趟交换以后,已经有序,则不用继续往下比。效率会高很多(绝大多数情况下)。优化代码如下:

  1. import com.anxpp.sort.base.Sortable;
  2. /**
  3. * 设置标志优化后的冒泡排序
  4. * @author anxpp.com
  5. *
  6. * 原理:比较相邻两个元素,从第一对开始比较一直到最后一对,若顺序不对就交换(感觉就像冒泡一样)。
  7. * 一趟比较后,最大(或最小)的会位于最后的位置,然后再以类似方式比较前面的元素。
  8. * 优化:传统的冒泡排序,总是要比较那么多次,如果在某趟完成后,并无交换表示数据已经有序,所以设置
  9. * 一个标志,如某趟比较完成后没有发生,则不再继续后面的运算直接返回即可,其实,有时候效率反而会比传统的低!
  10. * 其他:据说分而治之也能有用到冒泡,这里就不深究了...
  11. */
  12. public class BetterBubbleSort extends Sortable {
  13. public BetterBubbleSort(){
  14. super.LABLE = "冒泡排序优化";
  15. }
  16. @Override
  17. public void sort(int[] a) {
  18. boolean didSwap;
  19. for(int i=0;i<a.length-1;i++){
  20. didSwap = false;
  21. for(int j=0;j<a.length-1-i;j++){
  22. if(less(a[j+1],a[j])){
  23. exch(a,j,j+1);
  24. didSwap = true;
  25. }
  26. }
  27. if(!didSwap) return ;
  28. }
  29. }
  30. }

选择排序

和冒泡复杂度一样O(n²),但是时间上可能会比冒泡稍微快一点,因为交换的次数比冒泡少。

原理

选择排序可以说是最好理解的算法。就是每次遍历一趟,找出最小的数,放到最前端。(这里说的是最前,是指无序的队列中的最前)

排序算法总结(基于Java实现)

实现

  1. import com.anxpp.sort.base.Sortable;
  2. /**
  3. * 选择排序
  4. * @author anxpp.com
  5. *
  6. */
  7. public class SelectionSort extends Sortable {
  8. public SelectionSort(){
  9. super.LABLE = "选择排序";
  10. }
  11. @Override
  12. public void sort(int[] a) {
  13. for(int i=0;i<a.length;i++){
  14. int min=i;
  15. for(int j=i+1;j<a.length;j++){
  16. if(less(a[j],a[min])){
  17. min = j;
  18. }
  19. }
  20. exch(a,i,min);
  21. }
  22. }
  23. }

插入排序

时间复杂度O(n²)。

原理

遍历未排序序列。把未排序数列的第一个数和已排序数列的每一个数比较,若比它大则交换。经典的理解方式就是理解成摸牌时候理牌的顺序。我上面的实现是直接交互数字,若是把大的数直接往后移效率还会更高。

实现

  1. import com.anxpp.sort.base.Sortable;
  2. /**
  3. * 插入排序
  4. * @author anxpp
  5. *
  6. */
  7. public class InsertionSort extends Sortable {
  8. public InsertionSort(){
  9. super.LABLE = "插入排序";
  10. }
  11. @Override
  12. public void sort(int[] a) {
  13. for(int i=1;i<a.length;i++){
  14. for(int j=i;j>0;j--){
  15. if(less(a[j],a[j-1])){
  16. exch(a,j,j-1);
  17. }
  18. else break;
  19. }
  20. }
  21. }
  22. }

适合插入排序的数据

当你的数据是基本有序的时候且数据量小,利用插入排序的时候,效率会很高。若数据为逆序的话,效率很低。

希尔排序

可以看出是插入排序的一种优化,或者是预处理。希尔排序就是先进行h-sort,也就是让间隔为h的元素都是有序的。普通的插入排序就是1-sort。

原理

主要就是选定一个h的有序数组来进行预排序。这样最后进行插入排序的时候,能使数据局部有序。就算交换的话,交换的次数也不会很多。这样h序列称为递增序列。希尔的性能很大部分取决于递增序列.一般来说我们使用这个序列3x + 1.

排序算法总结(基于Java实现)

实现

  1. import com.anxpp.sort.base.Sortable;
  2. /**
  3. * 希尔排序
  4. * @author anxpp.com
  5. *
  6. */
  7. public class ShellSort extends Sortable {
  8. public ShellSort(){
  9. super.LABLE = "希尔排序";
  10. }
  11. @Override
  12. public void sort(int[] a) {
  13. int h=1;
  14. while(h<a.length/3){
  15. h=3*h+1;
  16. }
  17. while(h>=1){
  18. for(int i=h;i<a.length;i++){
  19. for(int j=i;j>=h;j=j-h){
  20. if(less(a[j],a[j-h])){
  21. exch(a,j,j-h);
  22. }
  23. else break;
  24. }
  25. }
  26. h=h/3;
  27. }
  28. }
  29. }

性能

对于希尔排序的性能其实无法准确表示。介于O(nlogn)和O(n²)之间,大概在n的1.5次幂左右。

希尔排序对于中大型数据的排序效率是很高的,而且占用空间少,代码量短。而且就算是很大的数据,用类似快排这种高性能的排序方法,也仅仅只比希尔快两倍或者不到。

归并排序

复杂度O(nlogn).

核心思想就是采用分而治之的方法,递归的合并两个有序的数组。效率比较高,缺点是空间复杂度高,会用到额外的数组。

原理

核心代码是合并的函数。合并的前提是保证左右两边的数组分别有序,在合并之前和之后在Java中我们可以用断言来保证数组有序。合并的原理其实也很简单,先把a数组中的内容复制到额外储存的temp数组中去。分别用两个index指向a数组的起始位置和中间位置,保证a数组左右两边有序,比如i,j。现在开始从头扫描比较左右两个数组,若a[i]<=a[j],则把a[i]放到temp数组中去,且i向前走一步。反正则放a[j],且j走一步。若其中一个数组走完了,则把另一个数组剩余的数直接放到temp数组中。我们用递归的方式来实现左右两边有序。递归到数组只有1个数时肯定是有序的,再合并2个数,再退出来合并4个数,以此类推。

排序算法总结(基于Java实现)

排序算法总结(基于Java实现)

实现

  1. import com.anxpp.sort.base.Sortable;
  2. /**
  3. * 归并排序
  4. * @author anxpp.com
  5. *
  6. */
  7. public class MergeSort extends Sortable {
  8. public MergeSort(){
  9. super.LABLE = "归并排序";
  10. }
  11. int[] temp ;
  12. private void merge(int[] a, int l, int m, int h){
  13. for(int i=l;i<=h;i++){
  14. temp[i]=a[i];
  15. }
  16. int i=l;
  17. int j=m+1;
  18. for(int k=l;k<=h;k++){
  19. if(i>m) a[k]=temp[j++];
  20. else if(j>h) a[k]=temp[i++];
  21. else if(less(temp[i],temp[j])) a[k]=temp[i++];
  22. else a[k] = temp[j++];
  23. }
  24. }
  25. private void sort(int[] a,int l,int h) {
  26. if(l<h){
  27. int mid = (l+h)/2;
  28. sort(a,l,mid);
  29. sort(a,mid+1,h);
  30. if (!less(a[mid+1], a[mid])) return;
  31. merge(a,l,mid,h);
  32. }
  33. }
  34. @Override
  35. public void sort(int[] a) {
  36. temp = new int[a.length];
  37. sort(a,0,a.length-1);
  38. }
  39. }

优化

归并排序对小数组排序时,由于会有多重的递归调用,所以速度没有插入排序快。可以在递归调用到小数组时改采用插入排序。小数组的意思是差不多10个数左右。

如果递归时判断已经有序则不用继续递归。也可以增加效率。

  1. private void sort(int[] a,int l,int h) {
  2. if(l<h){
  3. int mid = (l+h)/2;
  4. sort(a,l,mid);
  5. sort(a,mid+1,h);
  6. if (!less(a[mid+1], a[mid])) return;
  7. merge(a,l,mid,h);
  8. }
  9. }

另外在合并时交互两个数组的顺序,能节省复制数组到辅助数组的时间,但节省不了空间。

排序算法总结(基于Java实现)

适用范围

如果你对空间要求不高,且想要一个稳定的算法。那么可以使用归并排序。

快速排序

传说中最快的排序算法,听说能裸写快排,月薪可上10k...

快排平均情况下时间复杂度O(nlogn),最糟糕情况O(n²)。O(n²)主要是因为选定的主元是极端值造成的,比如说最大值,最小值。不过这种情况一般很少出现,所以在进行快排之前我们需要对数组进行乱序,尽量避免这种情况的发生。

原理

第一步打乱数组。

然后也是分治法。归并是先分再合并。快排是先排序再分别排序两边。

排序过程核心思想是为了选出一个数,把数组分成左右两边,左边比主元小,右边比主元大。

选定第一个数作为主元。然后设定两个index指向数组首尾,比如i,j。接着从两边向中间扫描,分别用a[i]和a[j]和主元比较。若两边位置不对则交换a[i]和a[j],比如说a[i]在扫描过程中遇到a[i]>主元,那么则停止扫描,因为我们需要左边的数小于主元,反正右边也一样等到a[j]也停下来,则交换a[i]和a[j]。

得到中间的位置之后再分别左右递归排序。

排序算法总结(基于Java实现)

排序算法总结(基于Java实现)

实现

  1. import com.anxpp.sort.base.Sortable;
  2. /**
  3. * 快速排序
  4. * @author u
  5. *
  6. * 原理:选择一个基准元素,通过一趟扫描,将数据分成大于和不大于基准元素的两部分(分别在基准元素的两边),此时
  7. * 基准元素就在未来排好后的正确位置,然后递归使用类似的方法处理这个基准元素两边的部分。
  8. * 既然用了递归,难免在空间上的效率不高...
  9. * 平均性能通常被认为是最好的
  10. */
  11. public class quickSort extends Sortable {
  12. public quickSort(){
  13. super.LABLE = "快速排序";
  14. }
  15. /**
  16. *
  17. * @param a 要排序的列表
  18. * @param low 左边位置
  19. * @param high 右边位置
  20. */
  21. private void sort(int[] a,int low,int high){
  22. //左
  23. int l =low;
  24. //右
  25. int h = high;
  26. //基准值
  27. int k = a[low];
  28. //判断一趟是否完成
  29. while(l<h){
  30. //若顺序正确就比较下一个
  31. while(l<h&&a[h]>=k)
  32. h--;
  33. if(l<h){
  34. int temp = a[h];
  35. a[h] = a[l];
  36. a[l] = temp;
  37. l++;
  38. }
  39. while(l<h&&a[l]<=k)
  40. l++;
  41. if(l<h){
  42. int temp = a[h];
  43. a[h] = a[l];
  44. a[l] = temp;
  45. h--;
  46. }
  47. }
  48. if(l>low) sort(a,low,l-1);
  49. if(h<high) sort(a,l+1,high);
  50. }
  51. @Override
  52. public void sort(int[] a) {
  53. sort(a,0,a.length-1);
  54. }
  55. }

优化

第一步的随机打乱数组,虽然会耗费一定时间,但却是必要的。同样的小数组的排序,快排不如插入排序。所以小数组可以直接采用插入排序。主元的选择方式可以有多种,比如随机选择主元。或者选取三个数,取中位数为主元,但是会耗费一定时间。

适用范围

虽然快速排序是不稳定的。但快速排序通常明显比其他Ο(nlogn)算法更快,因为它的内部循环很小。快速排序在对重复数据的排序时,会重复划分数据进行排序。虽然性能也还行,但这里可以进行改进,就是下面介绍的三向切分排序。

三向切分

快速排序的一种改进,使快排在有大量重复元素的数据,同样能保持高效。

原理

基本原理和快排差不多。三向切分的时候在划分数组时不是分为两组,而是分成三组。

  • 小于主元
  • 和主元相等
  • 大于主元

排序算法总结(基于Java实现)

实现

  1. public class ThreeWaySort extends Sortable {
  2. public void sort(int[] a,int l ,int h) {
  3. if(l>=h) return;
  4. int v = a[l];
  5. int i=l;
  6. int lv=l;
  7. int gh=h;
  8. while(i<=gh){
  9. int cmpIndex = compare(a[i],v);
  10. if(cmpIndex<0) exch(a,i++,lv++);
  11. else if(cmpIndex>0) exch(a,i,gh--);
  12. else i++;
  13. }
  14. sort(a,l,lv-1);
  15. sort(a,gh+1,h);
  16. }
  17. @Override
  18. void sort(int[] a) {
  19. sort(a,0,a.length-1);
  20. }
  21. }

堆排序

时间复杂度O(nlogn),堆排序主要用二叉堆实现,在讲堆排序之前我们可以要先了解下二叉堆。

二叉堆

所谓的二叉堆用一颗二叉树表示,也就是每一个节点都大于它的左右子节点。也就是说根节点是最大的。

二叉树用数组存储,可以用下标来表示节点。比如i这个节点的父节点为i/2,左儿子为2*i,右儿子为2*i+1.

堆的操作主要有两种上浮和下沉。主要对应两种情况,比如在数组末尾添加节点,此时需要上浮节点,保证二叉堆的特点。反之在替换根节点是则需要下沉操作。

原理

分为两步。

  • 把数组排成二叉堆的顺序
  • 调换根节点和最后一个节点的位置,然后对根节点进行下沉操作。

排序算法总结(基于Java实现)

实现

适用范围

堆排序也是不稳定的。

堆排序在空间和时间上都是O(nlogn),且没有最糟情况,但在平均情况下比快排慢。

所以现在大部分应用都是用的快排,因为它的平均效率很高,几乎不会有最糟情况发生。

但如果你的应用非常非常重视性能的保证,比如一些医学上的监控之类的。

那么可以使用堆排序。还有一个堆排序的缺点,是它无法利用缓存,几乎很少和相邻元素的比较。

运行时间比较

使用下面的代码测试以上排序算法:

  1. import java.util.Random;
  2. import com.anxpp.sort.base.Sortable;
  3. /**
  4. * 测试排序算法
  5. * @author anxpp.com
  6. *
  7. */
  8. public class TestSort {
  9. //需要排序的数字长度为LEN
  10. private final static int LEN = 30000;
  11. //最大值为MAX
  12. private final static int MAX = 99999;
  13. public static void main(String[] args){
  14. //初始化排序算法
  15. Sortable[] sortables = {
  16. new BubbleSort(),new BetterBubbleSort(),new SelectionSort(),
  17. new InsertionSort(),new ShellSort(),new MergeSort(),
  18. new BetterMergeSort(),new quickSort(),new ThreeWayQuickSort()};
  19. //产生源数据
  20. Random random = new Random();
  21. random.setSeed(System.currentTimeMillis());
  22. int[][] a = new int[sortables.length][LEN];
  23. int i = 0;
  24. while(i++ < LEN-1){
  25. int num = random.nextInt(MAX);
  26. int j = 0;
  27. while(j<sortables.length)
  28. a[j++][i] = num;
  29. }
  30. //排序
  31. for(i = 0;i<sortables.length;i++){
  32. System.out.println(sortables[i].getLABLE()+":");
  33. // print(a[i]);
  34. // sortTime(a[i],sortables[i]);
  35. System.out.println(sortTime(a[i],sortables[i]));
  36. // print(a[i]);
  37. }
  38. }
  39. public static int sortTime(int[] a,Sortable sortable){
  40. long start = System.currentTimeMillis();
  41. sortable.sort(a);
  42. return (int) (System.currentTimeMillis()-start);
  43. }
  44. public static void print(int[] a){
  45. for(int i = 0;i<a.length;i++)
  46. System.out.print(a[i] + ",");
  47. System.out.println();
  48. }
  49. }

下面是本人的一次运行结果:

  1. 冒泡排序:
  2. 2348
  3. 冒泡排序优化:
  4. 2660
  5. 选择排序:
  6. 250
  7. 插入排序:
  8. 907
  9. 希尔排序:
  10. 12
  11. 归并排序:
  12. 7
  13. 归并排序优化:
  14. 5
  15. 快速排序:
  16. 6
  17. 三向切分快速排序:
  18. 15

排序算法总结(基于Java实现)

推荐一个很好的网站,对各种算法进行了总结,和动画描述:sorting-algorithms

上一篇:STM32F0xx_FLASH编程(片内)配置详细过程


下一篇:排序算法大汇总 Java实现