快速编写桩号
 
     方法一：根据需要左右上下排序快速编写桩号；
 
     方法二：在AutoCAD中获取两点坐标为角度，间隔等距编写一行桩号；
 
     方法三：在AutoCAD中桩位附近点击鼠标左键，即可生成桩号，继续点击生成加1桩号。
 
     方法四：在AutoCAD中获取1点坐标，整行整列生成桩号，筏板基础桩适用较多。
 
       可以一次性编写约20000个桩号，重复N个20000则无限制。
 
                 正冠桩基资料软件主界面
 
 
                             快速编写桩号样本一
 
 
快速编写桩号样本二
 
 
AutoCAD中不同图形代表桩均可生成桩号
 
 
 快速编写桩号使用帮助与说明
 

 
 
 
 
目录
 
 
1.冒泡排序
 
 
2.选择排序
 
 
3.插入排序
 
 
3.1 二分插入排序
 
 
4. 希尔排序
 
 
5. 快速排序
 
 
6.归并排序
 
 
我的理解：
 
 
7.堆排序
 
 
排序算法总结：
 
 

 

 

1.冒泡排序（bubble sort）
 
 
 
 
1.每次比较相邻的两个数。
 
 
2.两重循环。第一重循环的意义是找出len个有序数。下标：i
 
 
3.对于第二重循环，循环只需要在前len-1-i个数里面找。因为此时后i个数已经有序（最max的i个数）
 
 
	private static int[] bubbleSort(int[] arr) {
//	总体思路：从左到右，相邻的两个进行比较，如果第一个比第二个大，就交换位置
//	这样经过一轮排序，最大的会在数组的末尾，再重复操作排剩下的，第二大的在末尾倒数第二个
		for(int i=0;i<arr.length-1;i++)
//		外循环:需要确定length-1个位置
			for(int j=0;j<arr.length-1-i;j++) {
//			内循环:此时已经确定了i个位置，这些不参与比较，剩下只需比较length-1次
				if(arr[j]>arr[j+1]) {
					int temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		return arr;
	}
 
 
 

2.选择排序
 

 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
 
我们来看一下图解：
 
 
选择排序就是对数组中的元素进行比较选择，然后直接放置在排序后的位置。 
 首先指针K先指向数组0号位置，K相当于指明一个目标位置。然后另一个指针min从K开始，往后一次比较，找到最小的值，并存储在min中，比较了一轮后，min中存储的数就是整个数组中最小的数字。这是直接将min中的数字和K指向的数字交换即可。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。
  
 

3.插入排序（我认为最没用的排序....对于基本有序的数列还有点用）
 

 要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。
 
直接插入排序
 直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
 
我们来看一下图解： 
 

 这张图虽然只有一步，但是很好的表现了插入排序的运行过程。 
 例如,已知待排序的一组记录是： 
 1，3，5，8，2，1 
 加入之前的1，3，5，8已经按照直接插入排序排序好了，现在我们需要对2进行排序。 首先将2存在一个临时变量temp中， 然后指针从2的前一位开始判断，如果前一位比2大，则将前一位往后移，以此类推，直到找到比2小的元素。这时将2插入进去。
 
 
 
3.1 二分插入排序
 

 将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较，即可得到折半插入排序算法。在处理A[i]时，A[0]……A[i-1]已经按关键码值排好序。所谓折半比较，就是在插入A[i]时，取A[i-1/2]的关键码值与A[i]的关键码值进行比较，如果A[i]的关键码值小于A[i-1/2]的关键码值，则说明A[i]只能插入A[0]到A[i-1/2]之间，故可以在A[0]到A[i-1/2-1]之间继续使用折半比较；否则只能插入A[i-1/2]到A[i-1]之间，故可以在A[i-1/2+1]到A[i-1]之间继续使用折半比较。如此担负，直到最后能够确定插入的位置为止。一般在A[k]和A[r]之间采用折半，其中间结点为A[k+r/2]，经过一次比较即可排除一半记录，把可能插入的区间减小了一半，故称为折半。执行折半插入排序的前提是文件记录必须按顺序存储。
 

4. 希尔排序
 

 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminshing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。 
 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
 
下面我们来看图解:
 
 
 
 
希尔排序意在减少直接排序中的数字移动次数，通过设置一个间隔，每次进行比较的都是间隔的数字。 
 比如说如图： 
 第一次的间隔是5，则可以将数字分为5组，每一组两个数字，将这两个数字进行比较，逆序就交换。这样我们第一次排序就完成了。 
 这时候的数组肯定还是存在许多的逆序对，所以我们需要将间隔缩小，在进行比较。如图，这时候间隔变成了3，也就是可以将4个数字分为一组比较，这时候可以使用直接插入排序的思想，在组内进行直接插入排序比较。只是跨度为间隔数而不是1了。 
 之后以此类推，直到间隔为1的时候，这时候就直接是直接选择排序了。
 
 
关于间隔的选择
 
 
 
这个间隔怎么确定，是个数学难题，至今没有解答。但是通过大量的实验，还是有个经验值。
 
 
减小间隔
 
 
上面已经演示了以5为初始间隔对包含10个数据项的数组进行排序的情况。对于更大的数组开始的间隔也应该更大。然后间隔不断减小，直到间隔变成1。
 
 
举例来说，含有1000个数据项的数组可能先以364为增量，然后以121为增量，以40为增量，以13为增量，以4为增量，最后以 1为增量进行希尔排序。用来形成间隔的数列被称为间隔序列。这里所表示的间隔序列由Knuth提出，此序列是很常用的。数列以逆向形式从1开始，通过递归表达式
 
 
h=3*b+1
 
 
来产生，初始值为1。
 
 
在排序算法中，首先在一个短小的循环中使用序列的生成公式来计算出最初的间隔。h值最初被赋为1，然后应用公式h=3*h+1生成序列1,4,13,40,121,364，等等。当间隔大于数组大小的时候，这个过程停止。对于一个含有1000个数据项的数组，序列的第七个数字，1093就太大了。因此，使用序列的第六个数字作为最大的数字来开始这个排序过程，作364-增量排序。然后，每完成一次排序全程的外部循环，用前面提供的此公式倒推式来减小间隔：
 
 
h=(h-1)/3
 
 
这个倒推的公式生成逆置的序列364,121,40,13,4,1。从364开始，以每一个数字作为增量进行排序。当数组用1-增量排序后，算法结束。
 
 
希尔排序比插入排序快很多，它是基于什么原因呢？当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长。这是非常有效率的。当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。
 
注意后期的排序过程不撤销前期排序所做的工作。例如，已经完成了以40-增量的排序的数组，在经过以13-增量的排序后仍然保持了以40-增量的排序的结果。如果不是这样的话，希尔排序就无法实现排序的目的。
 
选择间隔序列可以称得上是一种魔法。至此只讨论了用公式h=h*3+1生成间隔序列，但是应用其他间隔序列也取得了不同程序的成功，只是一个绝对的条件，就是逐渐减小的间隔最后一定要等于1，因此最后一趟排序是一次普通的插入排序。
 
在希尔的原稿中，他建议初始的间距为N/2，简单地把每一趟排序分成了两半。因此，对于N=100的数组逐渐减小的间隔序列为50,25,12,6,3,1。这个方法的好处是不需要在不开始排序前为找到初始的间隔而计算序列；而只需要用2整除N。但是，这被证明并不是最好的数列。尽管对于大多数的数据来说这个方法还是比插入排序效果好，但是这种方法有时会使运行时间降到O(N2)，这并不比插入排序的效率更高。
 
这个方法的一个变形是用2.2而非2来整除每一个间隔。对于N=100的数组来说，会产生序列45,20,9,4,1。这比用2整除显著改善了效果，因为这样避免了某些导致时间复杂度为O(N2)的最坏情况的发生。不论N为何值，都需要一些额外的代码来保证序列的最后取值为1。
 


  
 
5. 快速排序（过程图解）
 
快速排序(QuickSort)
 划分的关键是要求出基准记录所在的位置pivotpos,编程时候的关键点
 
 
 
首先上图：    
 
 
 
从图中我们可以看到：
 
left指针，right指针，base参照数。
 
其实思想是蛮简单的，就是通过第一遍的遍历（让left和right指针重合）来找到数组的切割点。
 
 
 
第一步：首先我们从数组的left位置取出该数（20）作为基准（base）参照物。
 
 
第二步：从数组的right位置向前找，一直找到比（base）小的数，
 
 
            如果找到，将此数赋给left位置（也就是将10赋给20），
 
 
            此时数组为：10，40，50，10，60
 
 
            left和right指针分别为前后的10。
 
 
第三步：从数组的left位置向后找，一直找到比（base）大的数，
 
 
             如果找到，将此数赋给right的位置（也就是40赋给10），
 
 
             此时数组为：10，40，50，40，60，
 
 
             left和right指针分别为前后的40。
 
 
第四步：重复“第二,第三“步骤，直到left和right指针重合，
 
 
             最后将（base）插入到40的位置，
 
 
             此时数组值为： 10，20，50，40，60，至此完成一次排序。
 
 
第五步：此时20已经潜入到数组的内部，20的左侧一组数都比20小，20的右侧作为一组数都比20大，
 
 
            以20为切入点对左右两边数按照"第一，第二，第三，第四"步骤进行，最终快排大功告成。
 
 
 
 
 快速排序具有最好的平均性能（average behavior），但最坏性能（worst case behavior）和插入排序
 
相同，也是O(n^2)。比如一个序列5,4,3,2,1，要排为1,2,3,4,5。按照快速排序方法，每次只会有一个数据进入正确顺序，不能把数据分成大小相当的两份，很明显，排序的过程就成了一个歪脖子树，树的深度为n，那时间复杂度就成了O(n^2)。尽管如此，需要排序的情况几乎都是乱序的，自然性能就保证了。据书上的测试图来看，在数据量小于20的时候，插入排序具有最好的性能。当大于20时，快速排序具有最好的性能，归并(merge sort)和堆排序(heap sort)也望尘莫及，尽管复杂度都为nlog2(n)。
 

1、算法思想
     　快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

 （1） 分治法的基本思想
     　分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

 （2）快速排序的基本思想
     　设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解： 
     　在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
   注意：
     　划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
     　R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
                   其中low≤pivotpos≤high。
②求解： 
    　 通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
 
 
 
③组合： 
     　因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

2、快速排序算法QuickSort
   void QuickSort(SeqList R，int low，int high)
    { //对R[low..high]快速排序
      int pivotpos； //划分后的基准记录的位置
      if(low<high){//仅当区间长度大于1时才须排序
         pivotpos=Partition(R，low，high)； //对R[low..high]做划分
         QuickSort(R，low，pivotpos-1)； //对左区间递归排序
         QuickSort(R，pivotpos+1，high)； //对右区间递归排序
       }
     } //QuickSort

   注意：
     　为排序整个文件，只须调用QuickSort(R，1，n)即可完成对R[l..n]的排序。
 
 
 
 

6.归并排序
 
 
 
https://blog.csdn.net/qq_38346791/article/details/91353745
 
 
 
 
 
1.void mergearray(int a[],int first,int mid,int last,int temp[])    //将两个有序数组合并排序 
 
 
2.void mergesort(int a[],int first,int last,int temp[])    //将两个任意数组合并排序 
 
 
我的理解：
 
 
 
该排序算法的应用范围是：有序数列
 
 
对于两个有序数列，组合的时间复杂度是O（n）
 
 
 
 
而在分治法的中间时刻，有一个状态：底层时刻
 
 
在这个时候，每一个数组只有一个元素——相当于此时该数组有序。
 
 
所以就可以调用排序算法。
 
 
而排序算法调用完后形成的元素个数为2的数组，也是有序的，那么此时可以继续调用排序算法。
 
 
直到最后
 
 
 
 
 对于奇数与偶数不同的情况，是不影响的。
 
数量为1时不进行 mergesort 操作，不进入循环也就不会产生多余计算。合并大小为1的数组与大小为2的数组，是一样的。
 
#include<bits/stdc++.h>
using namespace std;
void mergearray(int a[],int first,int mid,int last,int temp[])	//将两个有序数组合并排序 
{
	int i=first,j=mid+1;
	int m=mid,n=last;
	int k=0;
	while(i<=m&&j<=n)
	{
		if(a[i]<a[j])
			temp[k++]=a[i++];
		else
			temp[k++]=a[j++];
	}
	while(i<=m)
		temp[k++]=a[i++];
	while(j<=n)
		temp[k++]=a[j++];
	for(i=0;i<k;i++)
		a[first+i]=temp[i];
}
 
void mergesort(int a[],int first,int last,int temp[])	//将两个任意数组合并排序 
{
	if(first<last)
	{
		int mid=(first+last)/2;
		mergesort(a,first,mid,temp);	//左边有序 
		mergesort(a,mid+1,last,temp);	//右边有序 
		mergearray(a,first,mid,last,temp);	//再将两个有序数组合并 
	}
}
 
int main()
{
	int a[1005];
	int temp[1005];
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	mergesort(a,0,n-1,temp);
	for(int i=0;i<n;i++)
		printf("%d ",a[i]);
}
 
 
 
7.堆排序
 
大根堆：父结点的值大于等于其子结点的值；升序使用。
 
先层次构造二叉树，用数组作为储存单位。然后每一次找出一个最大的。（第一次建堆比较麻烦，后面的时候比较次数都很少logn，因为子树也满足大根堆）
 
 
小根堆：父结点的值小于等于其子节点的值。
 
 
 
 
 
排序算法总结：
 
 
 
 
 
稳定性意思：
 
 
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
 

编程珠玑第一章，电话号码排序，问题是这样的，给你大约1000万个数字，让你用最快的方式进行排序，限制如下：
1. 内存大约1M
2. 数字都是整数，且不重复
3. 数字的范围最大是7位数。


文章提到了大约三种解法，
第一种是归并算法，只不过不在内存，在外存上做归并排序。大致思路是将原始文件读入，然后按照数字的大小划分10份，写到10个文件里。
这样每个文件就小于1M，然后对每个文件进行排序，排序之后，将文件合并。由于file1<file2<...<file10。所以合并很简单，直接依次读一遍，再写文件即可。
读次数：1+10+10
写次数:  10+10+1


第二种二种比较傻，分多次读，每次只读i~ j的数字，然后对其排序，并输入到文件。这个方法不再赘述。


第三种就是使用bitmap，思路就是把一个32位的整数用来存32个数字，比如，如果数字i出现了，则该数的二进制的第i位为1,否则为0。这样1000万个数字大约要1.25M.
首先读入所有的数字，存入bitmap,然后遍历bitmap，如果第i位为1，表示出现过，则输出到文件，否则，不输出。
下面是标准答案，感觉位运算写的很好，很高效，学习下：

 

  

   [cpp] 
   view plain
    copy
   

   

   
  
 
 
#include <iostream>  
#include <cstdio>  
using namespace std;  
  
#define BITSPERWORD 32  
#define SHIFT 5  
#define MASK 0x1F  
#define N 1000000  
int a[1+N/BITSPERWORD];  
  
/* 
 * 参考代码写的bitmap实在是太巧妙了，全部都是移位和位运算，非常高效。 
 * 常用技巧： 
 * 1. 求n除以2^i的余数 
 *   最低效：n%(2^i) 
 *   低效：n-(n/2^i)*2^i 
 *   高效：n-(n>>i)<<i 
 *   最高效: 从上面的过程可以看出，求除以2^i后的余数即保留低i位的二进制，其余位变0 
 *       #define MASK 0x1F (假设是i=5) 
 *       n&MASK 
 * 
 * 2. 将n的第i个二进制位置1或0 
 *    置1：n=n|(1<<i) 
 *    置0: n=n&~(1<<i) 
 */  
  
void set(int i) { a[i>>SHIFT]|= (1<<(i&MASK)); }  
void clr(int i) { a[i>>SHIFT]&= ~(1<<(i&MASK)); }  
int test(int i) { return a[i>>SHIFT]&(1<<(i&MASK)); }  
void reset() { memset(a,0,sizeof(a)); }  
  
int main(){  
    int i;  
    int n,m;  
    reset();  
    scanf("%d",&n);  
    for(i=0;i<n;i++){  
        scanf("%d",&m);  
        set(m);  
    }  
    for(i=0;i<100;i++)  
        if(test(i))  
            printf("%d\n",i);  
    return 0;  
}  

最快最简单的排序——桶排序
 
 
 
　　在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序，考试的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排序……总之很多东西都需要排序，可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。
 
 
 
 
　　首先出场的我们的主人公小哼，上面这个可爱的娃就是啦。期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有5个同学，这5个同学分别考了5分、3分、5分、2分和8分，哎考的真是惨不忍睹（满分是10分）。接下来将分数进行从大到小排序，排序后是8 5 5 3 2。你有没有什么好方法编写一段程序，让计算机随机读入5个数然后将这5个数从大到小输出？请先想一想，至少想15分钟再往下看吧(*^__^*) 。
 
 
 
 
　　我们这里只需借助一个一维数组就可以解决这个问题。请确定你真的仔细想过再往下看哦。
 
 
 
　　首先我们需要申请一个大小为11的数组int a[11]。OK现在你已经有了11个变量，编号从a[0]~a[10]。刚开始的时候，我们将a[0]~a[10]都初始化为0，表示这些分数还都没有人得过。例如a[0]等于0就表示目前还没有人得过0分，同理a[1]等于0就表示目前还没有人得过1分……a[10]等于0就表示目前还没有人得过10分。
 
 
 
 
 
 
下面开始处理每一个人的分数，第一个人的分数是5分，我们就将相对应a[5]的值在原来的基础增加1，即将a[5]的值从0改为1，表示5分出现过了一次。
 
 
 
 
　　第二个人的分数是3分，我们就把相对应a[3]的值在原来的基础上增加1，即将a[3]的值从0改为1，表示3分出现过了一次。
 
 
 
 
　　注意啦！第三个人的分数也是“5分”，所以a[5]的值需要在此基础上再增加1，即将a[5]的值从1改为2。表示5分出现过了两次。
 
 
 
 
　　按照刚才的方法处理第四个和第五个人的分数。最终结果就是下面这个图啦。
 
 
 
 
　　你发现没有，a[0]~a[10]中的数值其实就是0分到10分每个分数出现的次数。接下来，我们只需要将出现过的分数打印出来就可以了，出现几次就打印几次，具体如下。
 
　　a[0]为0，表示“0”没有出现过，不打印。
 
　　a[1]为0，表示“1”没有出现过，不打印。
 
　　a[2]为1，表示“2”出现过1次，打印2。
 
　　a[3]为1，表示“3”出现过1次，打印3。
 
　　a[4]为0，表示“4”没有出现过，不打印。
 
　　a[5]为2，表示“5”出现过2次，打印5 5。
 
　　a[6]为0，表示“6”没有出现过，不打印。
 
　　a[7]为0，表示“7”没有出现过，不打印。
 
　　a[8]为1，表示“8”出现过1次，打印8。
 
　　a[9]为0，表示“9”没有出现过，不打印。
 
　　a[10]为0，表示“10”没有出现过，不打印。
 
　　最终屏幕输出“2 3 5 5 8”，完整的代码如下。
 
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 
10
 
11
 
12
 
13
 
14
 
15
 
16
 
17
 
18
 
19
 
20
 
 
#include <stdio.h>
 
int main()
 
{
 
    int a[11],i,j,t;
 
    for(i=0;i<=10;i++)
 
        a[i]=0;  //初始化为0
 
                 
 
    for(i=1;i<=5;i++)  //循环读入5个数
 
    {
 
        scanf("%d",&t);  //把每一个数读到变量t中
 
        a[t]++;  //进行计数
 
    }
 
    for(i=0;i<=10;i++)  //依次判断a[0]~a[10]
 
        for(j=1;j<=a[i];j++)  //出现了几次就打印几次
 
            printf("%d ",i);
 
    getchar();getchar();
 
    //这里的getchar();用来暂停程序，以便查看程序输出的内容
 
    //也可以用system("pause");等来代替
 
    return 0;
 
}
 
     输入数据为
 
5 3 5 2 8 
 
 
 
  仔细观察的同学会发现，刚才实现的是从小到大排序。但是我们要求是从大到小排序，这该怎么办呢？还是先自己想一想再往下看哦。
 
 
 
　　其实很简单。只需要将for(i=0;i<=10;i++)改为for(i=10;i>=0;i--)就OK啦，快去试一试吧。
 
 
 
　　这种排序方法我们暂且叫他“桶排序”。因为其实真正的桶排序要比这个复杂一些，以后再详细讨论，目前此算法已经能够满足我们的需求了。
 
 
 
　　这个算法就好比有11个桶，编号从0~10。每出现一个数，就将对应编号的桶中的放一个小旗子，最后只要数数每个桶中有几个小旗子就OK了。例如2号桶中有1个小旗子，表示2出现了一次；3号桶中有1个小旗子，表示3出现了一次；5号桶中有2个小旗子，表示5出现了两次；8号桶中有1个小旗子，表示8出现了一次。
 
 
 
 
　　现在你可以请尝试一下输入n个0~1000之间的整数，将他们从大到小排序。提醒一下如果需要对数据范围在0~1000之间的整数进行排序，我们需要1001个桶，来表示0~1000之间每一个数出现的次数，这一点一定要注意。另外此处的每一个桶的作用其实就是“标记”每个数出现的次数，因此我喜欢将之前的数组a换个更贴切的名字book（book这个单词有记录、标记的意思），代码实现如下。
 
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 
10
 
11
 
12
 
13
 
14
 
15
 
16
 
17
 
18
 
 
#include <stdio.h>
 
int main()
 
{
 
    int book[1001],i,j,t,n;
 
    for(i=0;i<=1000;i++)
 
        book[i]=0;
 
    scanf("%d",&n);//输入一个数n，表示接下来有n个数
 
    for(i=1;i<=n;i++)//循环读入n个数，并进行桶排序
 
    {
 
        scanf("%d",&t);  //把每一个数读到变量t中
 
        book[t]++;  //进行计数，对编号为t的桶放一个小旗子
 
    }
 
    for(i=1000;i>=0;i--)  //依次判断编号1000~0的桶
 
        for(j=1;j<=book[i];j++)  //出现了几次就将桶的编号打印几次
 
             printf("%d ",i);
 
    getchar();getchar();
 
    return 0;
 
}
 
　可以输入以下数据进行验证
 
10
8 100 50 22 15 6 1 1000 999 0
 
　运行结果是
 
1000 999 100 50 22 15 8 6 1 0
 
 
 
　最后来说下时间复杂度的问题。代码中第6行的循环一共循环了m次（m为桶的个数），第9行的代码循环了n次（n为待排序数的个数），第14和15行一共循环了m+n次。所以整个排序算法一共执行了m+n+m+n次。我们用大写字母O来表示时间复杂度，因此该算法的时间复杂度是O(m+n+m+n)即O(2*(m+n))。我们在说时间复杂度时候可以忽略较小的常数，最终桶排序的时间复杂度为O(m+n)。还有一点，在表示时间复杂度的时候，n和m通常用大写字母即O(M+N)。
 
 
 
　　这是一个非常快的排序算法。桶排序从1956年就开始被使用，该算法的基本思想是由E.J.Issac  R.C.Singleton提出来。之前说过，其实这并不是真正的桶排序算法，真正的桶排序算法要比这个更加复杂。但是考虑到此处是算法讲解的第一篇，我想还是越简单易懂越好，真正的桶排序留在以后再聊吧。需要说明一点的是：我们目前学习的简化版桶排序算法其本质上还不能算是一个真正意义上的排序算法。为什么呢？例如遇到下面这个例子就没辙了。
 
 
 
   现在分别有5个人的名字和分数：huhu 5分、haha 3分、xixi 5分、hengheng 2分和gaoshou 8分。请按照分数从高到低，输出他们的名字。即应该输出gaoshou、huhu、xixi、haha、hengheng。发现问题了没有？如果使用我们刚才简化版的桶排序算法仅仅是把分数进行了排序。最终输出的也仅仅是分数，但没有对人本身进行排序。也就是说，我们现在并不知道排序后的分数原本对应着哪一个人！这该怎么办呢？不要着急请听下回——冒泡排序。
 
 
 
我有一个微信公众号，经常会分享一些Java技术相关的干货；如果你喜欢我的分享，可以用微信搜索“Java团长”或者“javatuanzhang”关注。