C语言基本排序算法之桶式排序实例

本文实例讲述了C语言基本排序算法之桶式排序。分享给大家供大家参考,具体如下:

桶式排序是对一个有n个整型元素的数组a[n],其中对任意i,0 <= a[i] <= m的特殊排序算法。

可以对 n==m, n != m分别处理。写代码时需要注意的的是a[i]是访问第i-1个元素,而非第i个。

/************************************************************************************/
/* Bucket_Sort.h 桶式排序算法 */
/* 问题:对一个有n个整型元素a[0],a[1],…,a[n-1]的数组排序,其中0 <= a[i] <= m,任意i */
/* 程序:运行时间为O(m+n),辅助空间为O(m) */
/* 当 n=m 时特殊处理,运行时间为O(N), 辅助空间为O(1) */
/************************************************************************************/
#include <vector>
/*m != n */
void Bucket_Sort_m(int *a, int n, int m)
{
  std::vector<int> temp(m,0);
  int i;
  for(i = 0; i != n; ++i) //遍历a[]
    ++temp[a[i]-1]; //如果有对应于下标的值,标记为1,否则为0
  i = 0;
  for(int j = 1; j <= m; ++j) //遍历temp向量
    if(temp[j-1]) a[i++] = j;
  temp.clear();
}
/* m == n */
/* 最后的结果是a[i-1] = i */
void Bucket_Sort(int *a,int n)
{
  for(int i = 1; i <= n; ++i)
  {
    while(a[i-1] != i)
    {
       int temp = a[a[i-1]-1];
       a[a[i-1]-1] = a[i-1];
       a[i-1] = temp;
    }
    /* 伪代码:如果假设可以通过a[i]访问数组的第i个元素,而不是第i-1个 */
    /*while(a[i] != i)
    {
       int temp = a[a[i]];
       a[a[i]] = a[i];
       a[i] = temp;
    }
    */
  }
}

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

时间: 2017-09-25

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

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

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

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

C语言 实现归并排序算法

C语言 实现归并排序算法 归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 一个归并排序的例子:对一个随机点的链表进行排序 算法描述 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾

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

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

常用排序算法的C语言版实现示例整理

所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来.其确切定义如下: 输入:n个记录R1,R2,-,Rn,其相应的关键字分别为K1,K2,-,Kn. 输出:Ril,Ri2,-,Rin,使得Ki1≤Ki2≤-≤Kin.(或Ki1≥Ki2≥-≥Kin).     排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量.基本的排序算法有如下几种:交换排序(冒泡排序.快速排序).选择排序(直接选择排序.堆排序).插入排序(直接插入排序.希尔排序).归并排序.分配排序(基数排

C语言排序算法之冒泡排序实现方法【改进版】

本文实例讲述了C语言排序算法之冒泡排序实现方法.分享给大家供大家参考,具体如下: 冒泡排序和改进的冒泡排序 /*------------------------------------------------------------------------------------------- Bubble_sort.h 冒泡排序: 时间复杂度为O(N^2) 改进的冒泡排序: 时间复杂度仍为O(N^2) 一般的冒泡排序方法有可能会在已经排好序的情况下继续比较,改进的冒泡排序 设置了一个哨兵fla

C语言基本排序算法之插入排序与直接选择排序实现方法

本文实例讲述了C语言基本排序算法之插入排序与直接选择排序实现方法.分享给大家供大家参考,具体如下: 声明待排序元素类型 /*-------------------------- typedef.h 方便修改待排序元素类型 -------------------------------------*/ #ifndef TYPEDEF_H #define TYPEDEF_H typedef int T; #endif 插入排序: /*---------------------------------

C语言 冒泡排序算法详解及实例

C语言 冒泡排序算法 冒泡排序(Bubble Sort)是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序对n个项目需要O(n2)的比较次数,且可以原地排序.尽管这个算法是最简单了解和实作的排序算法之一,但它对于少数元素之外的数列排序是很没有效率的. 冒泡排序是与插入排序拥有相等的执

C语言基本排序算法之shell排序实例

本文实例讲述了C语言基本排序算法之shell排序.分享给大家供大家参考,具体如下: shell排序是对直接插入方法的改进方法. /*------------------------------------------------------------------------------------- Shell_sort.h shell排序是对直接插入方法的改进,它并不是对相邻元素进行比较,而是对一定间隔的元素比较. 选择增量序列的几种方法:(为方便,本例采用第一种增量序列) 1. h[1]=

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

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

Java基于余弦方法实现的计算相似度算法示例

本文实例讲述了Java基于余弦方法实现的计算相似度算法.分享给大家供大家参考,具体如下: (1)余弦相似性 通过测量两个向量之间的角的余弦值来度量它们之间的相似性.0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1.从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向.所以,它通常用于文件比较. 相关介绍可参考百度百科:余弦相似性 (2)算法实现的中未使用权重(IDF ---逆文档频率),使用词项的出现次数作为向量空间的值. import java.util.H

Python实现基于二叉树存储结构的堆排序算法示例

本文实例讲述了Python实现基于二叉树存储结构的堆排序算法.分享给大家供大家参考,具体如下: 既然用Python实现了二叉树,当然要写点东西练练手. 网络上堆排序的教程很多,但是却几乎都是以数组存储的数,直接以下标访问元素,当然这样是完全没有问题的,实现简单,访问速度快,也容易理解. 但是以练手的角度来看,我还是写了一个二叉树存储结构的堆排序 其中最难的问题就是交换二叉树中两个节点. 因为一个节点最多与三个节点相连,那么两个节点互换,就需要考虑到5个节点之间的关系,也需要判断是左右孩子,这将是

基于Java实现的一层简单人工神经网络算法示例

本文实例讲述了基于Java实现的一层简单人工神经网络算法.分享给大家供大家参考,具体如下: 先来看看笔者绘制的算法图: 2.数据类 import java.util.Arrays; public class Data { double[] vector; int dimention; int type; public double[] getVector() { return vector; } public void setVector(double[] vector) { this.vect

Python基于pycrypto实现的AES加密和解密算法示例

本文实例讲述了Python基于pycrypto实现的AES加密和解密算法.分享给大家供大家参考,具体如下: 一 代码 # -*- coding: UTF-8 -*- import string import random from Crypto.Cipher import AES def keyGenerater(length): '''''生成指定长度的秘钥''' if length not in (16, 24, 32): return None x = string.ascii_lette

C语言编写基于TCP和UDP协议的Socket通信程序示例

Tcp多线程服务器和客户端程序 服务器程序: #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <sys/types.h> #include <sys/socket.h> #include <unistd.h> #define PORT 8082 #define BUFSIZE 512 cha

Java基于循环递归回溯实现八皇后问题算法示例

本文实例讲述了Java基于循环递归回溯实现八皇后问题.分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @author Administrator * */ public interface Piece { abstract boolean isRow(int line); abstract boolean isCol(int line,int col); } 棋盘类: /** * 棋盘 * @author Administrator * */ public

解读堆排序算法及用C++实现基于最大堆的堆排序示例

1.堆排序定义 n个关键字序列Kl,K2,-,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. [例]关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1

C语言辗转相除法求2个数的最小公约数

辗转相除法最大的用途就是用来求两个数的最大公约数. 用(a,b)来表示a和b的最大公约数. 有定理: 已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c). (证明过程请参考其它资料) 例:求 15750 与27216的最大公约数. 解: ∵27216=15750×1+11466 ∴(15750,27216)=(15750,11466) ∵15750=11466×1+4284  ∴(15750,11466)=(11466,4284) ∵11466=4284×2+2898  ∴(114

C语言数据结构之二叉树的非递归后序遍历算法

C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,