C语言9种常用排序法
1.冒泡排序
2.选择排序
3.插入排序
4.快速排序
5.希尔排序
6.归并排序
7.堆排序
8.带哨兵的直接插入排序
9.基数排序
例子:乱序输入n个数,输出从小到大排序后的结果1.冒泡排序
#include
int main()
{
int i, j, n, a[100], temp;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i scanf("%d",&a[i]); for(i=0;i { for(j=0;j { if(a[j]>a[j+1]) //比较a[j]与a[j+1],使a[j+1]大于a[j] { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; } } } for(i=0;i printf("%d ",a[i]); printf("\n"); } return 0; } 2.选择排序 #include int main() { int i, j, n, a[100], t, temp; while(scanf("%d",&n)!=EOF) { for(i=0;i scanf("%d",&a[i]); for(i=0;i { t = i; for(j=i+1;j if(a[t]>a[j]) t = j; } temp = a[i]; a[i] = a[t]; a[t] = temp; } for(i=0;i printf("%d ",a[i]); printf("\n"); } return 0; } 3.快速排序 /* 1.假设数组为a[n]; 2.第一次排序过程如下: 取x = 0 ( a[0]为中轴 ); i=0 (第一个元素下标), j=n-1(最后一个元素下标); 重复下面过程:(直到i>=j) { 从a[j]起,向前找小于a[x]的元素,同时j--,找到后,a[j]与a[x]交换,x=j; 从a[i]起,向后找大于a[x]的元素,同时i++,找到后,a[i]与a[x]交换,x=i; } 3.注意快排函数是迭代函数,必须要有结束条件 (因为忽略结束条件,调试了很久......) 4.再对a[low]~a[x-1]、a[x+1]~a[high]分别调用快排函数 */ #include void quicksort(int a[],int low,int high); int main() { int i, n, a[100]; while(scanf("%d",&n)!=EOF) { for(i=0;i scanf("%d",&a[i]); quicksort(a,0,n-1); for(i=0;i printf("%d ",a[i]); printf("\n"); } return 0; } void quicksort(int a[],int low,int high) { if(low>=high) return; //坑爹的结束条件,return后面不能跟数值 int i=low, j= high, x=i, temp; while(i { for(;a[j]>=a[x]&&i if(i { temp = a[j]; a[j] = a[i]; a[i] = temp; x = j; i++; } else break; //i>=j即可跳出本次while循环 for(;a[i]<=a[x]&&i if(i { temp = a[i]; a[j] = temp; x = i; j--; } else break; //跳出本次while循环 } quicksort(a,low,x-1); quicksort(a,x+1,high); } 4.插入排序法 #include void show(int a[],int n) //输出数组 { int i; for(i=0;i printf("%d ",a[i]); printf("\n"); } void insertsort(int a[],int n); int main() { while(scanf("%d",&n)!=EOF) { for(i=0;i scanf("%d",&a[i]); insertsort(a,n); show(a,n); } return 0; } void insertsort(int a[],int n) { int i ,j ,k ,temp; for(i=1;i { j=i-1; for(;a[i]=0;j--); //寻找插入点 j++; if(j==i) //该数有序,不需要前插 continue; else { temp=a[i]; for(k=i-1;k>=j;k--) //将插入点后面的数依次后移一位 { a[k+1]=a[k]; } } } } 5.shell排序法 #include void show(int a[],int n) //输出数组{ int i; for(i=0;i printf("%d ",a[i]); printf("\n"); } void shellsort(int a[],int n); int main() { int i, n, a[100]; while(scanf("%d",&n)!=EOF) { for(i=0;i scanf("%d",&a[i]); shellsort(a,n); show(a,n); } return 0; } void shellsort(int a[],int n) { int k ,i ,j ,l ,temp; k = n/2; while(k>=1) { for(i=k;i { if(a[i]>=a[i-k]) //已经有序,不需要移动 continue; else { for(j=i-k;a[j]>=a[i]&&j>=0;j=j-k); j+=k; //寻找插入点a[j] temp = a[i]; // 保存a[i] for(l=i-k;l>=j;l-=k) //依次向后移动k个位置 { a[l+k] = a[l]; } a[j]=temp; //插入 } } k = k/2; } } 6.归并排序 归并排序是一种很容易进行并行化的算法,因为归并的各个数据区间都是独立的,没有依赖关系。并且归并排序是一种速度比较快的排序,且是一种稳定的排序算法,排序速度与关键词初始排列无关。 串行归并排序的算法大体的可以描述为:首先将要排序的表分成两个节点个数基本相等的子表,然后对每个子表进行排序,最后将排好序的两个子表合并成一个子表。在对子表进行排序时可以将子表再分解成两个节点数量基本相同的子表,当子表足够小时,也可以采用其他排序方法对子表进行排序,然后再对排好序的子表进行归并操作,最后将整个表排好序 算法流程图: /*伪代码: mergesort(int a[],int low,int high); if(high-low+1>2)执行如下几步:(3个及以上) mid = (0+n)/2; mergesort(a,low,mid-1); mergesort(a,mid,high); 进行本轮二路归并;bsort(int low,int mid,int high); i=low,j=mid; while(i { 先归并入other[]; } 将剩下的归并入数组other[]; 将other[low~high],复制到a[low~high]; else: (3个以下) if(a[low]>=a[high]) 交换a[low],a[high]; */ #include int other[100]; void exchange(int *a,int *b) { int t=*a; *a=*b; *b=t; } void show(int a[],int n) //输出数组 { int i; for(i=0;i printf("%d ",a[i]); printf("\n"); } void mergesort(int a[],int low,int high); int main() { int i, n, a[100]; while(scanf("%d",&n)!=EOF) { for(i=0;i scanf("%d",&a[i]); mergesort(a,0,n-1); show(a,n); } return 0; } void mergesort(int a[],int low,int high) { if((high-low+1)>2) //含3个以上 { int mid = (high+low)/2; mergesort(a,low,mid); mergesort(a,mid+1,high); int i=low, j=mid+1, k=low; while(i<=mid&&j<=high) { if(a[i]<=a[j]) { other[k++]=a[i++]; } if(a[i]>a[j]) { other[k++]=a[j++]; } } while(i<=mid) { other[k++]=a[i++]; } while(j<=high) { other[k++]=a[j++]; } for(i=low;i<=high;i++) a[i]=other[i]; } else //含2及个以下 { if(a[low]>a[high]) { exchange(a+low,a+high); } } } 7.堆排序 //堆排序 /*(堆是一个完全二叉树,根结点值最大(小)) 1.heapadjust(int a[],int i,int sizea) 功能:以a[i]为根,形成一个堆 buildheap(int a[],int sizea) 功能:调用heapadjust(),使a[]形成一个堆 heapsort(int a[],int sizea) 功能:do{建堆,输出堆顶}while(堆不空) */ #include void show(int a[],int n) //输出数组 { int i; for(i=0;i printf("%d ",a[i]); printf("\n"); } void exchange(int *a,int *b) { int t=*a; *a=*b; *b=t; } void heapadjust(int a[],int i,int sizea) { int maxi=i; int l=2*i+1; int r=2*i+2; if(i<(sizea/2)) //a[i]为叶结点,则不需要调整 { if(l<=(sizea-1)&&a[l]>a[i]) //左孩子比a[i]大的,取左孩子下标 { maxi=l; } if(r<=(sizea-1)&&a[r]>a[maxi]) //右孩子最大,取右孩子下标 { maxi=r; } if(maxi!=i) //取比根大的孩子,与根调换 { exchange(&a[maxi],&a[i]); heapadjust(a,maxi,sizea); //跌倒,以a[maxi]为根,向下调整为大根堆。 } } } //函数功能:从最后一个非叶结点起,向上直到根结点,逐步调整,建立大根对堆void buildheap(int a[],int sizea) { int i; for(i=(sizea/2-1);i>=0;i--) //a[i]为最后一个非叶结点 { heapadjust(a,i,sizea); } } void heapsort(int a[],int sizea) { int i; int j=sizea; for(i=0;i buildheap(a,j); exchange(&a[0],&a[--j]); //将根(最大)结点交换到后面去 //堆中元素个数减一 } } int main() { int i, n, a[100]; while(scanf("%d",&n)!=EOF) { for(i=0;i scanf("%d",&a[i]); heapsort(a,n); show(a,n); } return 0; } 8. 带哨兵的直接插入排序 /*从小到大排序 a[0]用作哨兵,当某个数a[i],找插入位置时,先令a[0]=a[i],再向前比较,当比较到a[0]时,说明插入位置为a[1],这样可以防止数组越界. */ #include void show(int a[],int n) //输出数组 { int i; for(i=1;i<=n;i++) printf("%d ",a[i]); printf("\n"); } void dir_insert(int a[],int n) { int i,j; for(i=2;i<=n;i++) { a[0]=a[i]; for(j=i-1;a[j]>a[0];j--) //插入位置:j a[j+1]=a[j]; a[++j]=a[0]; } } int main() { int i, n, a[100]; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&a[i]); dir_insert(a,n); show(a,n); } return 0; } 9.基数排序 //基数排序 /*假设输入数列最多为4位,且都是十进制数 要做4次划分、收集 */ #include #include #define N 4 //每个数最多4位 void show(int a[],int n) //输出数组 { int i; for(i=1;i<=n;i++) printf("%d ",a[i]); printf("\n"); } void radixsort(int c[],int i,int n) //以第i位为依据进行划分和收集 { int a[10][30]={{0},{0},{0},{0},{0},{0},{0},{0},{0},{0}}; //a[i][]中收集本次划分基数为i的数 int b[10]={0}; //b[i]表示本次本次划分后,基数为i的数的个数 int j,k,l,m; k=pow(10,i); l=k/10; for(j=1;j<=n;j++) //一次分配的过程 { m=(c[j]%k)/l; //判断c[j]在本次划分中被分到哪个部分 a[m][b[m]++]=c[j]; //分配完毕后,基数为m的数为b[m]个 } l=1; for(m=0;m<10;m++) //收集 { for(j=0;j { c[l++]=a[m][j]; } } } void basesort(int c[],int n) { int i; for(i=1;i<=N;i++) { radixsort(c,i,n); } } int main() { int i, n, c[100]; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&c[i]); basesort(c,n); show(c,n); } return 0; } C语言几种常见的排序方法 2009-04-2219:55 插入排序是这样实现的: 首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。 从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。 重复2号步骤,直至原数列为空。 插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的: 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。 重复2号步骤,直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。 选择排序 选择排序是这样实现的: 设数组内存放了n个待排数字,数组下标从1开始,到n结束。 i=1 从数组的第i个元素开始到第n个元素,寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n-1算法结束,否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始,我们要接触高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了,大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同,它是这样的: 首先新建一个空列表,作用与插入排序中的"有序列表"相同。 找到数列中最大的数字,将其加在"有序列表"的末尾,并将其从原数列中删除。 重复2号步骤,直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高(因为有堆这种数据结构以及它奇妙的特征,使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度,维护需要logn的时间复杂度),但是实现相对复杂(可以说是这里7种算法中比较难实现的)。 C语言9种常用排序法 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.带哨兵的直接插入排序 9.基数排序 例子:乱序输入n个数,输出从小到大排序后的结果1.冒泡排序 #include for(i=0;i int i, j, n, a[100], t, temp; while(scanf("%d",&n)!=EOF) { for(i=0;i 一、设计思想 插入排序:首先,我们定义我们需要排序的数组,得到数组的长度。如果数组只有一个数字,那么我们直接认为它已经是排好序的,就不需要再进行调整,直接就得到了我们的结果。否则,我们从数组中的第二个元素开始遍历。然后,启动主索引,我们用curr当做我们遍历的主索引,每次主索引的开始,我们都使得要插入的位置(insertIndex)等于-1,即我们认为主索引之前的元素没有比主索引指向的元素值大的元素,那么自然主索引位置的元素不需要挪动位置。然后,开始副索引,副索引遍历所有主索引之前的排好的元素,当发现主索引之前的某个元素比主索引指向的元素的值大时,我们就将要插入的位置(insertIndex)记为第一个比主索引指向元素的位置,跳出副索引;否则,等待副索引自然完成。副索引遍历结束后,我们判断当前要插入的位置(insertIndex)是否等于-1,如果等于-1,说明主索引之前元素的值没有一个比主索引指向的元素的值大,那么主索引位置的元素不要挪动位置,回到主索引,主索引向后走一位,进行下一次主索引的遍历;否则,说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大,那么,我们记录当前主索引指向的元素的值,然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位,这里注意,要从后向前一位一位挪,否则,会使得数组成为一串相同的数字。最后,将记录下的当前索引指向的元素的值放在要插入的位置(insertIndex)处,进行下一次主索引的遍历。继续上面的工作,最终我们就可以得到我们的排序结果。插入排序的特点在于,我们每次遍历,主索引之前的元素都是已经排好序的,我们找到比主索引指向元素的值大的第一个元素的位置,然后将主索引指向位置的元素插入到该位置,将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法,使得挪动的次数相对较多,如果对于排序数据量较大,挪动成本较高的情况时,这种排序算法显然成本较高,时间复杂度相对较差,是初等通用排序算法中的一种。 选择排序:选择排序相对插入排序,是插入排序的一个优化,优化的前提是我们认为数据是比较大的,挪动数据的代价比数据比较的代价大很多,所以我们选择排序是追求少挪动,以比较次数换取挪动次数。首先,我们定义我们需要排序的数组,得到数组的长度,定义一个结果数组,用来存放排好序的数组,定义一个最小值,定义一个最小值的位置。然后,进入我们的遍历,每次进入遍历的时候我们都使得当前的最小值为9999,即认为每次最小值都是最大的数,用来进行和其他元素比较得到最小值,每次认为最小值的位置都是0,用来重新记录最小值的位置。然后,进入第二层循环,进行数值的比较,如果数组中的某个元素的值比最小值小,那么将当前的最小值设为元素的值,然后记录下来元素的位置,这样,当跳出循环体的时候,我们会得到要排序数组中的最小值,然后将最小值位置的数值设置为9999,即我们得到了最小值之后,就让数组中的这个数成为最大值,然后将结果数组result[]第主索引值位置上的元素赋值为最小值,进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于,我们挪动元素的次数很少,只是每次对要排序的数组进行整体遍历,找到其中的最小的元素,然后将改元素的值放到一个新的结果数组中去,这样大大减少了挪动的次序,即我们要排序的数组有多少元素,我们就挪动多少次,而因为每次都要对数组的所有元素进行遍历,那么比较的次数就比较多,达到了n2次,所以,我们使用选择排序的前提是,认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序,他的比较次数大于插入排序的次数,而挪动次数就很少,元素有多少个,挪动次数就是多少个。 希尔排序:首先,我们定义一个要排序的数组,然后定义一个步长的数组,该步长数组是由一组特定的数字组成的,步长数组具体得到过程我们不去考虑,是由科学家经过很长时间计算得到的,已经根据时间复杂度的要求,得到了最适合希尔排序的一组步长值以及计算C语言几种常见的排序方法
C语言9种常用排序法
几种排序算法的分析与比较--C语言
C语言的四种排序