精华内容
下载资源
问答
  • 关于计数排序算法 当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。 由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待...
  • 主要介绍了Python实现的计数排序算法,简单描述了计数排序的算法原理并结合具体实例形式分析了Python计数排序的相关实现与使用技巧,需要的朋友可以参考下
  • 计数排序(Counting sort)是一种非基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中以达到排序的效果 2.算法原理 给定一组取值范围为0到9的无序序列:1、7、4、9、0、5、2、4、7、...
    十大经典排序算法

    一、什么是计数排序

    1.概念

    计数排序(Counting sort)是一种非基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中以达到排序的效果

    2.算法原理

    给定一组取值范围为0到9的无序序列:1、7、4、9、0、5、2、4、7、3、4,建立一个长度为10的计数数组,值初始化为0
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-au7gjQEg-1594191848834)(./计数1.png)]
    遍历无序序列,将每个序列元素值对应的计数数组下标的元素加1

    如:第一个序列元素为1,则计数数组中下标为1的元素加1
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rAv76jgZ-1594191848836)(./计数2.png)]
    第二个序列元素为7,计数数组中下标为7的元素加1
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0iwSn624-1594191848838)(./计数3.png)]
    继续遍历序列,当序列遍历完毕,计数数组的最终状态如下:
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nQ2rxszh-1594191848839)(./计数4.png)]
    遍历计数数组,输出计数数组下标值,元素的值是多少,就输出几次

    输出结果如下:0、1、2、3、4、4、4、5、7、7、9

    此时,元素已是有序的了

    3.算法实现

    // 计数排序
    function sort(arr) {
        // 得到数列的最大值
        let max = arr[0];
        for (let item of arr) {
            if (item > max) {
                max = item;
            }
        }
    
        // 初始化数组
        let countArr = [];
        for (let i = 0; i <= max; i++) {
            countArr[i] = 0;
        }
    
        // 遍历原始数组,填充计数数组
        for (let item of arr) {
            countArr[item]++;
        }
    
        // 遍历计数数组,得到排序后结果
        let index = 0;
        let sortArr = [];
        for (let i = 0; i <= max; i++) {
            for (let j = 0; j < countArr[i]; j++) {
                sortArr[index++] = i;
            }
        }
    
        return sortArr;
    }
    
    let arr = [1, 7, 4, 9, 0, 5, 2, 4, 7, 3, 4];
    let sortArr = sort(arr);
    console.log(sortArr);
    

    二、算法优化

    在前面的例子中,我们以序列的最大值来确定计数数组长度,假设有一个序列83、80、88、90、88、86,那么我们创建一个长度为91的计数数组,计数数组的0到79位都浪费了

    我们可以创建一个长度为90-80+1=11(最大值-最小值+1)的计数数组,计数数组的偏移量为序列的最小值80
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GEVUqFmx-1594191848842)(./计数5.png)]
    如图:计数数组下标0对应序列80,下标1对应序列81,以此类推

    此外,我们前面的例子中,我们在新建的计数数组中记录序列中每个元素的数量,如果序列有相同的元素,则在输出时,无法保证元素原来的排序,是一种不稳定的排序算法,可通过优化,将其改为稳定排序算法

    以序列83、80、88、90、88、86为例,首先填充计数数组
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SMlp12j3-1594191848844)(./计数6.png)]
    将计数数组从第二个元素开始,每个元素都加上前面所有元素的和,此时,计数数组的值表示的是元素在序列中的排序
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Qz3hEdhK-1594191848845)(./计数7.png)]
    接下来我们创建输出数组,长度与待排序序列一致,从后往前遍历待排序序列

    首先,遍历最后一个元素86,我们在计数数组中找到86对应的值为3,则在输出数组的第3位(下标为2)填入86,计数数组86对应的值减1,既当前的86排序是3,下次遇到86则排序是2
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UITNUESS-1594191848846)(./计数8.png)]
    接着,遍历下一个元素88,在计数数组中找到88对应的值为5,在输出数组的第5位(下标为4)填入88,计数数组88对应的值减1
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-u0hnOM1N-1594191848847)(./计数9.png)]
    然后,遍历下一个元素90,在计数数组中找到90对应的值为6,在输出数组的第6位(下标为5)填入90,计数数组90对应的值减1
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m9jDXrIF-1594191848848)(./计数10.png)]
    继续遍历下一个元素88,在计数数组中找到88对应的值为4,在输出数组的第4位(下标为3)填入88,计数数组88对应的值减1
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cizoT7xO-1594191848849)(./计数11.png)]
    以此类推,将所有元素遍历完,填入输出数组
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gbj2r8pB-1594191848851)(./计数12.png)]
    原序列第3位、第5位均为88,从上面的步骤我们可以看到,在第二步,第5位的88填入输出数组的第5位,在第四步,第3位的88填入输出数组的第4位,没有改变原序列相同元素的顺序

    优化后代码如下:

    // 计数排序优化
    function sort(arr) {
        // 得到数列的最大值、最小值,并计算计数数组长度
        let max = arr[0];
        let min = arr[0];
        for (let item of arr) {
            if (item > max) {
                max = item;
            }
            if (item < min) {
                min = item;
            }
        }
        let length = max - min + 1;
    
        // 初始化计数数组
        let countArr = [];
        for (let i = 0; i < length; i++) {
            countArr[i] = 0;
        }
    
        // 遍历原始数组,填充计数数组
        for (let item of arr) {
            countArr[item - min]++;
        }
    
        // 计数数组形变,后面的元素等于前面的元素之和
        let sum = 0;
        for (let i = 0; i < length; i++) {
            sum += countArr[i];
            countArr[i] = sum;
        }
        console.log(11111111, countArr);
    
        // 倒序遍历计数数组,从计数数组中找到正确位置,输入到输出数组
        let sortArr = [];
        for (let i = arr.length - 1; i >= 0; i--) {
            sortArr[countArr[arr[i] - min] - 1] = arr[i];
            countArr[arr[i] - min]--;
            console.log(arr[i], countArr, sortArr);
        }
    
        return sortArr;
    }
    
    let arr = [83, 80, 88, 90, 88, 86];
    let sortArr = sort(arr);
    console.log(sortArr);
    

    三、计数排序算法特点

    1.时间复杂度

    计数排序算法遍历了3次原始数组,一次计数数组,所以算法的时间复杂度是O(N+M)

    2.空间复杂度

    计数排序算法排序过程中新建了一个计数数组和一个输出数组,所以算法的空间复杂度是O(N+M)

    3.稳定性

    优化后的计数排序算法在排序过程中,相同元素的前后顺序不会发生改变,是一种稳定排序算法

    4.局限性

    • 当待排序序列的最大值和最小值差值特别大时,不适合使用计数排序算法
    • 当待排序序列的值不是整数时,不适合使用计数排序算法
    展开全文
  • 计数排序算法

    2021-06-06 22:45:51
      计数排序(Counting Sort)是一个非基于比较的排序算法,该算法的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。...

      计数排序(Counting Sort)是一个非基于比较的排序算法,该算法的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。它的优势在于在对一定范围内的整数排序时,它的复杂度为 O ( n + k ) Ο(n+k) O(n+k)(其中k是整数的范围),快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法,而且当 O ( k ) > O ( n ∗ l o g ( n ) ) O(k)>O(n*log(n)) O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是 O ( n ∗ l o g ( n ) ) O(n*log(n)) O(nlog(n)),如归并排序、堆排序)。

      算法的步骤如下:
       (1)找出待排序的数组中最大和最小的元素;
       (2)统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
       (3)对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
       (4)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

      计数排序算法的基本思想:把数组元素作为数组的下标,然后用一个临时数组统计该元素出现的次数,例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来,此时汇总起来是数据是有序的。

      例如: 使用计数排序算法将数组 { 2,3,8,7,1,7,3,9,8,2,1,4,2,4,6,9 } 进行升序排序。

    在这里插入图片描述
      实现代码如下所示。

    #include<iostream>
    using namespace std;
    
    void CountingSort(int *arr, int size)
    {
    	int minValue = arr[0];  //通过maxValue和minValue计算出临时数组所需要开辟的空间大小
    	int maxValue = arr[0];
    	int* tmp = 0;
    	int count = 0;
    	for (int i = 0; i < size; i++)  //找出待排序的数组中最大和最小的元素
    	{
    		if (arr[i] < minValue) 
    			minValue = arr[i];
    		if (arr[i] > maxValue)
    			maxValue = arr[i];
    	}
    	int range = maxValue - minValue + 1;  //计算数据的分散空间
    	tmp = (int*)malloc(sizeof(arr[0])*size);  //申请辅助空间
    	if (tmp == NULL)
    		return;
    	memset(tmp, 0, sizeof(int)*range);  //初始化
    
    	for (int i = 0; i < size; i++)  //统计每个元素出现的次数
    		tmp[arr[i] - minValue]++;  //在存储上要在原始数组数值上减去minValue才不会出现越界问题
    
    	for (int i = 0; i < range; i++)  //通过统计tmp[];回收元素
    	{
    		while (tmp[i]--)
    			arr[count++] = i + minValue;  //要将i的值加上minValue才能还原到原始数据
    	}
    	free(tmp);
    }
    
    int main()
    {
    	int a[] = { 2,3,8,7,1,7,3,9,8,2,1,4,2,4,6,9 };
    	int len = (int) sizeof(a) / sizeof(*a);
    
    	cout << "排序前:" << endl;
    	for (int i = 0; i < len; i++)
    	{
    		cout << a[i] << "  ";
    	}
    	cout << endl;
    
    	CountingSort(a, len);
    
    	cout << "排序后:" << endl;
    	for (int i = 0; i < len; i++)
    	{
    		cout << a[i] << "  ";
    	}
    	cout << endl;
    
    	system("pause");
    	return 0;
    }
    

    排序前:
    2 3 8 7 1 7 3 9 8 2 1 4 2 4 6 9
    排序后:
    1 1 2 2 2 3 3 4 4 6 7 7 8 8 9 9

      时间复杂度: O ( n + k ) O(n+k) O(n+k)

      空间复杂度: O ( k ) O(k) O(k)

      稳定性: 由于在排序的过程中,具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序相同。也就是说,对两个相同的数来说,在输人数组中先出现的数,在输出数组中也位于前面。所以计数排序是稳定的排序。

    展开全文
  • 以前看过网上的一篇关于一种号称时间复杂度能达到O(n)的不用比较就可以实现排序的算法——计数排序法,这是自己用C写的一个实现,大家可以参考下,欢迎指证。
  • 通常计数排序算法的实现步骤思路是: 1.找出待排序的数组中最大和最小的元素; 2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项; 3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加); 4....
  • Java实现计数排序算法

    2021-02-23 21:49:42
    计数排序算法 计数排序是一种排序算法,它通过计算数组中每个唯一元素的出现次数来对数组的元素进行排序。将计数存储在辅助数组中,并通过将计数映射为辅助数组的索引来完成排序。 计数排序如何工作? max从...

    计数排序算法

    计数排序是一种排序算法,它通过计算数组中每个唯一元素的出现次数来对数组的元素进行排序。将计数存储在辅助数组中,并通过将计数映射为辅助数组的索引来完成排序。


    计数排序如何工作?

    1. 从给定的数组中找出最大的元素(max)。计算排序步骤

      给定数组

    2. 初始化一个长度max+1为0的所有元素的数组。此数组用于存储数组中元素的数量。计数排序步骤

      计数数组

    3. 将每个元素的计数存储在count数组中它们各自的索引处

      例如:如果元素3的计数为2,则将2存储在元素的第3个位置数数大批。如果数组中不存在元素“ 5”,则在第5个位置存储0。计数排序步骤

      存储的每个元素的计数

    4. 存储计数数组元素的累积和。它有助于将元素放入已排序数组的正确索引中。计数排序步骤

      累计数

    5. 在count数组中找到原始数组的每个元素的索引。这给出了累计计数。将元素放置在计算出的索引处,如下图所示。计算排序步骤

      计数排序

    6. 将每个元素放置在正确位置后,将其数量减少一。

    计数排序算法

    countSort(array,size)
      max <-查找数组中的最大元素
      用全零初始化计数数组
      对于j <-0到大小
        找到每个唯一元素的总数,然后 
        将计数存储在count数组中的第j个索引处
      对于我<-1到最大
        找到累积和并将其存储在count数组本身中
      对于j <-减小到1
        恢复元素到数组
        将还原的每个元素的数量减少1

    Java示例

     
    import java.util.Arrays;
    
    public class CountingSortDemo {
    	public static void main(String[] args) {
    		int[] array = { 4, 2, 2, 8, 3, 3, 1 };
    		// Find the maximum element in the input array
    		int max = findMaxElement(array);
    		System.out.println("Max Value in input array-" + max);
    		System.out.println("Original Array- " + Arrays.toString(array));
    		int[] sortedArr = countingSort(array, max + 1);
    		System.out.println("Sorted array after counting sort- " + Arrays.toString(sortedArr));
    	}
    
    	private static int findMaxElement(int[] array) {
    		int max = array[0];
    		for (int val : array) {
    			if (val > max)
    				max = val;
    		}
    		return max;
    	}
    
    	private static int[] countingSort(int[] array, int range) {
    		int[] output = new int[array.length];
    		int[] count = new int[range];
    		// Calculate frequency of each element, put it in count array
    		for (int i = 0; i < array.length; i++) {
    			count[array[i]]++;
    		}
    		System.out.println("Count array- " + Arrays.toString(count));
    
    		// Modify count array to get the final position of elements
    		for (int i = 1; i < range; i++) {
    			count[i] = count[i] + count[i - 1];
    		}
    		System.out.println("Modified count array- " + Arrays.toString(count));
    
    		// Add elements to output sorted array
    		for (int i = 0; i < array.length; i++) {
    			output[count[array[i]] - 1] = array[i];
    			count[array[i]]--;
    		}
    		return output;
    	}
    }

     

    输出:

    Max Value in input array-8
    Original Array- [4, 2, 2, 8, 3, 3, 1]
    Count array- [0, 1, 2, 2, 1, 0, 0, 0, 1]
    Modified count array- [0, 1, 3, 5, 6, 6, 6, 6, 7]
    Sorted array after counting sort- [1, 2, 2, 3, 3, 4, 8]
     


    复杂

    时间复杂度:

    主要有四个主要循环。(可以在函数外部找到最大值。)

    循环计数时间
    第一O(最大)
    第二名O(大小)
    第三名O(最大)
    第四名O(大小)

    总体复杂度= O(max)+O(size)+O(max)+O(size)=O(max+size)

    • 最坏情况的复杂性: O(n+k)
    • 最佳案例复杂度: O(n+k)
    • 平均案件复杂度: O(n+k)

    在上述所有情况下,复杂度都是相同的,因为无论元素如何放置在数组中,算法都会经历n+k时间。

     

     

    任何元素之间都没有比较,因此它比基于比较的排序技术要好。但是,如果整数很大,那是不好的,因为应该制作该大小的数组。

    空间复杂度:

    计数排序的空间复杂度为O(max)。元素范围越大,空间复杂度越大。


    计算排序应用程序

    在以下情况下使用计数排序:

    • 有多个较小的整数。
    • 线性复杂度是必要的。
    展开全文
  • 计数排序(Counting sort)是一种稳定的线性时间排序算法,其平均时间复杂度和空间复杂度为O(n+k),其中n为数组元素的个数,k为待排序数组里面的最大值。同样具有线性时间排序的算法还有桶排序和基数排序,这一点...
    计数排序(Counting sort)是一种稳定的线性时间排序算法,其平均时间复杂度和空间复杂度为O(n+k),其中n为数组元素的个数,k为待排序数组里面的最大值。同样具有线性时间排序的算法还有桶排序和基数排序,这一点不要搞混。
    


    计数排序不是基于比较的排序,所以它的排序效率是线性的,在特定的场景下(已知数组的最大最小值,切数组元素整体量不是很大的情况下)排序效率极高,而基于比较排序的算法,其时间复杂度基本逃脱不了O(nlogn)的魔咒,当然能达到O(nlogn)的时间复杂度,已经是非常牛逼了,这里面典型的代表就是快速排序算法,因为没有其他条件限制,所以基本上是一种通用排序算法。


    计数排序的算法的原理,其实是非常简单的,它不需要去跟其他元素比来比去,而是一开始就知道自己的位置,所以直接归位,在计数的该元素出现的词频数组里面,出现一次,就直接+1一次即可,如果没有出现改位置就是0,最后该位置的词频,就是代表其在原始数组里面出现的次数,由于词频数组的index是从0开始,所以最后直接遍历输出这个数组里面的每一个大于0的元素值即可。

    我们先来看看简单版本的Java语言写的计数排序是如何实现的,假设有四个元素{2,1,0,1}。

    ```
    public static void simpleCountSort(){
    int nums[]={2,1,0,1};

    int maxNum=2;

    int storeArray[]=new int[maxNum+1];

    //词频计数
    for(int i=0;i<nums.length;i++){
    storeArray[nums[i]]++;
    }

    System.out.println("==============排序后==============");

    int ndx=0;
    //遍历计数后的词频数组
    for (int i = 0; i <storeArray.length ; i++) {
    //对于每个index的值进行循环,输出,因为有可能重复
    while (storeArray[i]>0){
    nums[ndx]=i;//把词频数组的值,放回原数组里面,
    ndx++;//替换一个数,就索引自增
    storeArray[i]--;//词频减1,防止死循环
    }
    }


    System.out.println(Arrays.toString(nums));


    }
    ```

    从上面可以看到,代码比较简单,但是并不是最优的,有三个缺点:

    第一不支持负数排序,第二在特定情况下使用空间较多,比如90-100仅仅有10个元素,但是数组却需要声明空间为100,第三排序不具有稳定性,重复元素的相对位置可能会变。

    经过优化后的计数排序算法,需要遍历一次得到元素的最小值和最大值,然后构造空间范围可以优化为,max-min+1,而不是前面简单的max,此外在实现的时候,对于原数组统计词频的时候,使用的每个元素减去min之后的值,这样能保证结果落在词频数组的范围之内,最后,为了保证排序算法的稳定性,我们需要对词频进行一次sum操作,从1开始,把每个位置的词频设置为当前的元素的词频+前一个元素的词频,这个值就代表了其在原数组里面应该出现的位置,接着我们倒序遍历原始数组,这样就能保证稳定性。 具体的算法过程,我推荐一个youtube上的一个视频,演示的最常清晰:

    [url] https://m.youtube.com/watch?v=TTnvXY82dtM[/url]

    优化后的代码如下:

    ```
    public static int[] countSort(int []a){
    //使用最大值和最小值的方式是一种优化的计数排序
    //可以兼容负数的情况,同时能减少存储的空间,比如最大数是100,但实际上只有90-100这10个数字
    //所以仅仅需要10个存储空间即可
    int max = a[0], min = a[0];
    for(int i : a){
    max=Math.max(max,i);
    min=Math.min(min,i);
    }
    System.out.println("max:"+max+" min:"+min);
    int k = max - min + 1;
    System.out.println("count array len:"+k);

    int c[] = new int[k];
    //先是count计数词频
    for(int i = 0; i < a.length; ++i){
    c[a[i]-min] ++;//优化过的地方,减小了数组c的大小,同时a[i]-min能保证c数组的第一个元素一定有元素的
    //因为必定存在min-min=0
    }
    System.out.println("count: "+Arrays.toString(c));
    //然后为了保持排序稳定,我们需要做一次累加操作
    //这样做的目的,是为了标记出原始数组里面的该元素,前面有几个元素,这个值
    //实际上就是其在原生数组里面的位置,如果有重复的元素,则会先会
    //放置最右边的元素,这样就能保证,排序的稳定性
    for(int i = 1; i < c.length; ++i){
    c[i] = c[i] + c[i-1];
    }

    System.out.println("sumCount:"+Arrays.toString(c));

    //存储最终的排序结果
    int b[] = new int[a.length];
    //这里必须从后向前遍历,只有这样出现重复的元素,才会保持顺序的把最后面的重复元素,永远放在最右边。
    //从而保证排序的稳定性
    //如果从前向后排序,重复元素的顺序,刚好相反,所以就不是稳定的算法,但如果不关注稳定性,那么结果还是正确的
    for (int i = a.length-1; i >=0 ; i--) {
    //减去min是为了优化存储空间,这样得到新的转换值,
    int pos=a[i]-min;
    int sumCount=c[pos];

    System.out.println(a[i]+" 在原数组的排序后的位置是: "+(sumCount-1));

    //把最终生层的排序值,放在新的数组里面返回
    b[sumCount-1]=a[i];
    c[pos]--; //如果有重复元素,位置需要从右向左放置,所以需要把sumCount的值-1

    }


    return b;
    }
    ```

    其中关键的地方有两个:

    第一,在于理解计算max和min之后,需要使用原数组每一个元素减去min的转换值统计词频,特定情况下能节省存储空间,这样做的另一个好处是可以兼容负数的情况,因为每一个元素减去最小值之后,结果必定是大于等于0


    第二,在于理解为什么采用词频求和的方式+倒序遍历原始数组的方式,能保证排序算法的稳定性


    理解了上面的两点,再来看优化后的计数排序就非常简单了,如果想证明计数排序的稳定性,可以参考我的github上的例子。

    [url]https://github.com/qindongliang/Java-Note[/url]


    总结:

    经典的计数排序分四个阶段:

    1,找出数组里面的最大值和最小值

    2,求出每个元素出现的词频(count)

    3,遍历词频数组求和

    4,反向遍历原始数组,进行目标数组填充,填充后的数组再遍历就是有序的。


    如果不考虑算法的稳定性和负数情况及特定情况的浪费空间,那么只需要前面的2步就可以了,如果想要保证稳定性,那么需要经过这4步计算。具体证明计数排序的稳定性的例子,可以参考我的github上例子:

    [url]https://github.com/qindongliang/Java-Note/blob/master/src/main/java/sort_algorithm/count_sort/ProveStableCountingSort.java[/url]


    计数排序在特定的情况下,排序效率极高,但是如果排序的计数空间范围过大,而实际元素个数非常小的情况,效率就会非常差,比如,我只有3个元素,3,1,500000,这样的情况其实是不适合用计数排序的,这一点需要注意。
    展开全文
  • 概述 计数排序与其它排序并不一样,其它排序是基于比较...计数排序属于稳定排序,顺便说一下排序算法稳定性的定义,两个相同的元素的相对位置不发生变化,则该算法具有稳定性。 算法分解 获取最大值,申请临时的连续
  • 计数排序算法实例

    2012-11-29 09:42:05
    算法导论上计数排序算法的vc.60Test实例
  • 算法-计数排序

    2016-04-17 22:40:41
    主要是对算法导论中计数排序的实现
  • 麻省理工学院“算法导论”课程中介绍的计数排序算法的实现。 例子 var countingSort = require ( './countingSort.js' ) ; // Construct input [0, 5], therefore an array of size 6 is needed // for the ...
  • C语言 计数排序算法

    2021-12-01 19:53:49
    计数排序的基本思想:对每一个输入元素 x ,确定小于 x 的元素个数。利用这一信息,就可以直接把 x 放在输出数组中对应的位置上。例如,假如有 17 个元素小于 x,则 x 就应该放在第 18 个输出位置上。当数组中有相同...
  • 经典算法——计数排序算法

    万次阅读 多人点赞 2017-03-12 00:06:47
    它是一个不需要比较的,类似于桶排序的线性时间排序算法。该算法是对已知数量范围的数组进行排序。其时间复杂度为O(n),适用于小范围集合的排序。计数排序是用来排序0到100之间的数字的最 好的算法。比如100万学生...
  • 计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。 一、算法基本思想...
  • 提出了一种改进的计数排序算法。首先找到待排序记录应该存放的位置,然后在原数组空间上进行交换。与传统的计数排序算法相比,在不改变时间复杂度的同时,降低了空间复杂度,提高了算法性能。
  • 计数排序假设nnn个输入元素中的每一个都是在000到kkk区间内的一个整数,其中kkk为某个整数。当k=O(n)k=O(n)k=O(n)时,排序的运行时间为Θ(n)\Theta(n)Θ(n)。...在计数排序算法的代码中,假设输入是一
  • 计数排序的思想 计数排序,当数据范围max不大的时候,可以使用一个长度为max+1,即[0,max]的数组用以存储数据出现的次数。根据这个数据出现的次数,通过一定的计算,就可以知道这个数据之前到底有多少个数据,那么...
  • 计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。 二、算法分析 1、算法描述 找出...
  • 基于openMP的并行计数排序算法

    千次阅读 2020-04-21 15:05:56
    基于openMP的并行计数排序算法 这是云计算的作业,实现对某个算法或程序的性能优化,以前没有接触过,所以使用了比较简单上手的openMP来实现。 代码如下 #include <stdio.h> #include <omp.h> #include ...
  • 计数排序算法讲解

    2018-09-25 23:41:39
    前面我讲解了一个基数排序算法,这地方要说一下哈,同音不同字,不要弄混淆了 今天我们讲的这个算法呢,这,这,这,又一个看名字就能看出来一点道道的,的确,计数算法就是给每个元素计一些数,通过一些数来对元素...
  • 前面我们详细讲解了计数排序算法,今天我们用代码来实现 #!/usr/bin/python # -*- coding: utf-8 -*- #计数排序 def _counting_sort(the_list): the_len = len(the_list) if the_len &lt;2:#0和1 print &...
  • 本文实例讲述了JS实现的计数排序与基数排序算法。分享给大家供大家参考,具体如下: 计数排序 计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数组数字范围一样大的辅助数组,一般用在...
  • 排序的利用的是数组的下标可以自动排序 var arr = []; //arr[乱序下标] = 随意数组 arr[5] = 1; arr[2] = 1; arr[3] = 1; arr[9] = 1; arr[10] = 1; //无论放入的顺序是什么,数组的排序都是不会乱的 console.log...
  • 计数排序算法(C语言实现)

    千次阅读 2012-11-17 16:36:12
    计数排序, 比较适合数值跨度比较小的, 也就是数组中最大值减去最小值得到的值尽量小, 同时数组元素又比较多的情况下用计数排序效率比较高,同时,计数排序算法基友稳定性。 计数排序的时间复杂度为O(n),...
  • 计数排序并行openmp Esterepositórioabriga实施工具会按顺序对序数进行排序。 Esses algoritmos foram desenvolvidos no Programme da Disciplina deProgramaçãoParalela e Multicore do curso deCiê...
  • 本回,将对计数排序进行相关说明分析。 一、排序算法系列目录说明 冒泡排序(Bubble Sort) 插入排序(Insertion Sort) 希尔排序(Shell Sort) 选择排序(Selection Sort) 快速排序(Quick Sort...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 89,221
精华内容 35,688
关键字:

计数排序算法