常用排序算法

Posted on   |   In   |   visitors

忙碌了一整个星期公司布置的任务，如今周末终于能抽出时间继续自己在互联网技术上的学习，尽管现阶段是学校安排的考试周，但也无法阻止我对新技术的学习热情。因为计划是寒假就开始leetcode的学习之旅，所以今天先总结一篇学习到的关于排序的算法，后面也会继续记录自己在刷leetcode时的感悟，代码将上传至我的github，欢迎star和fork。

当然，作为一个Java工程师，所以里面的算法都是用Java语言实现的，不过其实不管你用的是哪种语言，实现该算法的思路都是一样的，所以借鉴此篇文章的你即使用的不是Java，看完此片文章的实现思路及其实现代码后你也是可以用其他语言实现的～

前言

查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中，但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。那么常用的排序算法有哪些呢？本篇文章要介绍的排序算法，按照排序的效率分有以下10种:

  • 1.简单排序:冒泡排序、(直接)选择排序、(直接)插入排序。
  • 2.高效排序:快速排序、堆排序、希尔排序。
  • 3.基于分治递归思想的:归并排序。
  • 4.线性排序:计数排序、桶排序、基数排序。

按照排序的方式又可分为:

  • 1.插入排序:直接插入排序、希尔排序。
  • 2.选择排序:直接选择排序、堆排序。
  • 3.交换排序:冒泡排序、快速排序。
  • 4.线性排序:计数排序、基数排序、桶排序;其中基数排序又叫桶排序;
  • 5.递归排序:归并排序。

对于这些排序，我们需要掌握比较各自的优劣、各种算法的思想及其使用场景，还有要会分析算法的时间和空间复杂度，必要时要熟练写出代码。我们可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的，需要结合具体的需求和场景来选择甚至组合使用，才能达到高效稳定的目的。所以有句话叫做:没有最好的排序，只有最适合的排序。

下面我将分别介绍以上提出的这10种排序的思想及其算法实现，为了便于讲解，统一采取从小到大的排序方法。

1.简单排序之冒泡排序

1.1冒泡排序实现思想

冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把大的数交换到最后面(从小到大排序)。这个过程类似于水泡向上升一样，因此而得名。

举个栗子，对5,3,8,6,4这个无序序列进行冒泡排序。第一次冒泡:从前向后冒泡，5和3比较，5大所以将5和3交换，序列变成3，5，8，6，4;同理5和8比较，5比8小所以不交换;然后8和6比较，8大所以将8和6交换，序列变成3，5，6，8，4;然后8和4比较，进行8和4的交换，这样一次冒泡就完了，结果是将最大的数字8换到了最后面。对剩下的序列依次进行第二次冒泡、…、第n次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。

1.2冒泡排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class BubbleSort {
    
    public static void bubbleSort(int[] arr) {//将要排序的数字放入一个数组中
    	  //判断需要排序的数组是否为空，为空则不进行排序
        if(arr == null || arr.length == 0)
            return ;
        //i控制外循环即总共需要将多少个数字进行排序，j控制内循环即每次循环都会将最大的数排到右边
        for(int i=0; i<arr.length-1; i++) {
            for(int j=0; j<arr.length-i-1; j++) {
            		//如果前面的数字大于后面的数字就将前面的数字和后面的数字进行交换，直接最大的数字被排到最右侧
                if(arr[j] > arr[j+1]) {
                    swap(arr, j+1, j);
                }
            }
        }
    }
    
    //交换两个数字的位置
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2.简单排序之选择排序

2.1选择排序实现思路

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最大的元素放到最右边。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。

举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序。第一次选择排序:首先要循环遍历该数组，选择整体中5以外的最小数来和5交换，遍历该数组时发现3是最小的数字，那么就会拿3和5交换，一次遍历和排序后就变成了3,5,8,6,4，实现了将最小的数字放在最前面。对剩下的序列依次进行第二次选择和交换、…、第n次选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)。

2.2选择排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class SelectSort {
    
    public static void selectSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        //
        int minIndex = 0;
        for(int i=0; i<arr.length-1; i++) { //只需要比较n-1次
        	  //将数组中的第一个数arr[i]即arr[minIndex]作为基准，遍历其后面所有的数字，只要出现比这个数小的，那么就记下这个数的下标并赋给minIndex，遍历完后若该minIndex不等于i，说明找到了最小的值，就将这个数字下标为minIndex的值与基准数字交换之。
            minIndex = i;
            for(int j=i+1; j<arr.length; j++) { //从i+1开始比较，因为minIndex默认为i了，i就没必要比了。
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            if(minIndex != i) { //如果minIndex不为i，说明找到了更小的值，交换之。
                swap(arr, i, minIndex);
            }
        }
        
    }
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

3.简单排序之插入排序

3.1插入排序实现思路

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。

举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置是正确的，想一下在拿到第一张牌的时候，没必要整理。然后第二张牌3要插到5前面，所以把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后拿到第三张牌时8不用动，拿到第四张牌6时要插在8前面，此时8后移一位，拿到第五张牌4时，要插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。

3.2插入排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class InsertSort {
    
    public static void insertSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
            
        //这里首先要假设第一个数位置是正确的(arr[0]是第一张牌)；因为要往后移动数字，必须要假设第一个。然后将第二个数字arr[1]比作打扑克时拿到的第二张牌
        //i依旧控制需要将多少个数字进行排序(n个数字，n-1次排序，为啥？比如只有两个数字，你肯定只需要进行1次排序啊)
        for(int i=1; i<arr.length; i++) { 
            
            int j = i;//第一次循环时将第二个数字的下标赋给j
            int target = arr[j]; //第一次循环时将第二个数字赋值给target(即保留待插入元素)
            
            //第一次循环时如果第二个数字小于第一个数字，就将第一个数字后移(后面的循环中即将前面的数字都后移一位)
            while(j > 0 && arr[j] < arr[j-1]) {
                arr[j] = arr[j-1];
                //然后将第二个数字插入到第一个位置 (后面的循环中即将待插入数字插入到前面空出的地方)
                arr[j - 1] = temp;
                j --;//将j － 1，继续调整
            }     

        }
            
    }

}

4.高效排序之快速排序

4.1快速排序实现思路

快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算法。快速排序虽然高端，但其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是同时比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

举个栗子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。

第一次排序:用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。

首先设置i,j两个指针分别指向两端(即i指向5，j指向4)，j指针先扫描（思考一下为什么？）4比5小停止。然后i扫描，8比5大停止。交换i,j位置。

然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。

一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。

上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。

快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。

4.2快速排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class QuickSort {
    //一次划分
    public static int partition(int[] arr, int left, int right) {
        int pivotKey = arr[left];
        int pivotPointer = left;
        
        while(left < right) {
            while(left < right && arr[right] >= pivotKey)
                right --;
            while(left < right && arr[left] <= pivotKey)
                left ++;
            swap(arr, left, right); //把大的交换到右边，把小的交换到左边。
        }
        swap(arr, pivotPointer, left); //最后把pivot交换到中间
        return left;
    }
    
    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right)
            return ;
        int pivotPos = partition(arr, left, right);
        //通过上面的partition方法，一次排序后就出现:中间右边的数都比中间的基准数要大、中间左边的数都比中间的基准数要小得规律。这样接下来分两次排序:将中间左边的数进行快速排序、将中间右边的数进行快速排序即可。
        quickSort(arr, left, pivotPos-1);
        quickSort(arr, pivotPos+1, right);
    }
    
    public static void sort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        quickSort(arr, 0, arr.length-1);
    }
    
    //交换的是left、right下标对应的数组元素，而不是交换的left和right的值
    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
    
}

其实上面的代码还可以再优化，上面代码中基准数已经在pivotKey中保存了，所以不需要每次交换都设置一个temp变量，在交换左右指针的时候只需要先后覆盖就可以了。这样既能减少空间的使用还能降低赋值运算的次数。优化代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class QuickSort {
    
    /**
     * 划分
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partition(int[] arr, int left, int right) {
        int pivotKey = arr[left];
        
        while(left < right) {
            while(left < right && arr[right] >= pivotKey)
                right --;
            arr[left] = arr[right]; //把小的移动到左边
            while(left < right && arr[left] <= pivotKey)
                left ++;
            arr[right] = arr[left]; //把大的移动到右边
        }
        arr[left] = pivotKey; //最后把pivot赋值到中间
        return left;
    }
    
    /**
     * 递归划分子序列
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right)
            return ;
        int pivotPos = partition(arr, left, right);
        quickSort(arr, left, pivotPos-1);
        quickSort(arr, pivotPos+1, right);
    }
    
    public static void sort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        quickSort(arr, 0, arr.length-1);
    }
    
}

总结快速排序的思想：冒泡+二分+递归分治，慢慢体会吧。

5.高效排序之堆排序

5.1堆排序实现思路

堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。

首先，实现堆排序需要解决两个问题：

  1. 如何由一个无序序列键成一个堆？
  2. 如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。

第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。

从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，由此筛选即可。举个栗子：

49,38,65,97,76,13,27,49序列的堆排序建初始堆和调整的过程如下图:


5.2堆排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class HeapSort {
    
    /**
     * 堆筛选，除了start之外，start~end均满足大顶堆的定义。
     * 调整之后start~end称为一个大顶堆。
     * @param arr 待调整数组
     * @param start 起始指针
     * @param end 结束指针
     */
    public static void heapAdjust(int[] arr, int start, int end) {
        int temp = arr[start];
        
        for(int i=2*start+1; i<=end; i*=2) {
            //左右孩子的节点分别为2*i,2*i+1
            
            //选择出左右孩子较大的下标
            if(i < end && arr[i] < arr[i+1]) {
                i ++; 
            }
            if(temp >= arr[i]) {
                break; //已经为大顶堆，=保持稳定性。
            }
            arr[start] = arr[i]; //将子节点上移
            start = i; //下一轮筛选
        }
        
        arr[start] = temp; //插入正确的位置
    }
    
    
    public static void heapSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        
        //建立大顶堆
        for(int i=arr.length/2; i>=0; i--) {
            heapAdjust(arr, i, arr.length-1);
        }
        
        for(int i=arr.length-1; i>=0; i--) {
            swap(arr, 0, i);
            heapAdjust(arr, 0, i-1);
        }
        
    }
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

6.高效排序之希尔排序

6.1希尔排序实现思路

希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。

希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

举个栗子，见下图:

从上述排序过程可见，希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。如上面的例子，第一堂排序时的增量为5，第二趟排序的增量为3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。

希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n^1.3)。

6.2希尔排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class ShellSort {

	//排序
    public static void shellSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        int d = arr.length / 2;
        while(d >= 1) {
            shellInsert(arr, d); //调用下面的插入方法
            d /= 2;
        }
    }

    
    /**
     * 希尔排序的一趟插入
     * @param arr 待排数组
     * @param d 增量
     */
    public static void shellInsert(int[] arr, int d) {
        for(int i=d; i<arr.length; i++) {
            int j = i - d;
            int temp = arr[i];    //记录要插入的数据  
            while (j>=0 && arr[j]>temp) {  //从后向前，找到比其小的数的位置   
                arr[j+d] = arr[j];    //向后挪动  
                arr[j] = temp;
                j -= d;  
            }    
        }
    }
}

7.基于分治递归思想的归并排序

7.1归并排序实现思路

归并排序是另一种不同的排序方法，因为归并排序使用了递归分治的思想，所以理解起来比较容易。其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列;然后把子序列看成两个有序的子子序列，然后合并这两个子子序列;然后…倒着来看，其实就是先两两合并，然后四四合并，最终形成一个有序序列。空间复杂度为O(n)，时间复杂度为O(nlogn)。

举个栗子，见下图:

7.2归并排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class MergeSort {
    
    public static void mergeSort(int[] arr) {
        mSort(arr, 0, arr.length-1);
    }

    /**
     * 递归分治
     * @param arr 待排数组
     * @param left 左指针
     * @param right 右指针
     */
    public static void mSort(int[] arr, int left, int right) {
        if(left >= right)
            return ;
        int mid = (left + right) / 2;
        
        mSort(arr, left, mid); //递归排序左边
        mSort(arr, mid+1, right); //递归排序右边
        merge(arr, left, mid, right); //合并
    }
    
    /**
     * 合并两个有序数组
     * @param arr 待合并数组
     * @param left 左指针
     * @param mid 中间指针
     * @param right 右指针
     */
    public static void merge(int[] arr, int left, int mid, int right) {
        //[left, mid] [mid+1, right]
        int[] temp = new int[right - left + 1]; //中间数组
        
        int i = left;
        int j = mid + 1;
        int k = 0;
        
        //执行完这个while循环，相当于将两个子序列合并后重新进行了一次排序并将排序结果记录在了临时数组temp[k]中。while走完后k的值等于数组的长度，i的值此时大于mid，j的值大于right
        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            }
            else {
                temp[k++] = arr[j++];
            }
        }
        
        while(i <= mid) {
            temp[k++] = arr[i++];
        }
        
        while(j <= right) {
            temp[k++] = arr[j++];
        }
        
        //将有序的临时数组temp[k]一个一个赋值到原数组arr[]中
        for(int p=0; p<temp.length; p++) {
            arr[left + p] = temp[p];
        }
        
    }
}

8.线性排序之计数排序

8.1计数排序实现思路

前面基于比较的排序的时间复杂度下限是O(nlogn)，但接下来要谈的计数排序的时间复杂度却只有O(n)。确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。

其基本思想是：用待排序的数作为计数数组的下标，统计每个数字的个数，然后依次输出即可得到有序序列。

8.2计数排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class CountSort {
    
    public static void countSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        
        //取出数组中数值最大的数
        int max = max(arr);
        
        int[] count = new int[max+1];
        
        //用0填充count数组中的每一个数
        Arrays.fill(count, 0);
        
        for(int i=0; i<arr.length; i++) {
            count[arr[i]] ++;
        }
        
        int k = 0;
        for(int i=0; i<=max; i++) {
            for(int j=0; j<count[i]; j++) {
                arr[k++] = i;
            }
        }
        
    }
    
    public static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int ele : arr) {
            if(ele > max)
                max = ele;
        }
        
        return max;
    }

}

9.线性排序之桶排序

9.1桶排序实现思路

设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。bindex=f(key) 其中，bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1<k2，那么f(k1)<=f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然，映射函数的确定与数据本身的特点有很大的关系。

举个栗子:

假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如图所示。只要顺序输出每个B[i]中的数据就可以得到有序序列了。

桶排序分析：

桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，希尔排序中的子序列，归并排序中的子问题，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。　

对N个关键字进行桶排序的时间复杂度分为两个部分：

  • (1)循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。

  • (2)利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为 ∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。

很显然，第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此，我们需要尽量做到下面两点：

  • (1)映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。

  • (2)尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

总结:桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。

9.2桶排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class BucketSort {
    
    public static void bucketSort(int[] arr) {
        if(arr == null && arr.length == 0)
            return ;
        
        int bucketNums = 10; //这里默认为10，规定待排数[0,100)
        List<List<Integer>> buckets = new ArrayList<List<Integer>>(); //桶的索引
        
        for(int i=0; i<10; i++) {
            buckets.add(new LinkedList<Integer>()); //用链表比较合适
        }
        
        //划分桶
        for(int i=0; i<arr.length; i++) {
            buckets.get(f(arr[i])).add(arr[i]);
        }
        
        //对每个桶进行排序
        for(int i=0; i<buckets.size(); i++) {
            if(!buckets.get(i).isEmpty()) {
                Collections.sort(buckets.get(i)); //对每个桶进行快排
            }
        }
        
        //还原排好序的数组
        int k = 0;
        for(List<Integer> bucket : buckets) {
            for(int ele : bucket) {
                arr[k++] = ele;
            }
        }
    }
    
    /**
     * 映射函数
     * @param x
     * @return
     */
    public static int f(int x) {
        return x / 10;
    }
}

10.线性排序之基数排序

10.1基数排序实现思路

基数排序又是一种和前面排序方式不同的排序方式，基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面…如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。

举个栗子:


10.2基数排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public class RadixSort {
    
    public static void radixSort(int[] arr) {
        if(arr == null && arr.length == 0)
            return ;
        
        int maxBit = getMaxBit(arr);
        
        
        for(int i=1; i<=maxBit; i++) {
            
            List<List<Integer>> buf = distribute(arr, i); //分配
            collecte(arr, buf); //收集
        }
        
    }
    
    /**
     * 分配
     * @param arr 待分配数组
     * @param iBit 要分配第几位
     * @return
     */
    public static List<List<Integer>> distribute(int[] arr, int iBit) {
        List<List<Integer>> buf = new ArrayList<List<Integer>>();
        for(int j=0; j<10; j++) {
            buf.add(new LinkedList<Integer>());
        }
        for(int i=0; i<arr.length; i++) {
            buf.get(getNBit(arr[i], iBit)).add(arr[i]);
        }
        return buf;
    }
    
    /**
     * 收集
     * @param arr 把分配的数据收集到arr中
     * @param buf 
     */
    public static void collecte(int[] arr, List<List<Integer>> buf) {
        int k = 0;
        for(List<Integer> bucket : buf) {
            for(int ele : bucket) {
                arr[k++] = ele;
            }
        }
        
        
    }
    
    /**
     * 获取最大位数
     * @param x
     * @return
     */
    public static int getMaxBit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int ele : arr) {
            int len = (ele+"").length();
            if(len > max)
                max = len;
        }
        return max;
    }
    
    /**
     * 获取x的第n位，如果没有则为0.
     * @param x
     * @param n
     * @return
     */
    public static int getNBit(int x, int n) {
        
        String sx = x + "";
        if(sx.length() < n)
            return 0;
        else
            return sx.charAt(sx.length()-n) - '0';
    }

}

总结

这10个算法，我完全消化了的有7个，剩下3个如堆排序、桶排序、基数排序，它们的实现思路我是学明白了，但实现代码我想我还需要点时间消化…这里说下看懂实现代码的一个笨方法，就是随便列举一个要排序的序列，然后代入到代码中进行阅读，虽然费时但是这样看代码就简单多了(来自一个编程新手的笨方法…勿喷)。算法这种，关键要领悟它的思想，思想掌握好以后，再去用代码实现它就不难了。

参考:

2018.3.19更

欢迎加入我的Java交流1群:659957958。

2018.4.21更:如果群1已满或者无法加入，请加Java学习交流2群：305335626 。

联系

If you have some questions after you see this article,you can tell your doubts in the comments area or you can find some info by clicking these links.

记得扫一扫领一下红包再走哦