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

算法给小码农八大排序 八奇计只为宝儿姐

2022-02-07 107
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
云原生大数据计算服务MaxCompute，500CU*H 100GB 3个月
云原生大数据计算服务 MaxCompute，5000CU*H 100GB 3个月
简介： 算法给小码农八大排序 八奇计只为宝儿姐

文章目录



八排 八奇迹

排序

排序的概念及其运用

排序的概念

==排序：==所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

 ==稳定性：==假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

==内部排序：==数据元素全部放在内存中的排序。

==外部排序：==数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

排序运用

来上京东

大学排名

常见的排序算法

常见排序算法的实现

插入排序

基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

但是数组肯定不是有序的，所以我们得先让数组有序

先把打印数组给剥离出来

// 打印数组
void PrintArray(int* a, int n) {
  assert(a);
  int i = 0;
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
}

插入排序

// 插入排序
void InsertSort(int* a, int n) {
  assert(a);
  int i = 0;
  for (i = 0; i < n - 1; i++) {
    int end = i;
    int x = a[end+1];
    while (end >= 0) {
      //要插入的数比顺序中的数小就准备挪位置
      if (a[end] > x) {
        a[end + 1] = a[end];
        end--;
      }
      else {
        //插入的数比顺序中的要大就跳出
        break;
      }
    }
    //跳出来两种情况
    //1.end == -1 的时候
    //2.break 的时候
    //把x给end前面一位
    a[end + 1] = x;
  }
}

插入排序的时间复杂度：O(N2)

最好：O(N) — 顺序有序 （接近有序）

最坏：O(N2) — 逆序

插入排序的空间复杂度：O(1)

希尔排序( 缩小增量排序 ) (反正希尔牛逼)

希尔排序是在优化直接插入排序，而且效果超级明显，为什么是优化呢，因为我们知道直接插入排序接近有序了就会非常快，那我就创造这样的有序，让他时间复杂度接近O(N)，我们知道排序的时间复杂度最好情况就是O(N)，而我们接近O(N)也是相当了不起了，基本是接近天花板了

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序步骤

1.分组预排序 ---- 数组接近有序

按gap分组，对分组值进行插入排序 分成gap组

2.直接插入排序 数组接近有序，直接插入的时间复杂度就是O(N)

单组多躺

多组插入

间距为gap多组预排实现的时间复杂度O(gap*(1+…+N/gap))

最好：O(N)

最好：O(N)

最坏：O(gap*(1+…+N/gap))

gap越大，预排越快，预排后越不接近有序

gap越小，预排越慢，预排后越接近有序

多组一锅炖（要是分组插麻烦我们也可以一锅炖）

多次预排序(gap > 1)+直接插入（gap == 1）

gap/2

gap/3

时间复杂度O(N1.3)记住就行，反正记住希尔很牛逼就行，希尔排序很快

测直接插入排序和希尔排序的性能（让你看看什么才叫希尔排序）

文章目录

堆

数据结构中的堆不同于操作系统中的堆（操作系统中的堆是用来存储动态内存的），数据结构中的堆是数据的存储方式。数据结构中的堆是完全二叉树

既然堆是完全二叉树的形式存储的那么就非常适合用数组的方式来表示

堆的概念及结构

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

大堆：树中一个树及子树中，任何一个父亲都大于等于孩子

小堆：树中一个树及子树中，任何一个父亲都小于等于孩子

堆的性质

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。**

堆的结构（这里实现大堆）

既然还是数组的结构的话就还是顺序表的处理方式，数组指针，size，capacity。虽然物理上我们是用顺序表的方式来表示，但是他实际上表示的数据是完全二叉树。

堆的结构体

typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;

堆初始化函数HeapInit

就是一个指向NULL的数组，size 和 capacity都为零

//堆初始化函数
void HeapInit(HP* hp)
{
  assert(hp);
  hp->a = NULL;
  hp->size = hp->capacity = 0;
}

堆销毁函数HeapDestroy

由于数组是动态开辟的，所以用完后需要销毁的，不然会内存泄漏

//堆销毁函数
void HeapDestroy(HP* hp)
{
  assert(hp);
  free(hp->a);
  hp->size = hp->capacity = 0;
}

堆打印函数HeapPrint

可以想象成一种快速调试，类似于单片机中的串口打印看数据收发情况

//堆打印函数
void HeapPrint(HP* hp)
{
  int i = 0;
  for (i = 0; i < hp->size; i++)
  {
    printf("%d ", hp->a[i]);
  }
  printf("\n");
}

向上调整函数AdjustUp

为了不影响数据的存储形式（大堆还得是大堆），插入数据就不能破坏大堆的形式，我们需要把堆插入函数中的数据调整给剥离出来

我们可以看到插入的这个数据对其他的节点并没有什么影响，有影响的只是这个节点到根这条路径上的节点，如何解决对这条路径的影响呢，我们可以形象的看到仅仅是在这条路径上进行向上调整

通过parent = （child-1）/2 找到父亲节点，与之进行比较，然后父亲小就交换位置（大堆），然后交换后就在找上面的父亲节点，直到找到父亲大于孩子，就不交换了

//向上调整函数
void AdjustUp(HPDataType* a, int child)
{
  assert(a);
  int parent = (child - 1) / 2;
  while (child>0)
  {
    if (a[parent] < a[child])//父亲小于孩子就交换（大堆）
    {
      a[parent] = a[parent] ^ a[child];
      a[child] = a[parent] ^ a[child];
      a[parent] = a[parent] ^ a[child];
      //交换好后重新称呼一下孩子与父亲
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

堆插入函数HeapPush

//堆插入函数（要保持原来形式，大堆还是大堆，小堆就还是小堆）
void HeapPush(HP* hp, HPDataType x)
{
  assert(hp);
  //判断扩容
  if (hp->size == hp->capacity)
  {
    //容量给新的容量
    int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
    //扩容
    HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
    //增容失败
    if (!tmp)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    //增容成功
    hp->a = tmp;
    hp->capacity = newcapacity;   
  }
  //放数据
  hp->a[hp->size] = x;
  hp->size++;
  //实现大堆
  //这个部分的向上调整其他地方也用的到就把他剥离出来
  AdjustUp(hp->a, hp->size - 1);//child下标
}

判断堆是否为空函数HeapErmpy

//判断堆是否为空函数
bool HeapErmpy(HP* hp)
{
  assert(hp);
  return hp->size == 0;
}

返回堆大小函数HeapSize

//返回堆大小函数
int HeapSize(HP* hp)
{
  assert(hp);
  return hp->size;
}

下面还会用到交换函数，上面也有那么我们不妨把他剥离出来封装一下，就不需要重复写了

交换函数Swap

//交换函数void Swap(HPDataType* px, HPDataType* py){  *px = *px ^ *py;  *py = *px ^ *py;  *px = *px ^ *py;}

向下调整函数AdjustDown

//向下调整函数void AdjustDown(HPDataType* a, int size, int parent){ assert(a);  //创建一个孩子变量，有两个孩子就在这个上加1就行 int child = parent * 2 + 1; while (child< size) {   //选大孩子    if (child + 1 < size && a[child] < a[child + 1])    {     child++;    }   //大的孩子还大于父亲就交换    if (a[child] > a[parent])   {     Swap(&a[child], &a[parent]);      parent = child;     child = parent * 2 + 1;   } }}

堆删除函数HeapPop

我们可以认为假想根和堆的最后一个元素交换后，把最后一个删除，然后再对堆进行操作，你会发现，我们没有破坏原来的整体结构

//堆删除函数（删除的是堆顶数据也就是取最值）
//还有不可能一直删的所以我们需要一个判空函数
void HeapPop(HP* hp)
{
  assert(hp);
  assert(!HeapErmpy(hp));
  //根和堆最后一个元素交换
  Swap(&hp->a[0],&hp->a[hp->size-1]);
  //把最后一个删除，就是我们想要删除的元素
  hp->size--;
  //向下调整
  AdjustDown(hp->a,hp->size,0);
}


文章目录

排序

常见的排序算法

常见排序算法的实现

选择排序 最慢排序（最好理解）所以搬血

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

直接选择排序

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素

若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

上面那个就是选择排序的本质，但是一次就选一个最大或者最小是不是有点浪费，我们一次同时选到最大最小，就是会比传统的选择排序快一倍

我们基本看到上面代码的缺陷就是我们第一个就是最大是时候，最大的就被换走了，而最小的就被换过来了，但是最大的下标还是标记首位置，把最小的换到后面，也就出现了最小的1在后面的现象

解决方法：既然你最大数的下标和begin重合，那最大数被换走的时候，maxi这个下标也要连带着走

实际上下面 才是我第一次写的代码，直接说下次我再也不写装逼的交换了

我来道bug恶心之处 看好了跳跳 5 ^ 5 == 0 这就是恶心之处，下次再也不装逼了

数据交换 剥离出来其他函数也会用到 我明明是简洁之人为了一时的高级而忘记了朴素罪过罪过

//数据交换
void Swap(int* pa, int* pb) {
  int tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}

选择排序

// 选择排序
void SelectSort(int* a, int n) {
  int begin = 0;
  int end = n - 1;
  while (begin < end){
    //单趟
    //最大数，最小数的下标
    int mini = begin;//这边假设是刚开始的下标
    int maxi = end;  //这边假设是末尾的下标
    int i = 0;
    for (i = begin; i <= end; i++) {
      if (a[i] < a[mini])
        mini = i;
      if (a[i] > a[maxi])
        maxi = i;
    }
    //最小的放前面
    Swap(&a[begin], &a[mini]);
    if (begin == maxi)
      //如果最大数就是begin位置的，那么交换的时候最大数连带着下标一起动
      maxi = mini;
    //最大的放后面
    Swap(&a[end], &a[maxi]);
    begin++;
    end--;
  }
}

时间复杂度是O(N2) 我们的优化不是质的优化，而是量的优化

最好：O(N2)

最坏：O(N2)

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是

通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

向下调整函数

//向下调整函数
void AdjustDown(int* a, int n, int parent)
{
  assert(a);
  //创建一个孩子变量，有两个孩子就在这个上加1就行
  int child = parent * 2 + 1;
#if HEAP
  while (child < n)
  {
    //选大孩子
    if (child + 1 < n && a[child] < a[child + 1])
    {
      child++;
    }
    //大的孩子还大于父亲就交换
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
#elif !HEAP
  while (child < n)
  {
    //选小孩子
    if (child + 1 < n && a[child] > a[child + 1])
    {
      child++;
    }
    //小的孩子还小于父亲就交换
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
#endif // HEAP  
}

堆排序代码

// 堆排序   我们之前讲过升序建大堆
void HeapSort(int* a, int n) {
  //建堆时间复杂度O(N)
  //建大堆
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--) {
    AdjustDown(a, n, i);
  }
  int end = n - 1;
  //堆排序时间复杂度O(N*logN)
  while (end>0){
    //交换 把最大的放到后面
    Swap(&a[0], &a[end]);
    //在向下调整
    AdjustDown(a,end,0);
    end--;
  }
}

堆排序时间复杂度O(N*logN)


测性能 让你看看什么叫堆

这里我们测性能就用release版本测吧 因为release版本是程序最优状态，每个排序都是最好状态，巅峰打巅峰

1000大小数组 一千

10000大小数组 一万

100000大小数组 十万

1000000大小数组 一百万

10000000大小数组 一千万 我们不带选择，插入玩太拉跨了，我们看看希尔，堆在超大数据面前谁性能更优

性能函数图


文章目录

排序

常见的排序算法

常见排序算法的实现

归并排序

基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and  Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。  归并排序核心步骤：

实际上归并我们不是第一次接触，之前我们也是接触过的，比如合并两个有序数组这个就是归并思想

但是我们上面的题目是左区间有序，右区间也有序。我们正常题目肯定不会直接给你有序。这时候再深一点，你不是没有序吗，那我们再分，分到你无法再分，也就是只有一个了，你能说一个没有序吗，肯定不行，所以我们继续分治。

递归写法

看上面的GIF也知道第一反应是递归

通过调试看一下现象

归并顺序

归并排序递归子函数

// 归并排序递归子函数
void _MergeSort(int* a, int left, int right, int* tmp){
  //左大于右说明是空数组，空数组就跳
  //左等于右就是我们要的单体有序
  if (left >= right)
    return;
  //防溢出写法
  int mid = left + (right - left) / 2;
  _MergeSort(a, left, mid, tmp);
  _MergeSort(a, mid+1,right, tmp);
  //
  int begin1 = left;
  int end1 = mid;
  int begin2 = mid + 1;
  int end2 = right;
  int i = left;
  //跑空一组就直接跳
  while (begin1<=end1 && begin2<=end2){
    if (a[begin1] < a[begin2]) {
      tmp[i++] = a[begin1++];
    }     
    else {
      tmp[i++] = a[begin2++];
    }
  }
  while (begin1 <= end1) {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2) {
    tmp[i++] = a[begin2++];
  }
  //把tmp数组拷贝回到原来的数组中
  i = left;
  while (i<=right)
  {
    a[i] = tmp[i];
    i++;
  }
}

归并排序递归实现

// 归并排序递归实现
void MergeSort(int* a, int n) {
  assert(a);
  //首先创建一个临时数组
  int* tmp = (int*)malloc(sizeof(int) * n);
  //空就直接错
  assert(tmp);
  //子函数
  _MergeSort(a, 0, n - 1, tmp);
  //不用了就free掉
  free(tmp);
  //然后置空
  tmp = NULL;
}

非递归写法

2n个元素的数组

我们看到上面好像没啥问题，那是用为数组元素个数真的太有好了，一直没有落单的元素，好的不真实

随便几个元素的数组
修正下标

越界情况讨论

但是出现另一种恶心情况 重复拷贝

所以接下来我们需要解决index问题

我们修正到n-1，同样也可以把数组修不存在，让他不进下面的循环也就可以不会进行归并

归并排序非递归实现 修正下标

// 归并排序非递归实现
void MergeSortNonR(int* a, int n) {
  assert(a);
  //首先创建一个临时数组
  int* tmp = (int*)malloc(sizeof(int) * n);
  //空就直接错
  assert(tmp);
  int gap = 1;
  int i = 0;
  while (gap<n){
    for (i = 0; i < n; i += 2 * gap){
      //单组需要排序的区间
      //[i,i+gap-1]  [i+gap,i+2*gap-1]
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i+gap, end2 = i + 2*gap - 1;
      //适用任何元素个数的核心部分
      //end1出界，[begin2,end2]不存在
      if (end1 >= n) {
        end1 = n - 1;
      }
      //[begin2,end2]不存在
      if (begin2 >= n) {
        begin2 = n ;
        end2 = n - 1;
      }
      //end2出界
      if (end2 >= n) {
        end2 = n - 1;
      }
      //printf("[%d,%d],[%d,%d]",begin1,end1,begin2,end2);
      重复拷贝基本是我们修正到同一个位置的原因
      我们条件断点一下
      //if (begin1 == end1 && end1 == begin2 && begin2 == end2 && end2 == n-1)
      //{
      //  //随便一个代码来承接断点，一句费代码
      //  int a = 0;
      //}
      //tmp需要一个索引
      int index = i;
      while (begin1 <= end1 && begin2 <= end2){
        if (a[begin1] > a[begin2]) {
          tmp[index++] = a[begin2++];
        }
        else{
          tmp[index++] = a[begin1++];
        }
      }     
      //肯定还有一个没跑完
      while (begin1 <= end1){
        tmp[index++] = a[begin1++];
      }
      while (begin2 <= end2) {
        tmp[index++] = a[begin2++];
      }   
      //printf("       %d", index);
    }
    //printf("\n");
    //一行归并完了再考回去
    for (i = 0; i < n; i++) {
      a[i] = tmp[i];
    }
    gap *= 2;
  } 
  //不用了就free掉
  free(tmp);
  //然后置空
  tmp = NULL;
}
归一部分拷一部分

我们也可以像递归那样归一半分拷贝一部分，就不需要修正了，因为修正要考虑很多边界情况，有点繁琐

归并排序非递归实现 归一部分拷一部分

// 归并排序非递归实现
void MergeSortNonR(int* a, int n) {
  assert(a);
  //首先创建一个临时数组
  int* tmp = (int*)malloc(sizeof(int) * n);
  //空就直接错
  assert(tmp);
  int gap = 1;
  int i = 0;
  while (gap<n){
    for (i = 0; i < n; i += 2 * gap){
      //单组需要排序的区间
      //[i,i+gap-1]  [i+gap,i+2*gap-1]
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i+gap, end2 = i + 2*gap - 1;
      适用任何元素个数的核心部分
      end1出界，[begin2,end2]不存在
      //if (end1 >= n) {
      //  end1 = n - 1;
      //}
      [begin2,end2]不存在
      //if (begin2 >= n) {
      //  begin2 = n ;
      //  end2 = n - 1;
      //}
      end2出界
      //if (end2 >= n) {
      //  end2 = n - 1;
      //}
      //适用任何元素个数的核心部分
      //end1出界，[begin2,end2]不存在 都不需要归并
      if (end1 >= n || begin2 >= n) {
        //直接跳，因为是在原数组操作的不需要担心最后一个没考进去
        break;
      }
      //end2出界  需要归并  就修正
      if (end2 >= n) {
        end2 = n - 1;
      }
      //printf("[%d,%d],[%d,%d]",begin1,end1,begin2,end2);
      重复拷贝基本是我们修正到同一个位置的原因
      我们条件断点一下
      //if (begin1 == end1 && end1 == begin2 && begin2 == end2 && end2 == n-1)
      //{
      //  //随便一个代码来承接断点，一句费代码
      //  int a = 0;
      //}
      //tmp需要一个索引
      int index = i;
      while (begin1 <= end1 && begin2 <= end2){
        if (a[begin1] > a[begin2]) {
          tmp[index++] = a[begin2++];
        }
        else{
          tmp[index++] = a[begin1++];
        }
      }
      //肯定还有一个没跑完
      while (begin1 <= end1){
        tmp[index++] = a[begin1++];
      }
      while (begin2 <= end2) {
        tmp[index++] = a[begin2++];
      }   
      //归一部分拷贝一部分
      int j = 0;
      for (j = i; j <= end2; j++) {
        a[j] = tmp[j];
      }
      //printf("       %d", index);
    }
    //printf("\n");
    一行归并完了再考回去
    //for (i = 0; i < n; i++) {
    //  a[i] = tmp[i];
    //}
    gap *= 2;
  } 
  //不用了就free掉
  free(tmp);
  //然后置空
  tmp = NULL;
}

归并排序的特性总结

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

时间复杂度

时间复杂度:O(N*logN)

归并排序方法就是把一组n个数的序列，折半分为两个序列，然后再将这两个序列再分，一直分下去，直到分为n个长度为1的序列。然后两两按大小归并。如此反复，直到最后形成包含n个数的一个数组。

归并排序总时间=分解时间+子序列排好序时间+合并时间

无论每个序列有多少数都是折中分解，所以分解时间是个常数，可以忽略不计。

则：归并排序总时间=子序列排好序时间+合并时间

测性能

1000 一千

10000 一万 先抛弃选择和冒泡

100000 十万 再抛弃直接插入

1000000 一百万

10000000 一千万


文章目录

排序

常见的排序算法 扩展

计数排序 不进行数据的比较，而是统计数据出现的次数

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

网络异常，图片无法展示
|

我们可以发现是不是很快，自我感觉一下，没错实际上的确是很快的，时间复杂度是高效到==O(N)==级别的。计数的本质是哈希，所谓的映射

这也会面临一个很现实的问题，就是前面没有时候数，后面1000的位置反而有数，咋处理

eg.1000 1100 1200 1300 1200 1400 1000 1500 1300 1200

我们也可以发现计数排序比较适合大小范围集中的数组

计数排序

// 计数排序
void CountSort(int* a, int n) {
  assert(a);
  int max = a[0], min = a[0];
  int i = 0;
  for (i = 0; i < n; i++) {
    if (a[i] > max)
      max = a[i];
    if (a[i] < min)
      min = a[i];
  }
  //范围
  int range = max - min + 1;
  //开辟计数数组
  int* count = (int*)malloc(sizeof(int) * range); 
  //没开辟成功直接错
  assert(count);
  //数组全部初始化为零
  memset(count, 0, sizeof(int) * range);
  //统计次数
  for (i = 0; i < n; i++) {
    //相对映射加加
    count[a[i] - min]++;
  }
  //通过计数数组的次数对原数组进行排序
  int j = 0;
  for (i = 0; i < range; i++) {
    while (count[i]--)
      //相对映射要回到原数组的数据+min
      a[j++] = i+min;
  }
  free(count);
  count = NULL;
}

计数排序的特性总结

  1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
  2. 时间复杂度：O(MAX(N,范围))
  3. 空间复杂度：O(范围)

测性能

1000 一千

10000 一万

100000 十万

1000000 一百万

10000000 一千万

排序总结

稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j],且r[i] 在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是最稳定的，否则称为不稳定的

再简单一点：数组中相同的值，在排序以后相对位置是否变化

可能会变的，就是不稳定

能保持不变，就是稳定


八大排序总结

排序方法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
插入排序 O(N^2) O(N^2) O(N) O(1) 稳定
希尔排序 O(N^1.3) O(N^2) O(N) O(1) 不稳定
选择排序 O(N^2) O(N^2) O(N^2) O(1) 不稳定
堆排序 O(n*logN) O(n*logN) O(n*logN) O(1) 不稳定
冒泡排序 O(N^2) O(N^2) O(N) O(1) 稳定
快速排序 O(n*logN) O(N^2) O(n*logN) 最好O(logN)，最坏O(N) 不稳定
归并排序 O(n*logN) O(n*logN) O(n*logN) O(N) 稳定
计数排序 O(MAX(N,range)) O(MAX(N,range)) O(N) O(range) 不稳定


代码

Sort.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#define HEAP        1
// 排序实现的接口
// 打印数组
extern void PrintArray(int* a, int n);
// 插入排序
extern void InsertSort(int* a, int n);
// 希尔排序
extern void ShellSort(int* a, int n);
//数据交换
extern void Swap(int* pa, int* pb);
// 选择排序
extern void SelectSort(int* a, int n);
//向下调整
extern void AdjustDwon(int* a, int n, int parent);
// 堆排序
extern void HeapSort(int* a, int n);
// 冒泡排序
extern void BubbleSort(int* a, int n);
// 快速排序递归实现
// 快速排序hoare版本
extern int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
extern int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
extern int PartSort3(int* a, int left, int right);
extern void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
extern void QuickSortNonR(int* a, int left, int right);
// 归并排序递归实现
extern void MergeSort(int* a, int n);
// 归并排序非递归实现
extern void MergeSortNonR(int* a, int n);
// 计数排序
extern void CountSort(int* a, int n);

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"
#include"Stack.h"
// 打印数组
void PrintArray(int* a, int n) {
  assert(a);
  int i = 0;
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
}
// 插入排序
void InsertSort(int* a, int n) {
  assert(a);
  int i = 0;
  for (i = 0; i < n - 1; i++) {
    int end = i;
    int x = a[end+1];
    while (end >= 0) {
      //要插入的数比顺序中的数小就准备挪位置
      if (a[end] > x) {
        a[end + 1] = a[end];
        end--;
      }
      else {
        //插入的数比顺序中的要大就跳出
        break;
      }
    }
    //跳出来两种情况
    //1.end == -1 的时候
    //2.break 的时候
    //把x给end前面一位
    a[end + 1] = x;
  }
}
// 希尔排序
void ShellSort(int* a, int n) {
  //分组
  int gap = n;
  //多次预排序（gap>1）+ 直接插入（gap == 1）
  while (gap>1){
    //gap /= 2;
    //除以三我们知道不一定会过1，所以我们+1让他有一个必过1的条件
    gap = gap / 3 + 1;
    //单组多躺
    int i = 0;
    for (i = 0; i < n - gap; i++) {
    int end = i;
    int x = a[end + gap];
    while (end >= 0) {
      if (a[end] > x) {
        a[end + gap] = a[end];
        //步长是gap
        end -= gap;
      }
      else {
        break;
      }
    }
    a[end + gap] = x;
  }
  } 
}
//数据交换
void Swap(int* pa, int* pb) {
  int tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}
// 选择排序
void SelectSort(int* a, int n) {
  int begin = 0;
  int end = n - 1;
  while (begin < end){
    //单趟
    //最大数，最小数的下标
    int mini = begin;//这边假设是刚开始的下标
    int maxi = end;  //这边假设是末尾的下标
    int i = 0;
    for (i = begin; i <= end; i++) {
      if (a[i] < a[mini])
        mini = i;
      if (a[i] > a[maxi])
        maxi = i;
    }
    //最小的放前面
    Swap(&a[begin], &a[mini]);
    if (begin == maxi)
      //如果最大数就是begin位置的，那么交换的时候最大数连带着下标一起动
      maxi = mini;
    //最大的放后面
    Swap(&a[end], &a[maxi]);
    begin++;
    end--;
  }
}
//向下调整函数
void AdjustDown(int* a, int n, int parent)
{
  assert(a);
  //创建一个孩子变量，有两个孩子就在这个上加1就行
  int child = parent * 2 + 1;
#if HEAP
  while (child < n)
  {
    //选大孩子
    if (child + 1 < n && a[child] < a[child + 1])
    {
      child++;
    }
    //大的孩子还大于父亲就交换
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
#elif !HEAP
  while (child < n)
  {
    //选小孩子
    if (child + 1 < n && a[child] > a[child + 1])
    {
      child++;
    }
    //小的孩子还小于父亲就交换
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
#endif // HEAP  
}
// 堆排序   我们之前讲过升序建大堆
void HeapSort(int* a, int n) {
  //建堆时间复杂度O(N)
  //建大堆
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--) {
    AdjustDown(a, n, i);
  }
  int end = n - 1;
  //堆排序时间复杂度O(N*logN)
  while (end>0){
    //交换 把最大的放到后面
    Swap(&a[0], &a[end]);
    //在向下调整
    AdjustDown(a,end,0);
    end--;
  }
}
// 冒泡排序
void BubbleSort(int* a, int n) {
  //多躺
  int j = 0;  
  for (j = 0; j < n - 1; j++) { 
    //交换标记变量
    int flag = 0;
    //单趟
    int i = 0;
    for (i = 0; i < n - 1-j; i++) {     
      if (a[i] > a[i + 1]) {
        //交换标记改变
        flag = 1;
        Swap(&a[i], &a[i + 1]);
      }
    }
    //标记还是0就跳出
    if (!flag)
      break;
  }
}
//三数取中
int GetMinIndex(int* a, int left, int right) {
  //这样可以防止 int 溢出
  int mid = left + (right - left) / 2;
  if (a[left] < a[mid]) {
    if (a[mid] < a[right])
      return mid;
    else if (a[left] > a[right])
      return left;
    else
      return right;
  }
  else //a[left] >= a[mid]
  {
    if (a[mid] > a[right])
      return mid;
    else if (a[left] < a[right])
      return left;
    else
      return right;
  }
}
// 快速排序hoare版本 单趟排序
//最左边做key  [left,right]  我们这里给区间
int PartSort1(int* a, int left, int right) {
  //三数取中
  int mini = GetMinIndex(a, left, right);
  //把中间的数放到最左边，交换即可
  Swap(&a[mini], &a[left]);
  //还是最左边为keyi
  int keyi = left;
  //左右相遇就停止
  while (left < right)
  {
    //最左边为key，那么最右边就先动
    //找小于key的
    while (left < right && a[right] >= a[keyi]) {
      right--;
    }
    //然后再动右边的
    //找大于key的
    while (left < right && a[left] <= a[keyi]) {
      left++;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[keyi], &a[right]);
  //返回正确位置后的keyi
  return left;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right) {
  assert(a);
  //三数取中
  int mini = GetMinIndex(a, left, right);
  //把中间的数放到最左边，交换即可
  Swap(&a[mini], &a[left]);
  //先把Key存下来
  int Key = a[left];
  //挖坑
  int pit = left;
  while (left<right){
    //右边找小
    while (left < right && a[right] >= Key) {
      right--;
    }
    //找到后把数据扔到坑里面去
    Swap(&a[right],&a[pit]);
    //自己就变成新的坑
    pit = right;
    //左边找大
    while (left < right && a[left] <= Key) {
      left++;
    }
    //找到后把数据扔到坑里面去
    Swap(&a[left], &a[pit]);
    //自己就变成新的坑
    pit = left;
  }
  //出来后把Key放到坑里面去
  a[pit] = Key;
  return pit;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right) {
  assert(a);  
  //三数取中
  int mini = GetMinIndex(a, left, right);
  //把中间的数放到最左边，交换即可
  Swap(&a[mini], &a[left]);
  //把keyi记下来
  int keyi = left;
  int prev = left;
  int cur = prev + 1;
  while (cur <= right){
    比Key小就跳出
    //while (cur <= right && a[cur] >= a[keyi]) {
    //  cur++;
    //}
    //if (cur <= right) {
    //  //跳出来prev++
    //  prev++;
    //  //交换
    //  Swap(&a[prev], &a[cur]);
    //  //交换完后cur也++
    //  cur++;
    //}   
    if(a[cur] < a[keyi])
      Swap(&a[prev++], &a[cur]);
    cur++;
  }
  //跳出来说明交换a[prev]和Key
  Swap(&a[prev],&a[keyi]);
  return prev;
}
// 快速排序  小区间优化
void QuickSort(int* a, int left, int right) {
  if (left >= right)
    return;
  if (right - left + 1 < 10)//10以内的数插入
  {
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    int keyi = PartSort3(a, left, right);
    //[left,keyi-1] keyi [keyi+1,right]
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
  } 
}
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right) {
  //建栈
  ST st;
  //初始化栈
  StackInit(&st);
  //left进栈
  StackPush(&st, left);
  //right进栈
  StackPush(&st, right);
  //空栈跳出 
  while (!StackEmpty(&st))
  {
    //先取尾
    int end = StackTop(&st);
    //pop掉
    StackPop(&st);
    //再取头
    int start = StackTop(&st);
    //再pop掉
    StackPop(&st);
    //然后单趟排序找到keyi
    int keyi = PartSort3(a,start,end);
    //[start,keyi-1] keyi [keyi+1,end]
    if (keyi + 1 < end)//表示分割开来的区间大于1
    {
      //因为我们先取尾，所以问先入头
      StackPush(&st, keyi + 1);
      //再入尾
      StackPush(&st, end);
    }
    if (keyi - 1 > start)//表示分割开来的区间大于1
    {
      //因为我们先取尾，所以问先入头
      StackPush(&st, start);
      //再入尾
      StackPush(&st, keyi - 1);
    }
  }
  //与初始化联动的栈销毁
  StackDestroy(&st);
}
// 归并排序递归子函数
void _MergeSort(int* a, int left, int right, int* tmp){
  //左大于右说明是空数组，空数组就跳
  //左等于右就是我们要的单体有序
  if (left >= right)
    return;
  //防溢出写法
  int mid = left + (right - left) / 2;
  _MergeSort(a, left, mid, tmp);
  _MergeSort(a, mid+1,right, tmp);
  //
  int begin1 = left;
  int end1 = mid;
  int begin2 = mid + 1;
  int end2 = right;
  int i = left;
  //跑空一组就直接跳
  while (begin1<=end1 && begin2<=end2){
    if (a[begin1] < a[begin2]) {
      tmp[i++] = a[begin1++];
    }     
    else {
      tmp[i++] = a[begin2++];
    }
  }
  while (begin1 <= end1) {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2) {
    tmp[i++] = a[begin2++];
  }
  //把tmp数组拷贝回到原来的数组中
  i = left;
  while (i<=right)
  {
    a[i] = tmp[i];
    i++;
  }
}
// 归并排序递归实现
void MergeSort(int* a, int n) {
  assert(a);
  //首先创建一个临时数组
  int* tmp = (int*)malloc(sizeof(int) * n);
  //空就直接错
  assert(tmp);
  //子函数
  _MergeSort(a, 0, n - 1, tmp);
  //不用了就free掉
  free(tmp);
  //然后置空
  tmp = NULL;
}
// 归并排序非递归实现
void MergeSortNonR(int* a, int n) {
  assert(a);
  //首先创建一个临时数组
  int* tmp = (int*)malloc(sizeof(int) * n);
  //空就直接错
  assert(tmp);
  int gap = 1;
  int i = 0;
  while (gap<n){
    for (i = 0; i < n; i += 2 * gap){
      //单组需要排序的区间
      //[i,i+gap-1]  [i+gap,i+2*gap-1]
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i+gap, end2 = i + 2*gap - 1;
      适用任何元素个数的核心部分
      end1出界，[begin2,end2]不存在
      //if (end1 >= n) {
      //  end1 = n - 1;
      //}
      [begin2,end2]不存在
      //if (begin2 >= n) {
      //  begin2 = n ;
      //  end2 = n - 1;
      //}
      end2出界
      //if (end2 >= n) {
      //  end2 = n - 1;
      //}
      //适用任何元素个数的核心部分
      //end1出界，[begin2,end2]不存在 都不需要归并
      if (end1 >= n || begin2 >= n) {
        //直接跳，因为是在原数组操作的不需要担心最后一个没考进去
        break;
      }
      //end2出界  需要归并  就修正
      if (end2 >= n) {
        end2 = n - 1;
      }
      //printf("[%d,%d],[%d,%d]",begin1,end1,begin2,end2);
      重复拷贝基本是我们修正到同一个位置的原因
      我们条件断点一下
      //if (begin1 == end1 && end1 == begin2 && begin2 == end2 && end2 == n-1)
      //{
      //  //随便一个代码来承接断点，一句费代码
      //  int a = 0;
      //}
      //tmp需要一个索引
      int index = i;
      while (begin1 <= end1 && begin2 <= end2){
        if (a[begin1] > a[begin2]) {
          tmp[index++] = a[begin2++];
        }
        else{
          tmp[index++] = a[begin1++];
        }
      }
      //肯定还有一个没跑完
      while (begin1 <= end1){
        tmp[index++] = a[begin1++];
      }
      while (begin2 <= end2) {
        tmp[index++] = a[begin2++];
      }   
      //归一部分拷贝一部分
      int j = 0;
      for (j = i; j <= end2; j++) {
        a[j] = tmp[j];
      }
      //printf("       %d", index);
    }
    //printf("\n");
    一行归并完了再考回去
    //for (i = 0; i < n; i++) {
    //  a[i] = tmp[i];
    //}
    gap *= 2;
  } 
  //不用了就free掉
  free(tmp);
  //然后置空
  tmp = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"
// 测试排序的性能对比
void TestOP()
{
  //设置随机起点
  srand(time(NULL));
  //将要创建的数组大小
  const int N = 10000000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  int* a7 = (int*)malloc(sizeof(int) * N);
  int* a8 = (int*)malloc(sizeof(int) * N);
  int* a9 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++i)
  {
    //保证两个数组是一样的
    a1[i] = rand();
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
    a7[i] = a1[i];
    a8[i] = a1[i];
    a9[i] = a1[i];
  }
  int begin1 = clock();//开始时间
  //InsertSort(a1, N);
  int end1 = clock();  //结束时间
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin3 = clock();
  //SelectSort(a3, N);
  int end3 = clock();
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
  int begin5 = clock();
  //BubbleSort(a5, N);
  int end5 = clock();
  int begin6 = clock();
  QuickSort(a6, 0, N - 1);
  int end6 = clock();
  int begin7 = clock();
  QuickSortNonR(a7, 0, N - 1);
  int end7 = clock();
  int begin8 = clock();
  MergeSort(a8, N);
  int end8 = clock();
  int begin9 = clock();
  MergeSort(a9, N);
  int end9 = clock();
  printf("InsertSort:%d\n", end1 - begin1);//结束时间减去开始时间 
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("BubbleSort:%d\n", end5 - begin5);
  printf("QuickSort:%d\n", end6 - begin6);
  printf("QuickSortNonR:%d\n", end7 - begin7);
  printf("MergeSort:%d\n", end8 - begin8);
  printf("MergeSortNonR:%d\n", end9 - begin9);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
  free(a7);
  free(a8);
  free(a9);
}
//测试插入排序
void TestInsertSort() {
  int a[] = { 1,5,3,7,0,9 };
  InsertSort(a, sizeof(a) / sizeof(a[0]));  
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试希尔排序
void TestShellSort() {
  int a[] = { 9,1,2,5,7,4,8,6,3,5 };
  ShellSort(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试选择排序
void TestSelectSort() {
  int a[] = { 9,1,2,5,7,4,8,6,3,5 };
  SelectSort(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试堆排序
void TestHeapSort() {
  int a[] = { 9,1,2,5,7,4,8,6,3,5 };
  HeapSort(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试冒泡排序
void TestBubbleSort() {
  int a[] = { 9,1,2,5,7,4,8,6,3,5 };
  BubbleSort(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试单趟排序
void TestPartSort1() {
  int a[] = { 5,5,5,5,5,5,5,5,5,5 };
  PartSort1(a,0 ,sizeof(a) / sizeof(a[0])-1);
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试快速排序
void TestQuickSort() {
  int a[] = { 9,1,2,5,7,4,8,6,3,5 };
  QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试快速排序--非递归
void TestQuickSortNonR() {
  int a[] = { 9,1,2,5,7,4,8,6,3,5 };
  QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0]) - 1);
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试归并排序--递归
void TestMergeSort() {
  int a[] = { 10,6,7,1,3,9,4,2 };
  MergeSort(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试归并排序--非递归
void TestMergeSortNonR() {
  int a[] = {  10,6,7,1,3,9,4,2,5 };
  MergeSortNonR(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
int main(){
  //TestInsertSort();
  //TestShellSort();
  //TestSelectSort();
  //TestHeapSort();
  //TestBubbleSort();
  //TestPartSort1();
  //TestQuickSort();
  //TestQuickSortNonR();
  //TestMergeSort();
  //TestMergeSortNonR();
  TestOP();
  return 0;
}


文章标签：
云原生大数据计算服务 MaxCompute
搜索推荐
算法
存储
关键词：
算法排序
算法小码农
算法码农
相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析，通过分析能得到用户群体年龄分布，性别分布，地理位置分布，以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品，是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法，从场景到实践，体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库，助力开发者学习了解先进的技术栈，并能在实际业务中敏捷的进行大数据分析，赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景，可应用MaxCompute实现数仓搭建，快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理，需要搭建数据仓库？学它！ 没有足够人员和经验来运维大数据平台，不想自建IDC买机器，需要免运维的大数据平台？会SQL就等于会大数据？学它！ 想知道大数据用得对不对，想用更少的钱得到持续演进的数仓能力？获得极致弹性的计算资源和更好的性能，以及持续保护数据安全的生产环境？学它！ 想要获得灵活的分析能力，快速洞察数据规律特征？想要兼得数据湖的灵活性与数据仓库的成长性？学它！ 出品人：阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
小码农vv
目录
相关文章
HEX9CF
|
6月前
|
算法 C++
【洛谷 P1223】排队接水（贪心算法+结构体排序）
该问题要求安排$n$个人的排队顺序以最小化平均等待时间。每个人接水需时$T_i$，解决方案是让接水时间短的人优先。给定$n\leq1000$和$t_i\leq10^6$，代码示例使用C++实现，通过排序使时间从小到大排列，然后计算平均等待时间。样例输入为10个人的时间数组，输出为优化后的排队顺序及平均等待时间（291.90）。
HEX9CF
62 0
睡觉待开机
|
4月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
睡觉待开机
68 0
ephemerals__
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
95 8
ephemerals__
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
109 7
糜终
|
2月前
|
搜索推荐 Shell
解析排序算法：十大排序方法的工作原理与性能比较
解析排序算法：十大排序方法的工作原理与性能比较
糜终
73 9
java冯坚持
|
2月前
|
算法 搜索推荐 Java
数据结构与算法学习十三：基数排序，以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法，通过将数字按位数切割并分配到不同的桶中，以空间换时间的方式实现快速排序，但占用内存较大，不适合含有负数的数组。
java冯坚持
38 0
数据结构与算法学习十三：基数排序，以空间换时间的稳定式排序,速度很快。
Codelinghu
|
2月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
Codelinghu
34 0
龙大吉
|
2月前
|
存储 算法 搜索推荐
算法进阶之路：Python 归并排序深度剖析，让数据排序变得艺术起来！
算法进阶之路：Python 归并排序深度剖析，让数据排序变得艺术起来！
龙大吉
79 0
b3c447iaqrtq2
|
4月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例，展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中，实现算法的解耦和复用。
b3c447iaqrtq2
52 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法
软件求生
|
4月前
|
算法 搜索推荐 Java
算法实战：手写归并排序，让复杂排序变简单！
归并排序是一种基于“分治法”的经典算法，通过递归分割和合并数组，实现O(n log n)的高效排序。本文将通过Java手写代码，详细讲解归并排序的原理及实现，帮助你快速掌握这一实用算法。
软件求生
46 0

热门文章

最新文章

  • 1
    领域最全 | 计算机视觉算法在路面坑洼检测中的应用综述(基于2D图像/3D LiDAR/深度学习)（下）
  • 2
    DL之ANN/DNN： 人工神经网络ANN/DNN深度神经网络算法的简介、应用、经典案例之详细攻略
  • 3
    iOS 算法之排序、查找、递归
  • 4
    openssl中算法的组织方式
  • 5
    智能解决装箱问题：使用优化算法实现高效包装
  • 6
    指针难，算法难，难住了谁
  • 7
    多视图立体视觉: CVPR 2019 与 AAAI 2020 上的ACMH、ACMM及ACMP算法介绍
  • 8
    Linux内核中的有关Page的算法
  • 9
    OpenCV 1 图像分割--分水岭算法代码
  • 10
    缓存、缓存算法(转)
  • 1
    BASE64的算法说明
    68
  • 2
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    114
  • 3
    理解并应用机器学习算法：决策树
    145
  • 4
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    412
  • 5
    【机器学习】为什么K-means算法使用欧式距离度量？
    396
  • 6
    【机器学习】描述K-means算法的步骤
    153
  • 7
    【机器学习】K-means和KNN算法有什么区别？
    643
  • 8
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    54
  • 9
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    58
  • 10
    图搜索算法详解
    142

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 重温童年的“五子棋”，赢取专属阿里云Serverless证书
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks