AI 助理
备案控制台
开发者社区 人工智能 文章 正文

【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）

2023-10-13 55
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）

一，计数排序

计数排序也叫非比较排序；

1，基本思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用

操作步骤：

1，统计相同元素出现次数

2，根据统计的结果将序列回收到原来的序列中

图解原理：

对这样一个不需要比较的排序就完成了；

2，思路实现

// 计数排序
void CountSort(int* arr, int n)
{
  int i = 0;
  int max = arr[0], min = arr[0];
  //找最大，最小值
  for (i = 0; i < n; i++)
  {
    if (arr[i] > max)
    {
      max = arr[i];
    }
    if (arr[i] < min)
    {
      min = arr[i];
    }
  }
  //空间大小
  int sum = max - min + 1;
  //开辟空间并且使元素值都为0
  int* arr1 = (int*)calloc(sum, sizeof(int));
  //给新数组赋值
  for (i = 0; i < n; i++)
  {
    arr1[arr[i] - min]++;
  }
  int j = 0;
  //回收到原来的序列中
  for (i = 0; i < sum; i++)
  {
    while (arr1[i]--)
    {
      arr[j++] = i + min;
    }
  }
}

然后我们运行测试一下：

可以看到是有序的，选择排序就 OK 了；

3，计数排序的特性总结：

1， 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限

2.，时间复杂度：O(N+K)

3， 空间复杂度：O(N)

4, 稳定性：稳定

二，排序算法复杂度及稳定性分析

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(N^2) O(N) O(N^2) O(1) 稳定
选择排序 O(N^2)     O(N^2)  O(N^2)  O(1) 不稳定
直接插入排序 O(N^2)  O(N) O(N^2) O(1) 稳定
希尔排序 O(NlongN)~O(N^2) O(N^1.3) O(N^2) O(1) 不稳定
堆排序 O(NlongN) O(NlongN) O(NlongN) O(1) 不稳定
归并排序 O(NlongN) O(NlongN) O(NlongN) O(N) 稳定
快速排序 O(NlongN) O(NlongN) O(N^2) O(N) 不稳定
计数排序 O(N+K) O(N+K) O(N+K) O(K) 稳定

三，排序系列所有源代码

Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include"Stack.h"
//打印
void PrintSort(int* arr, int n);
//插入排序
void InsertSort(int* arr, int n);
//希尔排序
void HillSort(int* arr, int n);
//选择排序
void SeleSort(int* arr, int n);
//堆排序
void HeapSort(int* arr, int n);
//向下调整
void DownAdjust(int* arr, int n, int i);
冒泡排序
//void BubblSort(int* arr, int n);
//快速排序
void QuickSort(int* arr, int begin, int end);
//三数取中
int middle(int* arr, int left, int right);
//快慢指针法
int PartSort3(int* arr, int left, int right);
//挖坑法
int PartSort2(int* arr, int left, int right);
//霍尔排序
int PartSort1(int* arr, int left, int right);
//快速排序(非递归)
void QuickNon(int* arr, int begin, int end);
//归并排序
void MergerSort(int* arr, int begin, int end);
//归并排序(非递归)
void MergerSortNon(int* arr, int begin, int end);
// 计数排序
void CountSort(int* arr, int n);

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
//打印
void PrintSort(int* arr, int n)
{
  int i = 0;
  for (i = 0; i < n; i++)
  {
    printf("%d ", arr[i]);
  }
}
//交换
void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
//插入排序
void InsertSort(int* arr, int n)
{
  int i = 0;
  for (i = 0; i < n-1; i++)
  {
    int end = i;
    int tmp = arr[end + 1];
    while (end >= 0)
    {
      if (arr[end] >= tmp)
      {
        //交换
        Swap(&arr[end], &arr[end+1]);
        end--;
      }
      else
      {
        break;
      }
    }
    arr[end + 1] = tmp;
  }
}
//希尔排序
void HillSort(int* arr, int n)
{
  int gap = n;
  int i = 0;
  while (gap > 1)
  {
    gap = gap / 2;
    for (i = 0; i < n-gap; i++)
    {
      int end = i;
      int tmp = arr[end + gap];
      while (end >= 0)
      {
        if (arr[end] >= tmp)
        {
          //交换
          Swap(&arr[end], &arr[end + gap]);
          end -= gap;
        }
        else
        {
          break;
        }
      }
      arr[end + gap] = tmp;
    }
  }
}
//选择排序
void SeleSort(int* arr, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
    int maxi = begin, mini = begin;
    for (int i = begin; i <= end; i++)
    {
      if (arr[i] > arr[maxi])
      {
        maxi = i;
      }
      if (arr[i] < arr[mini])
      {
        mini = i;
      }
    }
    Swap(&arr[begin], &arr[mini]);
    // 如果maxi和begin重叠，修正一下即可
    if (begin == maxi)
    {
      maxi = mini;
    }
    Swap(&arr[end], &arr[maxi]);
    ++begin;
    --end;
  }
}
//向下调整
void DownAdjust(int* arr, int n, int i)
{
  int perent = i;
  int child = perent* 2 + 1;
  while (child<n)
  {
    if (child+1<n && arr[child + 1] > arr[child])
    {
      child++;
    }
    if (arr[perent] < arr[child])
    {
      //交换
      Swap(&arr[perent], &arr[child]);
      perent = child;
      child = perent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//堆排序
void HeapSort(int* arr, int n)
{
  //建堆
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    //向下调整
    DownAdjust(arr, n, i);
  }
  //交换，删除排序法
  while (n > 1)
  {
    //交换
    Swap(&arr[0], &arr[n - 1]);
    n--;
    //向下调整
    DownAdjust(arr, n, 0);
  }
}
//三数取中
int middle(int* arr, int left, int right)
{
  //int mid = (left +right)/ 2;
  //随机数取中
  int mid = left + (rand() % (right - left));
  if (arr[left] < arr[mid])
  {
    if (arr[mid] < arr[right])
    {
      return mid;
    }
    if (arr[left] < arr[right])
    {
      return right;
    }
    else
    {
      return left;
    }
  }
  //arr[mid]<=arr[left]
  else
  {
    if (arr[mid] > arr[right])
    {
      return mid;
    }
    if (arr[left] > arr[right])
    {
      return right;
    }
    else
    {
      return left;
    }
  }
}
//霍尔排序
int PartSort1(int* arr, int left, int right)
{
  //三数取中
  int ret = middle(arr, left, right);
  Swap(&arr[left], &arr[ret]);
  int keyi = left;
  while (left < right)
  {
    //右边先走
    while (left<right && arr[right]>=arr[keyi])
    {
      right--;
    }
    //左边后走
    while (left < right && arr[left] <= arr[keyi])
    {
      left++;
    }
    //交换
    Swap(&arr[left], &arr[right]);
  }
  Swap(&arr[left], &arr[keyi]);
  return left;
}
//挖坑法
int PartSort2(int* arr, int left, int right)
{
  //三数取中
  int ret = middle(arr, left, right);
  Swap(&arr[left], &arr[ret]);
  int key = arr[left];
  int hole = left;
  while (left < right)
  {
    while (left < right && arr[right] >= key)
    {
      right--;
    }
    arr[hole] = arr[right];
    hole = right;
    while (left < right && arr[left] <= key)
    {
      left++;
    }
    arr[hole] = arr[left];
    hole = left;
  }
  arr[hole] = key;
  return hole;
}
//前后指针法
int PartSort3(int* arr, int left, int right)
{
  //三数取中
  int ret = middle(arr, left, right);
  Swap(&arr[left], &arr[ret]);
  int keyi = left;
  int slow = left, fast = left+1;
  while (fast<=right)
  {
    if (arr[fast] < arr[keyi] && ++slow!=fast)
    {
      //交换
      Swap(&arr[fast], &arr[slow]);
    }
    fast++;
  }
  Swap(&arr[slow], &arr[keyi]);
  return slow;
}
//插入排序(改造版)
void InsertSort1(int* arr, int left, int right)
{
  int i = 0;
  for (i = left; i < right; i++)
  {
    int end = i;
    int tmp = arr[end + 1];
    while (end >= 0)
    {
      if (arr[end] >= tmp)
      {
        //交换
        Swap(&arr[end], &arr[end + 1]);
        end--;
      }
      else
      {
        break;
      }
    }
    arr[end + 1] = tmp;
  }
}
//快速排序
void QuickSort(int* arr, int begin, int end)
{
  srand(time(0));
  if (begin >= end)
  {
    return NULL;
  }
  if (end - begin <10)
  {
    InsertSort1(arr,begin,end);
  }
  else
  {
    int keyi = PartSort1(arr, begin, end);
    //排序[begin,keyi) & [keyi+1,end]
    QuickSort(arr, begin, keyi);
    QuickSort(arr, keyi + 1, end);
  }
}
//快速排序(非递归)
void QuickNon(int* arr, int begin, int end)
{
  srand(time(0));
  ST ps;
  //初始化
  STInit(&ps);
  if (begin >= end)
  {
    return;
  }
  //插入
  STPush(&ps, end);
  STPush(&ps, begin);
  //栈不为空就进去
  while (!STEmpty(&ps))
  {
    int left = STInsert(&ps);//栈顶元素
    STPop(&ps);//删除
    int right = STInsert(&ps);
    STPop(&ps);
    int keyi = PartSort1(arr, left, right);
    //排序[left,keyi-1] & [keyi+1,right]
    if (keyi + 1 < right)
    {
      //插入
      STPush(&ps, right);
      STPush(&ps, keyi + 1);
    }
    if (left < keyi - 1)
    {
      //插入
      STPush(&ps, keyi - 1);
      STPush(&ps, left);
    }
  }
  //销毁
  STDestroy(&ps);
}
//归并
void Merger(int* arr, int* tmp,int begin,int end)
{
  int mid = (begin + end) / 2;
  if (begin == end)
  {
    return;
  }
  //排序【begin,mid】& 【mid+1,end】
  Merger(arr, tmp, begin,mid);
  Merger(arr, tmp, mid+1, end);
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int i = 0;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (arr[begin1] < arr[begin2])
    {
      tmp[i++] = arr[begin1++];
    }
    else
    {
      tmp[i++] = arr[begin2++];
    }
  }
  while(begin1 <= end1)
  {
    tmp[i++] = arr[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = arr[begin2++];
  }
  //进行拷贝
  memcpy(arr + begin, tmp, (end - begin+1)*sizeof(int));
}
//归并排序
void MergerSort(int* arr, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  //开辟同等大小数组
  int* tmp = (int*)malloc((end - begin + 1)*sizeof(int));
  //归并
  Merger(arr, tmp, begin, end);
  free(tmp);
  tmp = NULL;
}
//归并排序(非递归)
void MergerSortNon(int* arr, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  //开辟同等大小数组
  int* tmp = (int*)malloc((end - begin + 1) * sizeof(int));
  int gap = 1;
  int j = 0;
  while (gap < end)
  {
    for (j = 0; j < end; j += 2 * gap)
    {
      int begin1 = j, end1 = begin1+gap-1;
      int begin2 =end1+1, end2 = begin2+gap-1;
      int i = 0;
      //处理边界问题
      if (end1 >= end)
      {
        break;
      }
      if (end2 >end)
      {
        end2 = end;
      }
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (arr[begin1] < arr[begin2])
        {
          tmp[i++] = arr[begin1++];
        }
        else
        {
          tmp[i++] = arr[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[i++] = arr[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[i++] = arr[begin2++];
      }
      //进行拷贝
      memcpy(arr + j, tmp, (end2 - j+ 1) * sizeof(int));
    }
    gap *= 2;
  }
  free(tmp);
  tmp = NULL;
}
// 计数排序
void CountSort(int* arr, int n)
{
  int i = 0;
  int max = arr[0], min = arr[0];
  //找最大，最小值
  for (i = 0; i < n; i++)
  {
    if (arr[i] > max)
    {
      max = arr[i];
    }
    if (arr[i] < min)
    {
      min = arr[i];
    }
  }
  //空间大小
  int sum = max - min + 1;
  //开辟空间并且使元素值都为0
  int* arr1 = (int*)calloc(sum, sizeof(int));
  //给新数组赋值
  for (i = 0; i < n; i++)
  {
    arr1[arr[i] - min]++;
  }
  int j = 0;
  //回收到原来的序列中
  for (i = 0; i < sum; i++)
  {
    while (arr1[i]--)
    {
      arr[j++] = i + min;
    }
  }
}

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct StackTop
{
  STDataType* a;
  int top;
  int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//返回栈顶
STDataType STInsert(ST* ps);
//数量
int STSize(ST* ps);
//判断是否为空
int STEmpty(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void STInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
//销毁
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
//插入
void STPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    ps->capacity = ps->top == 0 ? 4 : ps->capacity*2;
    ps->a = (STDataType*)realloc(ps->a,sizeof(STDataType)*ps->capacity);
  }
  ps->a[ps->top] = x;
  ps->top++;
}
//删除
void STPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  ps->top--;
}
//返回栈顶
STDataType STInsert(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top-1];
}
//数量
int STSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
//判断是否为空
int STEmpty(ST* ps)
{
  assert(ps);
  if (ps->top == 0)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}

同志们！排序的知识就到这里了！

后面博主会陆续更新；

如有不足之处欢迎来补充交流！

完结。。

文章标签：
搜索推荐
关键词：
数据结构复杂度
数据结构排序
数据结构计数排序
数据结构分析
数据结构排序复杂度
手法king
目录
相关文章
java冯坚持
|
1月前
|
算法 搜索推荐 Java
数据结构与算法学习十三：基数排序，以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法，通过将数字按位数切割并分配到不同的桶中，以空间换时间的方式实现快速排序，但占用内存较大，不适合含有负数的数组。
java冯坚持
23 0
数据结构与算法学习十三：基数排序，以空间换时间的稳定式排序,速度很快。
GuGuStudy
|
1月前
|
存储 搜索推荐 算法
【用Java学习数据结构系列】七大排序要悄咪咪的学（直接插入，希尔，归并，选择，堆排，冒泡，快排）以及计数排序（非比较排序）
【用Java学习数据结构系列】七大排序要悄咪咪的学（直接插入，希尔，归并，选择，堆排，冒泡，快排）以及计数排序（非比较排序）
GuGuStudy
22 1
小言从不摸鱼
|
1月前
|
算法
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
小言从不摸鱼
16 1
是店小二呀
|
1月前
|
人工智能 搜索推荐 算法
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（三）
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
是店小二呀
24 0
ephemerals__
|
15天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
那年春天
|
6天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
15 1
德国都芳最好
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
48 21
html的七十二变
|
12天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
26 2
dufadayang
|
14天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
42 4
java冯坚持
|
1月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
30 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器

热门文章

最新文章

  • 1
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 2
    数据结构学习笔记【持续更新】
  • 3
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 4
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 5
    学数据结构，只需要基本的编程体验
  • 6
    数据结构（2）：栈的原理和实现
  • 7
    【数据结构7】查找
  • 8
    算法导论第十四章 数据结构的扩张
  • 9
    R语言学习笔记（一）数据结构
  • 10
    基于OHCI的USB主机 —— UFI数据结构2
  • 1
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    97
  • 2
    数据结构（五）----特殊矩阵的压缩存储
    243
  • 3
    数据结构（九）---并查集
    67
  • 4
    【数据结构与算法 11，高并发系统基础篇
    41
  • 5
    JavaScript 中实现常见数据结构：栈、队列与树
    78
  • 6
    数据结构链表详解(不仅顺序表可以，我链表也可以)
    41
  • 7
    顺序表的实现（迈入数据结构的大门）（2）
    39
  • 8
    顺序表的实现（迈入数据结构的大门）（1）
    32
  • 9
    每个程序员都必须掌握的8种数据结构，retrofit教程
    35
  • 10
    scala中常见数据结构的用法
    45

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 图解算法小抄
    • 下一篇
    阿里云OSS设置跨域访问