C语言排序比较
C语言大小字母输出
大概有如下的几类:
冒泡排序,选择排序, 希而排序,快速排序,堆排序,合并排序,基数排序等等!
冒泡排序:
42,35,7,89,34,65,12,9;
第一次:以第一个位置的数作为关键字依次和后面的数进行比较,如果比第一个小,就和第一个位置的数进行交换,找出最小的数。
7,42,35,89,34,65,12,9
第二次:以第二个位置的数作为关键字依次和后面的数进行比较,如果比第二个位置的数小,就和第二个位置的数进行交换,找出最小的数。
7,9,42,89,35,65,34,12
第三次:以第三个位置的数作为关键字依次和后面的数进行比较,如果比第三个位置的数小,就和第三个位置的数进行交换,找出最小的数。
7,9,12,89,42,65,35,34
以此类推.....这里不一一介绍了!
#include<stdlib.h>
#include <math.h>
#define L 8 //排序元素个数
#define FALSE 0
#define TRUE 1
typedef struct
{
int key;
char otherinfo;
}RecType;
typedef RecType Seqlist[L+1];
int num; //定义排序趟数的全局变量
Seqlist R;
//直接插入排序
void Insertsort()
{
int i,j,k,m=0;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=2;i<=L;i++)
{
if(R[i].key<R[i-1].key)
{
R[0]=R[i];
j=i-1;
while(R[0].key<R[j].key)
{
R[j+1]=R[j];
j--;
}
R[j+1]=R[0];
}
m++;
printf("\t\t第%d趟排序结果为(按回车键继续):\n\t\t",m);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//希尔排序
void Shellsort()
{
int i,j,gap,x,m=0,k;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
gap=L/2;
while(gap>0)
{
for(i=gap+1;i<=L;i++)
{
j=i-gap;
while(j>0)
{
if(R[j].key>R[j+gap].key)
{
x=R[j].key;
R[j].key=R[j+gap].key;
R[j+gap].key=x;
j=j-gap;
}
else
{
j=0;
}
}
}
gap=gap/2;
m++;
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",m);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//冒泡排序
void Bubblesort()
{
int i,j,k;
int exchange;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=1;i<L;i++)
{
exchange=FALSE;
for(j=L;j>=i+1;j--)
{
if(R[j].key<R[j-1].key)
{
R[0].key=R[j].key;
R[j].key=R[j-1].key;
R[j-1].key=R[0].key;
exchange=TRUE;
}
}
if(exchange)
{
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",i);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
int Partition(int i,int j) //i和j为形式参数,分别代表low和high
{
RecType pirot=R[i];
while(i<j)
{
while(i<j&&R[j].key>=pirot.key)
{
j--;
}
if(i<j)
{
R[i++]=R[j];
}
while(i<j&&R[j].key<=pirot.key)
{
i++;
}
if(i<j)
{
R[j--]=R[i];
}
}
R[i]=pirot;
return i;
}
//递归形式为快速排序
void Quicksort(int low,int high)
{
int pirotpos,k;
if(low<high)
{
pirotpos=Partition(low,high);
num++;
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",num);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
Quicksort(low,pirotpos-1);
Quicksort(pirotpos+1,high);
}
}
//选择排序
void Selectsort()
{
int i,j,k,h;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=1;i<L;i++)
{
h=i;
for(j=i+1;j<=L;j++)
{
if(R[j].key<R[h].key)
{
h=j;
}
}
if(h!=j)
{
R[0]=R[i];
R[i]=R[h];
R[h]=R[0];
}
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",i);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
void Merge(int low,int mm,int high)
{
int i=low,j=mm+1,p=0;
RecType *R1;
R1=new RecType[high-low+1];
if(!R1)
{
printf("内存容量不够!");
}
while(i<=mm&&j<=high)
{
R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
}
while(i<=mm)
{
R1[p++]=R[i++];
}
while(j<=high)
{
R1[p++]=R[j++];
}
for(p=0,i=low;i<=high;p++,i++)
{
R[i]=R1[p];
}
}
void MergePass(int length)
{
int i;
for(i=1;i+2*length-1<=L;i=i+2*length)
{
Merge(i,i+length-1,i+2*length-1);
}
if(i+length-1<L)
{
Merge(i,i+length-1,L);
}
}
//归并排序
void Mergesort()
{
int length,k,m=0,i;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(length=1;length<L;length*=2)
{
MergePass(length);
m++;
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",m);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//堆建
void CreateHeap(int root,int index)
{
int j,temp,finish;
j=2*root;
temp=R[root].key;
finish=0;
while(j<=index&&finish==0)
{
if(j<index)
{
if(R[j].key<R[j+1].key)
{
j++;
}
}
if(temp>=R[j].key)
{
finish=1;
}
else
{
R[j/2].key=R[j].key;
j=j*2;
}
}
R[j/2].key=temp;
}//堆排序
void Heapsort()
{
int i,j,temp,k;
for(i=(L/2);i>=1;i--)
{
CreateHeap(i,L);
}
for(i=L-1,k=1;i>=1;i--,k++)
{
temp=R[i+1].key;
R[i+1].key=R[1].key;
R[1].key=temp;
CreateHeap(1,i);
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",k);
for(j=1;j<=L;j++)
{
printf("%5d",R[j].key);
}
getchar();
printf("\n");
}
}
void Heap()
{
int i;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
getchar();
printf("\n");
Heapsort();
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
main()
{
Seqlist S;
int i,k;
char ch1,ch2,q;
printf("\n\t\t请输入%d个待排序数据(按回车键分隔):\n\t\t",L);
for(i=1;i<=L;i++)
{
scanf("%d",&S[i].key);
getchar();
printf("\t\t");
}
printf("\n\t\t排序数据已经输入完毕!");
ch1='y';
while(ch1=='y'||ch1=='Y')
{
printf("\n");
printf("\n\t\t 排 序 子 系 统 \n");
printf("\n\t\t*******************************************\n");
printf("\n\t\t* 1--------更新排序数据 *\n");
printf("\n\t\t* 2--------直接插入排序 *\n");
printf("\n\t\t* 3--------希 尔 排 序 *\n");
printf("\n\t\t* 4--------冒 泡 排 序 *\n");
printf("\n\t\t* 5--------快 速 排 序 *\n");
printf("\n\t\t* 6--------选 择 排 序 *\n");
printf("\n\t\t* 7--------归 并 排 序 *\n");
printf("\n\t\t* 8--------堆 排 序 *\n");
printf("\n\t\t* 0--------返 回 *\n");
printf("\n\t\t*******************************************\n");
printf("\n\t\t 请选择菜单号(0--8):");
scanf("%c",&ch2);
getchar();
for(i=1;i<=L;i++)
{
R[i].key=S[i].key;
}
switch(ch2)
{
case '1':
printf("\n\t\t请输入%d个待排序数据(按回车键分隔):\n\t\t",L);
for(i=1;i<=L;i++)
{
scanf("%d",&S[i].key);
getchar();
printf("\t\t");
}
printf("\n\t\t排序数据已经输入完毕!");
break;
case '2':
Insertsort();
break;
case '3':
Shellsort();
break;
case '4':
Bubblesort();
break;
case '5':
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
num=0;
Quicksort(1,L);
printf("\n\t\t排序的最终结果是:\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
printf("\n");
break;
case '6':
Selectsort();
break;
case '7':
Mergesort();
break;
case '8':
Heap();
break;
case '0':
ch1='n';
break;
default:
system("cls");
printf("\n\t\t 对不起,您的输入有误,请重新输入!\n");
break;
}
if(ch2!='0')
{
if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')
{
printf("\n\n\t\t排序输出完毕!");
printf("\n\t\t按回车键返回。");
q=getchar();
if(q!='\xA')
{
getchar();
ch1='n';
}
}
}
}
}
没有错啊!我刚才试了一下,没有错!你把工程命名的后缀名为.cpp就可以了。
Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体
Bead sort — O(n) or O(√n), 但需要特别的硬体
Pancake sorting — O(n), 但需要特别的硬体
排序的算法
排序的算法有很多,对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序,他们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。
插入排序
冒泡排序
选择排序
快速排序
堆排序
归并排序
基数排序
希尔排序
插入排序
插入排序是这样实现的:
首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。
从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。
重复2号步骤,直至原数列为空。
插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。
冒泡排序
冒泡排序是这样实现的:
首先将所有待排序的数字放入工作列表中。
从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。
重复2号步骤,直至再也不能交换。
冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。
选择排序
选择排序是这样实现的:
设数组内存放了n个待排数字,数组下标从1开始,到n结束。
i=1
从数组的第i个元素开始到第n个元素,寻找最小的元素。
将上一步找到的最小元素和第i位元素交换。
如果i=n-1算法结束,否则回到第3步
选择排序的平均时间复杂度也是O(n²)的。
快速排序
现在开始,我们要接触高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了,大大减少了数字间不必要的比较。但查找数据得另当别论了。
堆排序
堆排序与前面的算法都不同,它是这样的:
首先新建一个空列表,作用与插入排序中的"有序列表"相同。
找到数列中最大的数字,将其加在"有序列表"的末尾,并将其从原数列中删除。
重复2号步骤,直至原数列为空。
堆排序的平均时间复杂度为nlogn,效率高(因为有堆这种数据结构以及它奇妙的特征,使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度,维护需要logn的时间复杂度),但是实现相对复杂(可以说是这里7种算法中比较难实现的)。
看起来似乎堆排序与插入排序有些相像,但他们其实是本质不同的算法。至少,他们的时间复杂度差了一个数量级,一个是平方级的,一个是对数级的。
平均时间复杂度
插入排序 O(n2)
冒泡排序 O(n2)
选择排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
归并排序 O(n log n)
基数排序 O(n)
希尔排序 O(n1.25)
取自"http://www.wiki.cn/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95"
不知道哪看到的了- -!
这里有分析。
http://hi.baidu.com/sodarfish/blog/item/47cd8b12b528dd56f819b892.html
c语言中如何排序?
在C语言中,可以使用多种排序算法来对数组进行排序。以下是几种常见的排序算法示例:1. 冒泡排序(Bubble Sort):```c void bubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { in...
C语言堆排序最坏的情况下比较次数最多要多少次?
O(n1og2n)在最坏情况下,冒泡排序所需要的比较次数为n(n-1)\//2;简单插入排序所需要的比较次数为n(n-1)\/2;希尔排序所需要盼的比较次数为0(n1.5);堆排序所需要的比较次数为0(nlog2n)。
c语言的两种排序?
输出:9 8 7 6 5 3 2 1 0 -4 代码:include<stdio.h> int main(int argc,const char*argv[]){ int num[10],i,j,k,l,temp;\/\/用一个数组保存输入的数据 for(i=0;i<=9;i++){ scanf("%d",&num);} \/\/用两个for嵌套循环来进行数据大小比较进行排序 for(j=0;j<9;j++){ ...
c语言一维数组冒泡排序
如果遇到相等的值不进行交换,那这种排序方式是稳定的排序方式。原理:比较两个相邻的元素,将值大的元素交换到右边思路:依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。(1)第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。(2)比较第2和第3个数,将小数 ...
比较abc三个数的大小,用C语言怎么表示?
2. 比较不同类型的数据:在C语言中,可以比较各种不同类型的数据,包括整数、浮点数和字符等。整数和浮点数之间的比较需要注意精度问题。在进行比较时,会进行隐式类型转换,但在某些情况下这可能会导致意外的结果。3. 比较和排序算法:比较是许多算法的基础,如排序和搜索。C语言提供了内置的排序函数,...
怎么用c语言程序比较五个数的大小,还要从大到小排序,求大神指点!_百度...
\/\/#include "stdafx.h"\/\/vc++6.0加上这一行.include "stdio.h"void main(void){ int a[5],i,j,k;printf("Type 5 integers...\\n");for(i=0;i<5;scanf("%d",a+i++));for(i=0;i<5;i++){ for(k=i,j=k+1;j<5;j++)if(a[k]<a[j]) k=j;if(k!=i){ j=a[...
C语言冒泡排序法是什么?
具体方法是:相邻数值两两交换。从第一个数值开始,如果相邻两个数的排列顺序与我们的期望不同,则将两个数的位置进行交换(对调);如果其与我们的期望一致,则不用交换。重复这样的过程,一直到最后没有数值需要交换,则排序完成。C语言常见的排序算法:1、冒泡排序 基本思想:比较相邻的两个数,如果...
C语言中选择排序和冒泡排序的区别是什么?哪位大侠教教小弟
冒泡法每次比较和移动相邻的两项 而选择排序每次交换当前项和第n项 我把代码写出来你就懂了:冒泡:fori:=1ton-1do if(a[i]>a[i+1])thenswap(i,i+1);选择:fori:=1ton-1do if(a[i]>a[n])thenswap(i,n);(swap表示交换)总的来说,两种排序比较的次数是相同的 但交换的次数,...
c语言冒泡排序
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端,就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。冒泡排序就是把小的元素往前调或者把大的元素往后调:比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的;...
c语言冒泡排序详解
到此第三轮就比较完了。第三轮的结果是找到了序列中第三大的那个数,并浮到了最右边第三个位置。第四轮:1) –58 和 21 比,–58<21,则不用交换位置。至此,整个序列排序完毕。从小到大的序列就是“–58 21 34 90 132”。从这个例子中还可以总结出,如果有 n 个数据,那么只需要比较 n–...
岛砌异丙: 现在流行的排序有:直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、堆排序、归并排序、基数排序.对n个记录进行选择排序的方法是:通过n-i次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)...
颍州区14727086474: C语言一个字符串排序比较程序,怎么写? - ?
岛砌异丙: 这个跟整数数组排序几乎没什么区别,无非就是把int类型变成char*类型而已,另外字符串比较不能直接用大于或小于等符号,而是用strcmp函数来取代 排序算法随意,喜欢冒泡排序的的用冒泡排序,喜欢快速排序的用快速排序,随你喜好
颍州区14727086474: 用C语言编写一个比较数的大小并排序的程序? - ?
岛砌异丙: #include<stdio.h> void BubbleStort() { int i,j; int arr[7]; printf("请输入要排数字:\n"); for(i=0;i<=6;i++) scanf("%d",&arr[i]); for(i=1;i<=6;i++) { for (j=0;j<=6-i;j++) { if(arr[j]>arr[j+1]) { int t; t=arr[j]; arr[j]=arr[j+1]; arr[j+1]=t; } }} printf("排序后的数...
颍州区14727086474: C语言中字符串排序的原理是什么 - ?
岛砌异丙: 从第一个字符开始一次比较,比较两个字符的ASCII值的大小. asd d 上面两个字符串,d的ASCII值大于a,所以 d 就排在 asd前面
颍州区14727086474: C语言数据排序 - ?
岛砌异丙: /*选择排序法:从小到大排列10个数并输出*/#include<stdio.h>#define N 10 //可修改输入个数 void main() { int i,a[N],t,j; for(i=0;i<N;i++) scanf("%d",&a[i]); //输入 for(j=1;j<N;j++) //N次比较 for(i=0;i<j;i++) //每趟中比j次if(a[i]>a[j]) //与a[i]后面的元素进行比较 { t=a[i];a[i]=a[j];a[j]=t; } printf("排序后:\n"); for(i=0;i<N;i++) printf("%d ",a[i]); printf("\n"); }
颍州区14727086474: C语言两个一维数组排序比较 - ?
岛砌异丙: 有区别,第一个程序中被比较的数是固定的,即min,运行时k=0,即min=22,那么从i=0,到i=4,运行后的数列第1个数会是9.第二个程序是一个排序,被比较的数是变动的,即数列第k个数在比较完以后,第k+1个以后的数都比第k个数大,当k=0时,运行后数列第一个数是2.
颍州区14727086474: C语言排序 - ?
岛砌异丙: //冒泡排序法 #include #include main() { int i,j,temp; int a[10]; for(i=0;i<10;i++) scanf ("%d,",&a[i]); for(j=0;j<=9;j++) { for (i=0;i<10-j;i++) if (a[i]>a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;} } for(i=0;i<10;i++) printf("%5d,",a[i] ); printf("\n"); system("pause"); return 0; }
颍州区14727086474: 用C语言如何对大量数字进行排序? - ?
岛砌异丙: 如果是C语言的话只能手写堆排序、归并排序或者快速排序等等 如果是用C++的话可以看下面: 10W量级直接考虑使用STL的sort函数,用法自行百度或者参见http://www.cplusplus.com/reference/algorithm/sort/ sort函数默认是升序排序,要降序排...
颍州区14727086474: c语言中排列大小的方法用中位数比较 - ?
岛砌异丙: //这个,听你的意思有点像是快速排序算法.可以百度下快速排序看看 void sort(int *a, int left, int right) {if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/{return ;}int i = left;int j = right;int key = a[left]; while...
颍州区14727086474: c语言,快速排序,在最坏条件下需要比较的次数为多少 - ?
岛砌异丙: 快速排序最坏的情况是初始序列已经有序,第1趟排序经过n-1次比较后,将第1个元素仍然定在原来的位置上,并得到一个长度为n-1的子序列;第2趟排序经过n-2次比较后,将第2个元素确定在它原来的位置上,又得到一个长度为n-2的子序列;以此类推,最终总的比较次数:C(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2 最坏的情况下,快速排序的时间复杂度为O(n^2)