C++ 计数排序实例详解

计数排序

计数排序是一种非比较的排序算法

优势：

计数排序在对于一定范围内的整数排序时，时间复杂度为O(N+K)  （K为整数在范围）快于任何比较排序算法，因为基于比较的排序时间复杂度在理论上的上下限是O(N*log(N))。

缺点：

计数排序是一种牺牲空间换取时间的做法，并且当K足够大时O（K）>O(N*log(N)),效率反而不如比较的排序算法。并且只能用于对无符号整形排序。

时间复杂度：

O（N）  K足够大时为O（K）

空间复杂度：

O（最大数-最小数）

性能：

计数排序是一种稳定排序

代码实现：

#include <iostream>
#include <Windows.h>
#include <assert.h> 

using namespace std; 

//计数排序，适用于无符号整形
void CountSort(int* a, size_t size)
{
  assert(a);
  size_t max = a[0];
  size_t min = a[0];
  for (size_t i = 0; i < size; ++i)
  {
    if (a[i] > max)
    {
      max = a[i];
    }
    if (a[i] < min)
    {
      min = a[i];
    }
  }
  size_t range = max - min + 1;   //要开辟的数组范围
  size_t* count = new size_t[range];
  memset(count, 0, sizeof(size_t)*range);  //初始化为0
  //统计每个数出现的次数
  for (size_t i = 0; i < size; ++i)   //从原数组中取数，原数组个数为size
  {
    count[a[i]-min]++;
  }
  //写回到原数组
  size_t index = 0;
  for (size_t i = 0; i < range; ++i)  //从开辟的数组中读取，开辟的数组大小为range
  {
    while (count[i]--)
    {
      a[index++] = i + min;
    }
  }
  delete[] count;
} 

void Print(int* a, size_t size)
{
  for (size_t i = 0; i < size; ++i)
  {
    cout << a[i] << " ";
  }
  cout << endl;
}

#include "CountSort.h" 

void TestCountSort()
{
  int arr[] = { 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 2, 4, 5, 8, 9, 5, 11, 11, 22, 12, 12 };
  size_t size = sizeof(arr) / sizeof(arr[0]);
  CountSort(arr, size);
  Print(arr, size);
} 

int main()
{
  TestCountSort();
  system("pause");
  return 0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • C++计数排序详解

    C++计数排序详解

    计数排序不同于比较排序,是基于计数的方式,对于计数排序,假设每一个输入都是介于0~k之间的整数.对于每一个输入元素x,确定出小于x的元素的个数.假如有17个元素小于x,则x就属于第18个输出位置. 计数排序涉及到三个数组A[0-..length-1],length为数组A的长度:数组B与数组A长度相等,存放最终排序的结果:C[0-..K]存放A中每个元素的个数,k为数组A中的最大值. int count_k(int A[],int length),此函数为了确定数组A中最大的元素,用来确定C数组

  • C++ 计数排序实例详解

    C++ 计数排序实例详解

    计数排序 计数排序是一种非比较的排序算法 优势: 计数排序在对于一定范围内的整数排序时,时间复杂度为O(N+K)  (K为整数在范围)快于任何比较排序算法,因为基于比较的排序时间复杂度在理论上的上下限是O(N*log(N)). 缺点: 计数排序是一种牺牲空间换取时间的做法,并且当K足够大时O(K)>O(N*log(N)),效率反而不如比较的排序算法.并且只能用于对无符号整形排序. 时间复杂度: O(N)  K足够大时为O(K) 空间复杂度: O(最大数-最小数) 性能: 计数排序是一种稳定排序

  • Angular排序实例详解

    说点小案例angular的排序 <!DOCTYPE html> <html ng-app="mk"> <head> <meta charset="UTF-8"> <title></title> <style type="text/css"> *{ margin: 0px; padding: 0px; } nav{ text-align: center; } nav

  • Java Map的排序实例详解

     Java Map的排序实例详解 要对Map中的key-value键值对进行排序,可以使用Collections类提供的sort方法.该方法允许用户使用自定义的排序方法,可以按键进行排序,或者按值进行排序. 具体代码如下: 1.产生需要的数据 Map<String, Integer> map_Data = new HashMap<String, Integer>(); map_Data.put("A", 98); map_Data.put("B&quo

  • python字典排序实例详解

    本文实例分析了python字典排序的方法.分享给大家供大家参考.具体如下: 1. 准备知识: 在python里,字典dictionary是内置的数据类型,是个无序的存储结构,每一元素是key-value对: 如:dict = {'username':'password','database':'master'},其中'username'和'database'是key,而'password'和'master'是value,可以通过d[key]获得对应值value的引用,但是不能通过value得到k

  • javascript中sort排序实例详解

    javascript中sort排序实例详解

    代码如下所示: var arr = [5,32,28,66,2,15,3]; arr.sort(function(a1,a2){ return a1-a2; //a2-a1 输入倒序 }); console.log(arr); console.log(arr.reverse()); //reverse颠倒数组中元素的顺序 var arr2 = ['hezihao','chensan','xiaomin','lishi'] arr2.sort(); console.log(arr2); var a

  • 利用JavaScript对中文（汉字）进行排序实例详解

    利用JavaScript对中文（汉字）进行排序实例详解

    前言 在网页上展示列表时经常需要对列表进行排序:按照修改/访问时间排序.按照地区.按照名称排序. 对于中文列表按照名称排序就是按照拼音排序,不能简单通过字符串比较-- 'a' > 'b'--这种方式来实现. 比如比较 '北京' vs '上海',实际是比较 'běijīng' vs 'shànghǎi':比较 '北京' vs '背景',实际是比较 'běijīng' vs 'bèijǐng'. 一般需要获取到字符串的拼音,再比较各自的拼音. 实现方法 JavaScript 提供本地化文字排序,比如

  • 深入IComparable与IComparer的排序实例详解

    如下所示: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Text;using System.Collections;namespace hgoApp{    class Comparer    {        static void Main()        {            Employee[] Employees = new Employee[5]; Employees[0] = ne

  • Java集合和数据结构排序实例详解

    Java集合和数据结构排序实例详解

    目录 概念 插入排序 直接插入排序 代码实现 性能分析 希尔排序 代码实现 性能分析 选择排序 直接选择排序 代码实现 性能分析 堆排序 代码实现 性能分析 交换排序 冒泡排序 代码实现 性能分析 快速排序 代码实现 性能分析 非递归实现快速排序 代码实现 性能分析 归并排序 归并排序 代码实现 性能分析 非递归实现归并排序 代码实现 性能分析 海量数据的排序问题 总结 概念 排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作. 平时的上下文中,如果提到排序,通常

  • Android 中ViewPager重排序与更新实例详解

    Android 中ViewPager重排序与更新实例详解 最近的项目中有栏目订阅功能,在更改栏目顺序以后需要更新ViewPager.类似于网易新闻的频道管理. 在重新排序之后调用了PagerAdapter的notifyDataSetChanged方法,发现ViewPager并没有更新,于是我开始跟踪源码,在调用PagerAdapter的notifyDataSetChanged方法后,会触发Viewpager的dataSetChanged方法. void dataSetChanged() { //

  • Java 选择排序、插入排序、希尔算法实例详解

    Java 选择排序、插入排序、希尔算法实例详解

    1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu

随机推荐