鸽巢排序Pigeonhole Sort----(排序算法八)

男娘i 2022-09-17 14:16 107阅读 0赞

# 1.算法原理 #

鸽巢排序是对桶排序算法的改进，只是桶中装对应下标放元素出现的次数

待排序数组：a\[14\] =\{ 6, 6, 2, 2, 2, 4, 1, 1, 1, 5, 5, 5, 5, 9 \};

桶中: bucket\[10\]=0 3 3 0 1 4 2 0 0 1

1出次3次，所以bucket\[1\]=3

2出次3次，所以bucket\[2\]=3

4出次1次，所以bucket\[4\]=1

5出次4次，所以bucket\[5\]=4

6出次2次，所以bucket\[6\]=2

9出次1次，所以bucket\[9\]=1

# 2.代码实现 #

#include <stdio.h>
    
    //printArray打印出数组
    void printArray(int a[],int size){  
     //   printf("数组为：[%d] ",a[0]);  
        for (int i=0;i<size;i++)  
        {  
            printf(" %x ",a[i]);  
        }  
        printf("\n");  
    }
    
    
    void main()
    {
       int  a[14] ={ 6, 6, 2, 2, 2, 4, 1, 1, 1, 5, 5, 5, 5, 9 };
       int  len=14;
        //分配空桶
       int  bucket[10]={0} ;
       printf("排序前：");
       printArray(a,len);
    	//直接以每个待排数字为索引,将自己的值赋值给当前桶
       for (int i = 0; i < len; i++) {
              bucket[a[i]]++;
        }
       printf("桶中:");
       printArray(bucket,10);
    	//跳过值为0的空桶,顺序输出即可
    	int temp=0;
    	for (int j = 0; j < 10; j++){
    		while(bucket[j]-->0)
    			a[temp++]=j;
         }
    	printf("排序后：");
    	printArray(a,len);
    	
    }

# 3.排序结果 #

排序前： 6  6  2  2  2  4  1  1  1  5  5  5  5  9
    桶中: 0  3  3  0  1  4  2  0  0  1
    排序后： 1  1  1  2  2  2  4  5  5  5  5  6  6  9

发表评论取消回复

表情：

评论列表（有 0 条评论，107人围观）

还没有评论，来说两句吧...

相关阅读

相关 Arrays.sort排序算法

ava默认的排序算法及思路 List.sort() 还是 Collections.sort底层的排序都是调用了Arrays.sort()方法 Arrays.sort...

一时失言乱红尘/ 2024年04月18日 19:52/ 0 赞/ 52 阅读

相关鸽巢排序Pigeonhole Sort----(排序算法八)

1.算法原理鸽巢排序是对桶排序算法的改进，只是桶中装对应下标放元素出现的次数待排序数组：a\[14\] =\{ 6, 6, 2, 2, 2, 4, 1, 1, 1,

男娘i/ 2022年09月17日 14:16/ 0 赞/ 108 阅读

相关 go实现鸽巢排序算法

前面我们讲解了什么是[鸽巢排序][Link 1]，现在我们看一下代码，看看使用go如何实现 package main import "fmt"

素颜马尾好姑娘i/ 2022年05月14日 13:12/ 0 赞/ 147 阅读

相关 java实现鸽巢排序

前面我们讲解了什么是[鸽巢排序][Link 1]，现在我们看一下代码，看看使用java如何实现 package ttt; public class

亦凉/ 2022年05月14日 13:12/ 0 赞/ 132 阅读

相关 python实现鸽巢排序

前面我们讲解了什么是[鸽巢排序][Link 1]，现在我们看一下代码，看看使用python如何实现 !/usr/bin/python -- coding:

水深无声/ 2022年05月14日 13:12/ 0 赞/ 155 阅读

相关鸽巢排序讲解

鸽巢排序是[桶排序][Link 1]的一种，反正是变着花样玩，顾名思义，就是一排鸽巢，看里面有几个鸽巢，然后遍历这些鸽巢，打印出来就好，排序之前得先知道区间和最大值我们通过

墨蓝/ 2022年05月14日 13:11/ 0 赞/ 375 阅读

相关排序算法八--基数排序

基数排序(radix sort)是一种特殊的桶排序（bucket sort），相对于常见的比较排序，基数排序是一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖

Love The Way You Lie/ 2022年05月10日 14:58/ 0 赞/ 227 阅读

相关排序算法—八大排序

八大排序算法 1.冒泡排序冒泡排序是一种交换排序, 就是两两比较待排序的元素, 若次序不满足要求则交换, 知道整个数组有序基本思想 : 每次找到最大或最小值,

系统管理员/ 2021年11月08日 21:32/ 0 赞/ 411 阅读

相关排序算法5：归并排序（Merge sort）

归并排序（Merge sort）归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个

今天药忘吃喽~/ 2021年09月28日 22:18/ 0 赞/ 328 阅读

相关排序算法-2、选择排序（Selection Sort）

排序算法-2、选择排序（Selection Sort）选择排序选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中

今天药忘吃喽~/ 2021年09月28日 09:24/ 0 赞/ 295 阅读