时间复杂度为O(N)的常用排序算法总结与Java实现

时间:2021-11-07 17:18:48

时间复杂度为O(N)的排序算法主要有三种——桶排序、计数排序与基数排序,后两者是基于桶排序的思想

1.桶排序

·基本思想

    给定一个数组arr,数组内都是整数,整数都是处于0到9之间的。于是可以定义一个大小为10的数组b(这个大小通过极值差+1可以尽量的减少大小),初始值为0,表示10个桶。遍历待排序数组arr,将arr对应的值放在b中对应的位置(即b[arr[i]]++),arr中的3使b[3]+1,如果arr中有两个3则b[3]的值成为2;

    然后遍历b这个数组,即是遍历桶,将桶中数据“倒”出来,如果b[i]的值为2,则输出两次,如此就完成了整个桶排序。

·代码实现
public void bucketSort(int [] arr) {
    int max = arr[0],min = arr[0];
	//找到元素的极值差+1作为计数数组大小
        for(int i:arr){
            if(i>max){
                max=i;
            }
            if(i<min){
                min=i;
            }
        }
        int n=max-min+1;
	int[] b = new int[n];
	for(int i = 0 ; i < arr.length ; i ++) {
	    //装入桶
	    b[arr[i]]++;
	}
	for(int i = 0 ; i < b.length ; i ++) {
	    //b[i]是多大,则输出几次
	    while(b[i]!=0) {
	        //按次数顺序输出
		System.out.println(i);
		b[i]--;
	}
    }
}
·性能分析
    桶排序号称最快最简单的算法,排序过程中只进行了一次遍历,因此时间复杂度就是O(N),但是在排序的过程中申请了一个额外的数组(假设大小是M),额外空进复杂度就是O(M),偶尔也使用链表来完成重复数据的存储,而不采取计数的方式,一般来说,认为桶排序是稳定的。

2.计数排序

·基本思想
    先明确一个概念:一个有序序列中,元素k的秩,等于这个序列中,小于等于元素k的的元素个数。

    计数排序基于桶排序的思想,假设待排序数组arr,先找出取值的范围(即已经限定的范围或者序列中max-min+1),依据这个范围定义桶的大小,装入桶的过程与桶排序相同,都是对序列中的元素进行计数;然后每个桶的计数=前一个桶的计数+自身桶的计数,这样下来,每一个桶的计数就等于桶中元素的秩,于是可以有,桶中元素的大小b[arr[i]]即表示arr[i]排序之后所在位置的下标。这样同时也可以处理相同元素的问题,因为所有的相同元素与不同元素都进行了计数,只需要输出排序后的数组,就可以保持原序列的元素不变。

代码实现
public int[] countSort(int[] arr) {
    int max = arr[0],min = arr[0];
    //找到元素的极值差+1作为计数数组大小
    for(int i:arr){
        if(i>max){
        max=i;
        }
        if(i<min){
        min=i;
        }
    }
    int n=max-min+1;
    int[] b = new int[n];
    for(int i = 0 ; i < arr.length ; i ++) {
        //arr[i]对应的元素所在下标计数+1
        b[arr[i]-min]++;
    }
    for(int i = 1 ; i < b.length ; i ++) {
        //记录不大于当前元素的个数
        b[i] = b[i] + b[i-1];
    }
    int [] c = new int[arr.length];
    for(int i = arr.length-1 ; i >= 0 ; i --) {
        //计数数组-1就是当前元素对应的秩,用原数组的当前值赋值
        //b[arr[i]-min]表示arr[i]这个元素的秩,-1则可以表示所在的下标
        c[--b[arr[i]-min]]=arr[i];
    }
    return c;
}
性能分析

    如果计数数组范围本身就很小,只需要进行三次遍历就可以排序完毕;如果想减少计数数组的大小,则还需要一次遍历来找到极值差+1;计数排序不是基于比较的方式来排序的,辅助数组的大小为M的话,时间复杂度则为O(M+N),额外空间复杂度就是O(M+N),有一种理想的状态,就是M<<N的时候,此时,数据多而不散,集中在一个小范围内,此时,时间复杂度就是O(N)。同理,计数排序也是稳定的排序算法。

3.基数排序

·基本思想

    假设待排序数组arr,我们可以知道数组的最大数的位数maxDigit,准备一个大小为10的数组buckets,表示0~9位,接下来,在循环maxDigit次中,分别把所有的数字按照

·代码实现
/**
* 
* @param arr 待排序数组
* @param index 以10为初值,每次乘以10
* @param maxDigit 最长的数字的位数
*/
public void radixSort(int[] arr,int index,int maxDigit) {
    //使用temp数组存储arr数组的所有值
    int[] temp = new int[arr.length];
    //定义10个桶
    int[] buckets = new int [index];
    //用于计算当前位数的值
    int rate = 1;
    for(int i = 0; i < maxDigit ; i ++) {
        //每次排序需要重置桶
        Arrays.fill(buckets, 0);
        //将arr复制到temp
        System.arraycopy(arr, 0, temp, 0, arr.length);
        for(int j = 0 ; j < arr.length ; j ++) {
            buckets[(temp[j]/rate)%index]++;
        }
        //计数
        for(int j = 1 ; j < index ; j ++) {
            buckets[j] = buckets[j] + buckets[j-1];
        }
        for(int j = arr.length-1 ; j >= 0 ; j --) {
            arr[--buckets[(temp[j]/rate)%index]] = temp[j];
        }
        rate *= index;
    }
}
性能分析

    基数排序不是基于比较的方式来排序的,基数排序的时间复杂度一般认为是O(N),额外空间复杂度还需要定义一个辅助数组,辅助数组的大小为M的话,额外空间复杂度是O(M+N)。基数排序也是稳定的排序算法。