常用排序算法全解析（Java实现）

桃扇骨 2022-05-22 11:55 154阅读 0赞

这篇博客是我之前做的一些零散笔记的重新整理，有些想不起来了，有新的内容我会更新进来。

为简单起见，假设我们讨论目标只包含整数，当然我们的程序也允许更一般的对象（实现Comparable接口中的compareTo方法）。我们还假设整个排序工作能够在主存中完成，不能在主存中完成的排序叫作外部排序，我们单独讨论。

接下来我们会分析一些排序算法的实现原理，时间复杂度，针对特定待排序目标下性能优劣以及改进的空间，设计的排序算法有：

插入排序

冒泡排序

简单选择排序

希尔排序

快速排序

归并排序

堆排序

桶排序

基数排序

————————————————————————————————————————————————————

最简单的排序算法之一是插入排序。插入排序由N-1趟排序组成。对于p=1到N-1趟，插入排序保证从位置0到位置p上的元素为已排序状态。说白了就是第二个数插入到第一个数，保证这两个数有序，第三个数插入到前两个数中去，保证这三个数有序，以此类推。

插入排序的实现例程

//插入排序
    public static void insertionSort(int[] nums){
        int j;
        for(int i=1;i<nums.length;i++){
            int tmp = nums[i];
            for(j=i;j>0&&tmp<nums[j-1];j--){
                nums[j] = nums[j-1];
            }
            nums[j] = tmp;
        }
    }

由于嵌套循环的每一个都花费N次迭代，因此插入排序为O(N平方），而且这个界是精确的，当输入的序列是反序的时候可以达到该界。另外如果输入数据已预先排序，那么运行时间为O(N)，此时内存循环总是监测判定不成立而终止。事实上，如果输入序列几乎被排序，那么插入排序将运行得很快。插入排序的平均时间复杂度为O(N平方)。

二分查找插入排序（待补充）

————————————————————————————————————————————————————

冒泡排序就是通过比较相邻的两个数，将大的放后边，小的放左边（增序的话是这样），这样一轮遍历下来，最大的数就会出现在序列的最后，如此重复不停的将较大的数放到最后，实现排序。

冒泡排序的实现例程

public static void bubbleSort(int[] nums){
        for(int i=0;i<nums.length;i++){
            for(int j=1;j<nums.length-i;j++){
                if(nums[j]<nums[j-1]){
                    int tmp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = tmp;
                }
            }
        }
    }

冒泡排序通过交换相邻元素，其平均时间复杂度为O(N平方)，最差也是O(N平方)

如果输入的序列有序，本来走完一趟便可完成排序，这里却需要重复的判断，这里还有优化的空间。对于本生有序或者部分有序的序列，我们可以在算法中加一个区间来记录从哪里到哪里没有发生交换。进而只在剩下无序的空间中排序。

基本有序情况下冒泡排序优化（待补充）

————————————————————————————————————————————————————

选择排序就是每一趟从待排序的序列中选出最小的，依次摆放最小的形成排序序列

简单选择排序的实现例程

public static void selectionSort(int[] nums){
        for(int i=0;i<nums.length-1;i++){
            int k =i;
            for(int j=k+1;j<nums.length;j++){
                if(nums[j]<nums[k]){
                    k = j;
                }
            }
            if(i != k){
                int tmp = nums[i];
                nums[i] = nums[k];
                nums[k] = tmp;
            }
        }
    }

简单选择排序的时间复杂度为O(N平方)

————————————————————————————————————————————————————

希尔排序的名称来自他的发明者Donald Shell，它通过比较相距一定间隔的元素的来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。有间隔的增长序列有多种选择，性能也会不一样，Shell建议的是N/2，其例程如下

//希尔排序
    public static void shellSort(int[] nums){
        int j;
        for(int gap = nums.length/2;gap>0;gap/=2)
            for(int i = gap;i<nums.length;i++){
                int tmp = nums[i];
                for(j = i;j>=gap&&tmp<nums[j-gap];j-=gap){
                    nums[j] = nums[j-gap];
                }
                nums[j] = tmp;
            }
    }

使用希尔增量时希尔排序的最坏情形运行时间为O(N平方)，使用Hibbard增量的希尔排序的最坏情形运行时间为O(N的1.5次方)

————————————————————————————————————————————————————

快速排序，顾名思义就是实践中的一种很快的排序算法，在C++或对Java基本类型的排序中特别有用。该算法之所以特别快，主要是由于非常精炼和高度优化的内部循环。快速排序跟后面说到的归并排序都是一种分治的递归算法。经典快速排序的思想也很简单，选待排序列中的一个数，用这个数将序列划分为两部分，一个比它小一个比它大，这样就形成了左中右三节，然后递归重复这个过程。

快速排序的实现例程

//快速排序
    public static void fastSort(List<Integer> nums){
        if(nums.size() > 1){
            List<Integer> smaller = new ArrayList<>();
            List<Integer> same = new ArrayList<>();
            List<Integer> larger = new ArrayList<>();
    
            Integer chosenNum = nums.get(nums.size() / 2);
            for(Integer i : nums){
                if(i < chosenNum){
                    smaller.add(i);
                }else if(i > chosenNum){
                    larger.add(i);
                }else{
                    same.add(i);
                }
            }
            fastSort(smaller);//递归调用
            fastSort(larger);//递归调用
    
            nums.clear();
            nums.addAll(smaller);
            nums.addAll(same);
            nums.addAll(larger);
        }
    }

它的平均运行时间是O(NlogN)，最坏情形性能为O(N平方)。

快排的其他写法（待补充）

————————————————————————————————————————————————————

归并排序，这个算法中的基本操作是合并两个已排序的表。因为这两个表是已排序的，所以若将输出放到第三个表中，一趟遍历几个完成合并排序。归并排序也是一种分治思想的体现。

归并排序的实现例程

//归并排序
        private static void mergeSort(int[] nums,int[] tmp,int left,int right){
            if(left<right){
                int center = (left+right)/2;
                mergeSort(nums,tmp,left,center);
                mergeSort(nums,tmp,center+1,right);
                merge(nums,tmp,left,center+1,right);
            }
        }
        private static void merge(int[] nums,int[] tmp,int leftPos, int rightPos, int rightEnd){
            int leftEnd = rightPos-1;
            int tmpPos = leftPos;
            int numElements = rightEnd - leftPos + 1;
        
            while(leftPos<=leftEnd&&rightPos<=rightEnd){
                if(nums[leftPos]<nums[rightPos])
                    tmp[tmpPos++]=nums[leftPos++];
                else 
                    tmp[tmpPos++]=nums[rightPos++];
            }
            while(leftPos<=leftEnd)
                tmp[tmpPos++]=nums[leftPos++];
            
            while(rightPos<=rightEnd)
                tmp[tmpPos++]=nums[rightPos++];
        
            for(int i = 0;i<numElements;i++,rightEnd--)
                nums[rightEnd]=tmp[rightEnd];
        }
        public static void mergeSort(int[] nums){
            int[] tmp = new int[nums.length];
            mergeSort(nums,tmp,0,nums.length-1);
        }

归并排序最坏情形的运行时间是O(NlogN)。

————————————————————————————————————————————————————

堆排序是优先队列数据结构的使用，建立N个元素的二叉堆花费O(N)时间，而执行deleteMin操作只花费O(logN)时间，因此总的运行时间是O(NlogN)。

堆排序的实现例程

//堆排序
    private static int leftChild(int i){
        return 2 * i + 1;
    }
    private static void percDown(int [] a ,int i, int n){
        int child;
        int tmp;
        for(tmp = a[i];leftChild(i)<n;i =child){
            child = leftChild(i);
            if(child != n-1 && a[child] < a[child+1]) child++;
            if(tmp < a[child]) a[i] = a[child];
            else break;
        }
        a[i] = tmp;
    }
    private static void swapReferences(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    public static void heapSort(int[] a){
        for(int i = a.length/2 -1;i >= 0;i--) percDown(a, i, a.length);
        for(int i = a.length-1;i>0;i--){
            swapReferences(a, 0 ,i);//将堆顶元素与末尾元素进行交换
            percDown(a, 0, i);
        }
    }

————————————————————————————————————————————————————

桶排序和基数排序都是线性时间的排序，不过是在某些特殊的情况下才能实现。对于桶排序，要使桶排序能够正常工作，输入数据必须仅由小于M的正整数组成。这时我们可以使用一个大小为M的称为count的数组，初试化为全0。于是，count有M个单元（称为桶），当读入一个数i时，count\[i\]增加1。读入所有的输入数据后，扫描count数组，打印出排序后的表。

//桶排序
    public static void bucketSort(int[] nums, int m){
        int[] sorted = new int[m];
        for(int i=0;i<m;i++){
            sorted[i]=0;
        }
        for(int i : nums){
            sorted[i]++;
        }
        int j = 0;
        for(int i = 0;i<m;i++){
            while(sorted[i]>0){
                nums[j] = sorted[i];
                j++;
                sorted[i]--;
            }
        }
    }

基数排序的原理是将数值按照位数切分为不同数字，然后对每位数分别进行比较，从而达到排序的目的。比如可以实现字符串的排序。