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月前
|
搜索推荐 索引
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（二）
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
是店小二呀
27 4
小言从不摸鱼
|
1月前
|
算法
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
小言从不摸鱼
16 1
星霜旅人
|
1月前
|
算法
数据结构（复杂度）
数据结构（复杂度）
星霜旅人
17 0
阿客不是客
|
1月前
|
存储 机器学习/深度学习 算法
探索数据结构：入门及复杂度的解锁
探索数据结构：入门及复杂度的解锁
阿客不是客
19 0
是店小二呀
|
1月前
|
人工智能 搜索推荐 算法
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（三）
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
是店小二呀
24 0
ephemerals__
|
16天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
那年春天
|
6天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
15 1
德国都芳最好
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
49 21

热门文章

最新文章

  • 1
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 2
    数据结构学习笔记【持续更新】
  • 3
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 4
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 5
    学数据结构，只需要基本的编程体验
  • 6
    数据结构（2）：栈的原理和实现
  • 7
    【数据结构7】查找
  • 8
    算法导论第十四章 数据结构的扩张
  • 9
    R语言学习笔记（一）数据结构
  • 10
    基于OHCI的USB主机 —— UFI数据结构2
  • 1
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    98
  • 2
    数据结构（五）----特殊矩阵的压缩存储
    243
  • 3
    数据结构（九）---并查集
    70
  • 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设置跨域访问