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

前言:

  前面所讲的排序算法基本都是需要进行两个数依次比较,这种两个数依次比较的算法不依赖于数组重元素的特性并且有下界Ω(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数据结构与算法-在M个数中找K个最小的数

比如输入10,-9,0,100,90,1,4,-9;找到最小的3个数为:-9,-9,0

661
来自专栏Crossin的编程教室

【Python 第73课】reduce 函数

上次说了 Python 中一个比较有意思的内置函数 map,今天再来介绍另一个类似的函数:reduce map 可以看作是把一个序列根据某种规则,映射到另一个序...

2656
来自专栏Java技术栈

涨姿势,图文带你了解 8 大排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

855
来自专栏PPV课数据科学社区

数据结构常见的八大排序算法

前言 八大排序,三大查找是《数据结构》当中非常基础的知识点,在这里为了复习顺带总结了一下常见的八种排序算法。 常见的八大排序算法,他们之间关系如下: 他们的性能...

46211
来自专栏小白客

每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单...

2694
来自专栏用户2442861的专栏

桶排序

http://blog.csdn.net/houapple/article/details/6480100

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

数组

1、 一维数组的定义和使用 通过对前面知识的学习,我们已经知道如何定义和使用一个一个的各种变量,但总有不够用的时候。举个例子,我要记录一个班32个同学C语...

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

数据结构 链表改进

主要介绍循环链表和双向循环链表 循环链表 双向循环链表 2-1 对于一非空的循环单链表,h和p分别指向链表的头、尾结点,则有() ? 循环单链表判空: 设头结点...

2347
来自专栏owent

C/C++语言常用排序算法

资料由互联网收集整理,供新手参考学习 这里又生动点的演示:http://www.cnblogs.com/wangfupeng1988/archive/2011...

901
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

642

扫描关注云+社区