依赖数组特性的几种非比较排序算法

前言:

  前面所讲的排序算法基本都是需要进行两个数依次比较,这种两个数依次比较的算法不依赖于数组重元素的特性并且有下界Ω(nlogn)。换句话说就是使用比较排序算法最快的时间消耗没法小于这个界。那么是不是我们永远没法跨越这个梗呢?答案当然不是,当数组中的元素有一定的特点的时候,我们就可以利用这个特定,以实现排序算法的时间消耗与n呈线性的关系。

特性一:数组中所有元素正负性一致并且他们绝对值都小于某一个数。

  当数组中所有元素都为正数或者都为负数的时候其实比较的算法是一致。这里我们假设所有元素都是非负。关于这个特性我们的思路灵感可能来自于统计一段文字中每个字母出现的次数。我们可以假设数组中所有元素都小于k。那么我们可以建立一个长度为k的数组,通过遍历要排序的数组,我们可以知道元数组中特定值的元素的个数。更进一步的,完成第一步之后我们可以知道原数组中小于等于某一元素的个数。既然我们知道了小于该元素的个数,就很简单的能得到该元素应该在数组中的位置。  这种排序算法叫做计数排序(Counting Sort)。源代码如下:

 1 public static void main(String[] args) {
 2         int[] arr = { 1, 12, 11, 4, 5, 7, 3, 1, 23, 56, 34, 76, 25, 76 };
 3         countingSort(arr, 80);
 4     }
 5 
 6     private static void countingSort(int[] arr, int upBound/** 数组中元素的上界 */
 7     ) {
 8         // 新建一个数组,该数组用来存储arr中所有值出现的次数(如果不给数组中的元素赋值,默认每个值都为0)
 9         int[] valueCountArr = new int[upBound];
10 
11         // 计算arr中对应值出现的次数
12         for (int i = 0; i < arr.length; i++) {
13             valueCountArr[arr[i]] = valueCountArr[arr[i]] + 1;
14         }
15 
16         // 使valueCountArr[i]中存储的为原数组中小于等于i的元素的个数
17         for (int i = 1; i < upBound; i++) {
18             valueCountArr[i] += valueCountArr[i - 1];
19         }
20 
21         // 新建一个数组用来存放排序完成之后的值
22         int[] sortedArr = new int[arr.length];
23         for (int i = 0; i < arr.length; i++) {
24             sortedArr[valueCountArr[arr[i]] - 1] = arr[i]; // 如果小于等于arr[i]的值的个数为j,那么arr[i]在排序好的数组中的位置应该在arr[j-1]
25             valueCountArr[arr[i]] = valueCountArr[arr[i]] - 1; // 此时小于等于特定值的计数应该减一(如果存在同样大小的元素,需要把计数减一,不然两个值的位置会互相覆盖)
26         }
27 
28         System.out.println(Arrays.toString(sortedArr));
29     }

特性二:数组中的元素的位数都一样且数组中元素的正负性一致。

  同特性一,我们假设所有元素都是非负的。这一特性可供我们利用的一点就是从个位数开始分别比较每一位的值。假设每一位的值有上界k(其实k最大为10)。我们可以假设共有n个元素,每个元素都有d位,每位数字都小于k。我们其实可以针对每一位都进行计数排序。这样每一次计数排序的耗时为:θ(n+k),共有d位,所以总共的耗时为:θ(d(n+k))。

因为d、k都是一个常量。所以这其实也是关于n的线性排序。这种排序算法叫做基数排序(RadixSort)。源代码如下:

 1 public static void main(String[] args) {
 2         int[] arr = { 123, 111, 213, 110, 990, 212, 345, 541, 246, 798, 555 };
 3         radixSort(arr, 3);
 4     }
 5 
 6     private static void radixSort(int[] arr, int digit/** 每一个数字的位数 */
 7     ) {
 8         int[] eachDigitArr = new int[arr.length];
 9         for (int i = 1; i <= digit; i++) {
10             for (int j = 0; j < arr.length; j++) {
11                 eachDigitArr[j] = arr[j] % (int) Math.pow(10, i)
12                         / (int) Math.pow(10, i - 1);
13             }
14             sortDigit(arr, eachDigitArr);
15         }
16         System.out.println(Arrays.toString(arr));
17     }
18 
19     private static void sortDigit(int[] arr, int[] eachDigitArr) {
20 
21         // 因为每一位数都小于10,所以可以设置上界为10的计数排序
22         int[] valueCountArr = new int[10];
23         int[] indexArr = new int[arr.length]; // 还需要定义一个数组用来存放排序之后每一个位置对应排序之前的数组中元素的下标
24         for (int i = 0; i < arr.length; i++) {
25             indexArr[i] = i;
26         }
27 
28         for (int i = 0; i < eachDigitArr.length; i++) {
29             valueCountArr[eachDigitArr[i]] += 1;
30         }
31 
32         for (int i = 1; i < 10; i++) {
33             valueCountArr[i] = valueCountArr[i] + valueCountArr[i - 1];
34         }
35 
36         // 在计数排序的过程更新排序后对应位置的元素在原数组中的下标(此时应该从数组末尾进行遍历,以保证前面的排序对这次排序的限定性)
37         for (int i = eachDigitArr.length - 1; i >= 0; i--) {
38             indexArr[valueCountArr[eachDigitArr[i]] - 1] = i;
39             valueCountArr[eachDigitArr[i]] -= 1;
40         }
41 
42         int[] resultArr = new int[arr.length];
43         for (int i = 0; i < arr.length; i++) {
44             resultArr[i] = arr[indexArr[i]];
45         }
46 
47         System.arraycopy(resultArr, 0, arr, 0, arr.length);
48     }

特性三:数组中的元素均匀的分布在一定的范围内。

这个特性排序算法的灵感来自于HashCode的生成规则以及HashMap的存储结构。该算法的原理大致是:维护一个数组,数组中的每一个元素相当于一个列表。每个列表存储了拥有相同特性的元素。假设被维护的数组为arr,arr[i]和arr[j]为维护数组中的两个元素。那么对于任意i、j,如果i<j。那么arr[i]中的所有元素都小于arr[j]中的所有元素。这样其实对于任意元素,如果该元素属于arr[i],那么其实只要用插入排序算法插入arr[i]中的元素列表即可。最后将维护的数组每一个下标元素中的元素列表拼接起来即为最终结果。这种算法称作桶排序(BucketSort)。源代码如下:

 1 public static void main(String[] args) {
 2         int[] arr = { 1, 12, 11, 4, 5, 7, 3, 1, 23, 56, 34, 76, 25, 76 };
 3         bucketSort(arr);
 4     }
 5 
 6     private static void bucketSort(int[] arr) {
 7         // 观察数组可以认为数组均匀的分布在(0 , 100)之间,我们可以将数组中的元素按照除以10所得的余数不同来进行分组,这样就一共有10组。
 8         // 建立一个二维数组来进行相同特性的元素划分维护
 9         int[][] bucketArr = new int[10][10];
10         for (int i = 0; i < 10; i++) {
11             for (int j = 0; j < 10; j++) {
12                 bucketArr[i][j] = 100;
13             }
14         }
15 
16         for (int i = 0; i < 10; i++) {
17             insert2Arr(bucketArr[arr[i] / 10], arr[i]);
18         }
19 
20         int k = 0;
21         for (int i = 0; i < 10; i++) {
22             for (int j = 0; j < bucketArr[i].length; j++) {
23                 if (bucketArr[i][j] < 100) {
24                     arr[k++] = bucketArr[i][j];
25                 }else {
26                     continue;
27                 }
28             }
29         }
30         System.out.println(Arrays.toString(arr));
31     }
32 
33     private static void insert2Arr(int[] arr, int value) {
34         arr[arr.length - 1] = value;
35         for (int i = arr.length - 1; i > 0; i--) {
36             if (arr[i] < arr[i - 1]) {
37                 swap(arr, i, i - 1);
38             } else {
39                 break;
40             }
41         }
42     }
43 
44     private static void swap(int[] arr, int index1, int index2) {
45         int temp = arr[index1];
46         arr[index1] = arr[index2];
47         arr[index2] = temp;
48     }

   可以看到该算法最后合并的耗时为:θ(n)。中间针对每一个桶进行排序我们可以假设每一次进行桶的某一个列表进行插入排序的时候列表的元素有ni 个。那么有公式:

T(n) = θ(n) + ΣΟ(ni )2  其中i的取值为1到n-1。第二项的取值不好计算,我们可以定义指示器变量 Xij = I(表示a[j]落在桶i中)。其中i=0, 1, 2, ... n-1;j=0, 1, 2... n-1(桶的长度最多和数组元素个数一直)。 所以ni = Σ(Xij ) (其中j为0, 1, 2, ... , n-1)。对刚刚的时间消耗公式同时取期望得:

E[T(n)] = E[θ(n) + ΣΟ(ni )2] = θ(n) + ΣΟ(E[ni ]2)。 所以有 E[ni ]2 = E[ Σ(Xij )2] 。后面是一个多项式乘以多项式:E[ Σ(Xij )2]  = E[ ΣXij2 + ΣXijΣXik] = ΣE[Xij2] + ΣΣE[XijXik](其中j和k的取值都是0, 1, 2, .. n-1且k!=j)。指示器随机变量Xij为1的概率为1/n,其他情况下该指示器变量的值为0。易得: E[Xij2] = 1*1/n + 0*(1- 1/n) = 1/n。

又当k!=j的时候Xij、Xik 是相互独立的。所以有E[XijXik] = 1/n * 1/n = 1/n2。进而得到:  E[ni ]2  =  Σ(1/n) + ΣΣ(1/n2) = 2 - 1/n。对消耗的时间去掉取期望之后得到:

T(n) = θ(n) + n*Ο(2- 1/n) = θ(n)。其实即使数组中的元素不是均匀分布,桶排列也可以得到关于n的线性时间消耗。

总结

  以上的三种排序突破了数组比较排序的下界。但是他们依赖于数组的特性,而且暂用的空间也比堆排序和数组排序这种原数组内部进行替换的排序大。在实际应用中应该根据需要进行特定的算法选择。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记...

3307
来自专栏mathor

十大经典排序算法(动图演示)

不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 ...

1K3
来自专栏用户画像

7.6.1 内部排序算法的比较

1、简单选择排序、直接插入排序和冒泡排序的平均情况下的时间复杂度都为O(n^2),并且实现过程比较简单,但直接插入排序和冒泡排序在最好的情况下时间复杂度可以达到...

632
来自专栏大闲人柴毛毛

动态规划法(三)——最长公共子序列

问题描述 给定两个序列,求出它们的最长公共子序列。 如:序列X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a},则X和Y的最长公共子...

3314
来自专栏Petrichor的专栏

tensorflow编程: Constants, Sequences, and Random Values

  注意: start 和 stop 参数都必须是 浮点型;     取值范围也包括了 stop; tf.lin_space 等同于 tf.lins...

742
来自专栏wym

字符串--Kmp详解+代码

        给定文本串text和模式串pattern,要求从文本串中找到模式串第一次出现的位置。

921
来自专栏机器学习从入门到成神

2014百度研发真题及其解析-求比指定数大且最小的“不重复数”

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1192
来自专栏mathor

小和问题

 在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组的小和。

1964
来自专栏SeanCheney的专栏

《Pandas Cookbook》第03章 数据分析入门1. 规划数据分析路线2. 改变数据类型,降低内存消耗3. 从最大中选择最小4. 通过排序选取每组的最大值5. 用sort_values复现nl

1272
来自专栏Brian

数据分析利器-NumPy

---- 概述 NumPy类库是Python的一种开源的数值计算扩展。这种工具可用来存储和处理大型矩阵,比Python自身的嵌套列表(nested list s...

3398

扫码关注云+社区