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

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

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

一，计数排序

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

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
目录
相关文章
RossyYan
|
2天前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序（头歌实践教学平台习题）【合集】
本关任务是实现二路归并算法，即将两个有序数组合并为一个有序数组。主要内容包括： - **任务描述**：实现二路归并算法。 - **相关知识**： - 二路归并算法的基本概念。 - 算法步骤：通过比较两个有序数组的元素，依次将较小的元素放入新数组中。 - 代码示例（以 C++ 为例）。 - 时间复杂度为 O(m+n)，空间复杂度为 O(m+n)。 - **测试说明**：平台会对你编写的代码进行测试，提供输入和输出示例。 - **通关代码**：提供了完整的 C++ 实现代码。 - **测试结果**：展示代码运行后的排序结果。 开始你的任务吧，祝你成功！
RossyYan
23 10
RossyYan
|
2天前
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序（头歌实践教学平台习题）【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括： - **任务描述**：实现希尔排序算法。 - **相关知识**： - 排序算法基础概念，如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列（增量序列）的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧，如循环嵌套和索引计算。 - **测试说明**：提供了测试输入和输出示例，帮助验证代码正确性。 - **我的通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了代码运行的测试结果。 通过这些内容，读者可以全面了解希尔排序的原理和实现方法。
RossyYan
26 10
RossyYan
|
2天前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序（头歌实践教学平台习题）【合集】
快速排序是一种高效的排序算法，基于分治策略。它的主要思想是通过选择一个基准元素（pivot），将数组划分成两部分。一部分的元素都小于等于基准元素，另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序，最终使整个数组有序。(第一行是元素个数，第二行是待排序的原始关键字数据。本关任务：实现快速排序算法。开始你的任务吧，祝你成功！
RossyYan
23 7
土木林森
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
72 1
java冯坚持
|
3月前
|
算法 搜索推荐 Java
数据结构与算法学习十三：基数排序，以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法，通过将数字按位数切割并分配到不同的桶中，以空间换时间的方式实现快速排序，但占用内存较大，不适合含有负数的数组。
java冯坚持
48 0
数据结构与算法学习十三：基数排序，以空间换时间的稳定式排序,速度很快。
ephemerals__
|
2月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
262 9
那年春天
|
2月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
42 1
RossyYan
|
2天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
112 75
RossyYan
|
2天前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
25 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
RossyYan
|
2天前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现链栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储整数，最大
RossyYan
27 9