C语言实现桶排序的方法示例

本文实例讲述了C语言实现桶排序的方法。分享给大家供大家参考，具体如下：

一、定义

假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。

二、性能

对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

快排的时间复杂度为n*log2(n)

当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

桶排序是稳定的

三、实现

/*==============================
8 name:bucket sort
--------------------------------
time complexity:
average
O(n+nlogn-nlogm)
--------------------------------
space complexity:
O(n)
--------------------------------
stability:
unstable
==============================*/
//suppose: 0<data[i]<100
//we should design the project function based on the data distribution
void bucket_sort(std::vector<int> &a)
{
  std::vector<std::vector<int>> bucket;
  bucket.resize(10);
  std::vector<int>::iterator it=a.begin();
  while(it!=a.end())
  {
    int idx=*it/10;
    bucket[idx].push_back(*it);
    it++;
  }
  std::vector<std::vector<int>>::iterator it1=bucket.begin();
  while(it1!=bucket.end())
  {
    simple_sort(*it1);
    it1++;
  }
  it=a.begin();
  it1=bucket.begin();
  while(it!=a.end() && it1!=bucket.end())
  {
    std::vector<int>::iterator tmp_it=(*it1).begin();
    while(tmp_it!=(*it1).end())
    {
      *it=*tmp_it;
      tmp_it++;
      it++;
    }
    it1++;
  }
}

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

希望本文所述对大家C语言程序设计有所帮助。

赞 (0)

相关推荐

  • c语言合并两个已排序数组的示例(c语言数组排序)

    问题:将两个已排序数组合并成一个排序数组 这里先不考虑大数据量的情况(在数据量很大时不知大家有什么好的思路或方法?),只做简单数组的处理. 简单代码如下: 说明:之所以把merge函数定义成返回数组长度,是因为后续会有重复数据合并功能的merge版本,考虑到接口一致性. 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <string.h> int merge(int* ar1, int len1, int

  • c语言实现奇偶排序算法

    =====第2题:奇偶排序(一)===== 总时间限制:1000ms内存限制:65536kB描述输入十个整数,将十个整数按升序排列输出,并且奇数在前,偶数在后.输入输入十个整数输出按照奇偶排序好的十个整数 复制代码 代码如下: #include<stdio.h> #define  COUNT 10#define bool int#define true 1#define false 0 /*****负责冒泡排序***/int* sortFunction(int data[]){ int i,j

  • 桶排序算法的理解及C语言版代码示例

    理解: 桶排序是计数排序的变种,把计数排序中相邻的m个"小桶"放到一个"大桶"中,在分完桶后,对每个桶进行排序(一般用快排),然后合并成最后的结果. 基本思想: 桶排序假设序列由一个随机过程产生,该过程将元素均匀而独立地分布在区间[0,1)上.我们把区间[0,1)划分成n个相同大小的子区间,称为桶.将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. 效率分析: 桶排序的平均时间复杂度为线性的

  • c语言冒泡排序法代码

    总在写 总在错, 面试也还忘记 学习就是这么个过程, 温故才知新, 望自己谨记 忘记不要紧 复习就好 //排序是有很多种方法的 ,完成从小到大的排列 复制代码 代码如下: #include <stdio.h>void sort(int *a,int len){int i=0; int j; int t;    for(i=0;i<len;i++)    {        for(j=0;j<len-i-1;j++)        {            if(a[j]>a[

  • C语言对堆排序一个算法思路和实现代码

    算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的

  • 合并排序(C语言实现)

    合并排序(C语言实现)

    其基本模式如下: 分解:把一个问题分解成与原问题相似的子问题 解决:递归的解各个子问题 合并:合并子问题的结果得到了原问题的解. 现在就用递归算法,采用上面的分治思想来解合并排序. 合并排序(非降序) 分解:把合并排序分解成与两个子问题 伪代码: 复制代码 代码如下: MERGE_SORT(A, begin, end) if begin < end then mid<- int((begin + end)/2) MERGE_SORT(A, begin, mid) MERGE_SORT(A, m

  • C语言实现基于最大堆和最小堆的堆排序算法示例

    堆定义 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其

  • 用c语言实现冒泡排序,选择排序,快速排序

    代码如下所示: 复制代码 代码如下: /* * 冒泡排序 */void BubbleSort(int arr[], int n){ int temp; for (int i = 0; i < n - 1; i++) {  for (int j = i + 1; j < n; j++)  {   if (arr[i] > arr[j])   {    temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;   }  } }}/* * 选择排

  • C语言实现排序算法之归并排序详解

    排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

  • c语言实现冒泡排序、希尔排序等多种算法示例

    实现以下排序 插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置⒋ 重复步骤3,直到找到已排序的元素

  • c语言快速排序算法示例代码分享

    步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat

随机推荐