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

前言:

  前面所讲的排序算法基本都是需要进行两个数依次比较,这种两个数依次比较的算法不依赖于数组重元素的特性并且有下界Ω(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 条评论
登录 后参与评论

相关文章

来自专栏python读书笔记

《python算法教程》Day3 - 递归递归简介代码示例

这是《python算法教程》的第3篇读书笔记。由于之前看书的效率太低了,所以拖了一个多星期才写第三篇读书笔记。这次主要简单总结一下递归(recursion)。 ...

2528
来自专栏Java3y

十道算法题[二]

前言 清明不小心就拖了两天没更了~~ 这是十道算法题的第二篇了~上一篇回顾:十道简单算法题 最近在回顾以前使用C写过的数据结构和算法的东西,发现自己的算法和数据...

3049
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

34711
来自专栏数据结构与算法

1807. [NOIP2014]寻找道路P2296 寻找道路

题目描述 在有向图G 中,每条边的长度均为1 ,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件: 1 .路径上的所有点的出边所指向的点...

2846
来自专栏TensorFlow从0到N

讨厌算法的程序员 7 - 归并排序的时间复杂度分析

? 递归树 上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度...

2346
来自专栏小樱的经验随笔

Gym 100952C&&2015 HIAST Collegiate Programming Contest C. Palindrome Again !!【字符串,模拟】

C. Palindrome Again !! time limit per test:1 second memory limit per test:64 meg...

2493
来自专栏糊一笑

非比较排序算法总结与实现

之前一篇文章介绍了几种常用的比较排序算法,下面介绍的是几种非比较排序算法。 非比较排序算法内部引用的都是计数排序,当然你也可以将计数排序换为其他的比较排序算法。...

2958
来自专栏ml

HDUOJ --2566

统计硬币 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

2557
来自专栏Java Web

最长公共子序列问题

问题描述: 求两个字符序列的公共最长子序列。 ---- 最长公共子串 在回到子序列问题之前,先来了解一下子串的问题。 例如,HISH和FISH两个字符序列的公...

3024
来自专栏C语言及其他语言

【每日一题】问题1075: 台球碰撞(此次问题较难)

题目描述 在平面直角坐标系下,台球桌是一个左下角在(0,0),右上角在(L,W)的矩形。有一个球心在(x,y),半径为R的圆形母球放在台球桌上(整个球都在台球...

2585

扫码关注云+社区