数据结构C语言--三种以上的排序算法
刚做完的
#include
using namespace std;
void BiInsertsort(int r[], int n) //插入排序（折半）
{
for(int i=2;i<=n;i++)
{
if (r[i]<r[i-1])
{
r[0] = r[i]; //设置哨兵
int low=1,high=i-1; //折半查找
while (low<=high)
{
int mid=(low+high)/2;
if (r[0]<r[mid]) high=mid-1;
else low = mid+1;
}
int j;
for (j=i-1;j>high;j--) r[j+1] = r[j]; //后移
r[j+1] = r[0];
}
}
for(int k=1;k<=n;k++) cout<<r[k]<<" ";
cout<<"
";
}
void ShellSort ( int r[], int n) //希尔排序
{
for(int d=n/2;d>=1;d=d/2) //以d为增量进行直接插入排序
{
for (int i=d+1;i<=n;i++)
{
r[0] = r[i]; //暂存被插入记录
int j;
for( j=i-d; j>0 && r[0]<r[j]; j=j-d) r[j+d] = r[j]; //记录后移d个位置
r[j+d] = r[0];
}
}
for(int i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<"
";
}
void BubbleSort(int r[], int n) //起泡排序
{
int temp,exchange,bound;
exchange=n; //第一趟起泡排序的范围是r[0]到r[n-1]
while (exchange) //仅当上一趟排序有记录交换才进行本趟排序
{
bound=exchange;
exchange=0;
for (int j=1; j<bound; j++) //一趟起泡排序
if (r[j]>r[j+1])
{
temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
exchange=j; //记录每一次发生记录交换的位置
}
}
for(int i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<"
";
}
int Partition(int r[], int first, int end) //快速排序一次划分
{
int i=first; //初始化
int j=end;
r[0]=r[first];
while (i<j)
{
while (i<j && r[0]<= r[j]) j--; //右侧扫描
r[i]=r[j];
while (i<j && r[i]<= r[0]) i++; //左侧扫描
r[j]=r[i];
}
r[i]=r[0];
return i; //i为轴值记录的最终位置
}
void QuickSort(int r[], int first, int end) //快速排序
{
if (first<end)
{ //递归结束
int pivot=Partition(r, first, end); //一次划分
QuickSort(r, first, pivot-1);//递归地对左侧子序列进行快速排序
QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序
}
}
void SelectSort(int r[ ], int n) //简单选择排序
{
int i,j,index,temp;
for (i=1; i<n; i++) //对n个记录进行n-1趟简单选择排序
{
index=i;
for (j=i+1; j<=n; j++) //在无序区中选取最小记录
if (r[j]<r[index]) index=j;
if (index!=i)
{
temp=r[i];
r[i]=r[index];
r[index]=temp;
}
}
for(i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<"
";
}
void main()
{
const int numv=12;
int a[3][numv]={{0,6,13,19,23,37,39,41,45,48,58,86},{0,86,58,48,45,41,39,37,23,19,13,6},{0,23,13,48,86,19,6,41,58,37,45,39}};
int z1[numv],z2[numv];
int m,n;
cout<<"请选择测试数据类型：⑴正序 ⑵逆序 ⑶随机 [ 若跳出,请按⑷ ]" <<endl;
cin>>m;
while(m>0&&m<4)
{
cout<<"请选择排序算法：⑴直接插入排序 ⑵希尔排序 ⑶冒泡排序 ⑷快速排序
⑸简单选择排序"<<endl;
cin>>n;
switch(n)
{
case 1:
cout << "直接插入排序前：" << "
";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "
直接插入排序结果为：" << "
";
BiInsertsort(a[m-1],numv-1);
break;
case 2:
cout << "
希尔排序前：" << "
";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "
希尔排序结果为：" << "
";
ShellSort(a[m-1], numv-1);
break;
case 3:
cout << "
冒泡排序前：" << "
";
for(int k=1;k<numv;k++) cout<<a[m-1][k]<<" ";
cout << "
冒泡排序结果为：" << "
";
BubbleSort(a[m-1], numv-1);
break;
case 4:
cout << "
快速排序前：" << "
";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "
快速排序结果为：" << "
";
QuickSort(a[m-1],0,numv-1);
for(int i=1;i<numv;i++)
cout<<a[m-1][i]<<" ";
cout<<"
";
break;
case 5:
cout << "
简单选择排序前：" << "
";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "
简单选择排序结果为：" << "
";
SelectSort(a[m-1],numv-1);
break;
default:
cout<<"输入错误！"<<endl;
}
m=0;
cout<<"请选择测试数据类型：⑴正序 ⑵逆序 ⑶随机 [ 若跳出,请按⑷ ]" <<endl;
cin>>m;
}
if(m==4) cout<<"(*^__^*) 再见！"<<endl;
else cout<<"输入错误！"<<endl;
}
这题你只要把每个算法的程序代码看一下，在计算下就行
冒泡排序：两个循环，从1加到N，(1+N)N/2
=
500500,最坏交换情况是每次判断都要交换，既500500*3次
选择排序：也是两个循环，比较次数跟冒泡排序一样500500，但是这个只要底层循环交换，既只需1000*3
=
3000次赋值。
插入排序：循环次数一样500500，但是这个最坏情况是每比较一次就赋值一次，既需500500次赋值
希尔排序：时间复杂度是N^1.3倍，比较次数和赋值应该是1000^1.3次方。
归并排序和快速排序，你去查查它的时间复杂度是怎么算，O(lgN*N),好像有系数，算法导论那本书上有，现在不记得是多少了。
希望能帮到你，
void QSort(int a[], int l, int r) //单关键字交换法快排
{
int i = l, j = r, mid = (i + j) / 2; //二分[i,j]区间
while (i <= j) //让a[mid]左边都比a[mid]小，右边都比a[mid]大
{
while (a[i] < a[mid]) //找到一个元素a[i]比a[mid]小
i++;
while (a[j] > a[mid]) //找到一个元素a[j]比a[mid]大
j--;
if (i <= j) //交换a[i]和a[j]，并让指针向中间靠拢
Swap(a[i++], a[j--]);
}
if (i < r)
QSort(a, i, r); //对右区间[i,r]递归排序
if (l < j)
QSort(a, l, j); //对左区间[l,j]递归排序
}
归并排序：
void Merge(int a[], int l, int m, int r) //将a中区间[l, r]合并为有序
{
int x[101], y[101]; //循环变量
int i, j, k;
int l1 = m - l + 1, l2 = r - m; //l1表示区间[l, m]的长度，l2表示区间[m + 1, r]的长度
for (i = 1; i <= l1; i++) //将a中区间[l, m]复制到x中
{
x[i] = a[l + i - 1];
}
for (i = 1; i <= l2; i++) //将a中区间[m + 1, r]复制到y中
{
y[i] = a[m + i];
}
x[l1 + 1] = MaxInt; //设置一个很大的数作为结束标志
y[l2 + 1] = MaxInt;
i = 1;
j = 1;
for (k = l; k <= r; k++) //将两个区间合并成为一个有序区间
{
if (x[i] <= y[j])
{
a[k] = x[i++];
}
else
{
a[k] = y[j++];
}
}
}
void MergeSort(int a[], int l, int r) //对a数组的[l, r]区间排序
{
int m;
if (l < r)
{
m = (l + r) / 2; //二分区间[l, r]
MergeSort(a, l, m); //递归二分区间[l, m]
MergeSort(a, m + 1, r); //递归二分区间[m + 1, r]
Merge(a, l, m, r); //合并区间[l, m]和[m + 1, r]
}
}
二叉排序树排序：
struct BinaryTree //二叉树结构
{
int data, p, l, r; //data数值域，p父节点编号，l左儿子编号，r右儿子编号
};
int root = 0;
void Init(BinaryTree a[], int &n) //读入数据域，并初始化树
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].data;
a[i].p = a[i].l = a[i].r = -1;
}
}
void Insert(BinaryTree a[], int i) //在二叉查找树中插入编号为 i 的节点
{
int parent = -1, x = a[1].p; //parent 始终指向 x 的父节点编号
while (x != -1) //向下搜索，直到找到最下一层
{
parent = x;
if (a[i].data < a[x].data)
x = a[x].l;
else
x = a[x].r;
}
a[i].p = parent; //把第 i 号节点的父亲指向parent
if (parent != -1) //判断树是否为空
{
if (a[i].data < a[parent].data) //向父节点插入儿子
a[parent].l = i;
else
a[parent].r = i;
}
else //为空就以 i 节点为根节点
a[root].p = i;
}
void BuildTree(BinaryTree a[], int n) //建立二叉查找树
{
root = 1;
for (int i = 1; i <= n; i++) //依次插入 n 个节点到二叉查找树
{
Insert(a, i);
}
a[root].p = -1;
}
void Sort(BinaryTree a[], int i) //中序遍历输出
{
if (a[i].l > -1) //递归遍历左儿子
Sort(a, a[i].l);
cout << a[i].data << " "; //输出节点
if (a[i].r > -1) //递归遍历右儿子
Sort(a, a[i].r);
}
堆排序：
void Heap(int a[], int n, int p) //维护最大（最小）堆，维护以P为根的堆
{
int l = p * 2, r = l + 1, t = p; //左儿子编号为2P，右儿子为2P+1，初始化根节点P为最大
if ((l <= n) && (a[l] > a[p])) //找一个最大的数，维护最大堆（改为<就是维护最小堆）
t = l;
if ((r <= n) && (a[r] > a[t])) //找一个最大的数，维护最大堆（改为<就是维护最小堆）
t = r;
if (p != t) //如果根节点不是最大，和最大的交换，再递归维护堆
{
Swap(a[p], a[t]);
Heap(a, n, t);
}
}
void HeapSort(int a[], int n)
{
int i;
for (i = n / 2; i >= 1; i--) //n / 2开始必然是根节点，依次调用Heap，建立一个最大堆
Heap(a, n, i);
for (i = n; i >= 2; i--) //每次将堆顶和当前堆最后一个节点(i)交换，然后将[1, i - 1]重新堆化
{
Swap(a[i], a[1]);
Heap(a, i - 1, 1);
}
}
插入排序：
void InsertionSort(int a[], int l, int r) //对区间[l, r]执行插入排序
{
int i, j, t;
for (i = l + 1; i <= r; i++)
{
j = i - 1;
t = a[i];
while ((j >= l) && (a[j] > t)) //后移操作，并找到正确的位置
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = t;
}
}
以上所有的Swap函数的意思都是交换两个变量。
百度百科上有。
排序：http://baike.baidu.com/view/58783.htm?fr=ala0_1
快排：http://baike.baidu.com/view/115472.htm
... ...
计算机二级C语言考试内容有哪些?
1、根据新大纲的要求，二级(C语言)考试分为理论考试和上机考试两部分，必须都通过考试才能算合格。2、考试内容分为C语言程序设计(顺序结构、选择结构、循环结构、函数、指针、数组、字符串、编译预处理、作用域、结构体、共用体、文件等)和公共基础(数据结构、程序设计、软件工程和数据库)。
c语言比较abc三个数大小
程序首先检查a是否大于b和c，如果是，那么a就是最大的数，并且程序会打印出a是最大的数。如果a不是最大的数，那么程序会继续检查b是否大于a和c，如果是，那么b就是最大的数。如果b也不是最大的数，那么程序会继续检查c是否大于a和b，如果是，那么c就是最大的数。3、多分支结构：如果一个数...
C语言中如何输出一个三位数
代码如下：include<stdio.h> int main(void){ int number;int units, tens, hundreds; \/\/定义三个变量分别存储个位、十位和百位上的数字 scanf("%d", &number); \/\/读入一个三位数 hundreds = number \/ 100; \/\/ 一个三位数除以100的整数商，即百位上的数字 tens = (number % 100) \/ 10;...
c语言程序设计编程题目:请 :编写完成对学生相关信息的要求:1.定义一...
include <stdio.h> include <stdlib.h> define STU_NUM 10 \/*宏定义学生的数量*\/ struct student \/*定义一个结构体用来存放学生学号、三门课成绩、总分及平均成绩*\/ { char stu_id[20]; \/*学生学号；*\/ float score[3]; \/*三门课成绩；*\/ float total; \/*总成绩；*\/ float aver; \/*...
c语言结构程序设计。根据要求定义函数,并输出结果。
include <stdio.h> define MAX 50 struct student { char no[10];char name[10];float score[3];}stu[MAX];float course_ave[3] = {0};float stu_ave[MAX] = {0};\/\/ 录入学生成绩 void input(int n) { int i;for(i=0; i<n; i++) { scanf("%s %s", stu[i].no,stu[i...
c语言编程:建立一个结构体数组?
分析题意:一、要定义两个结构体，一个是日期年月日，一个是员工。二、程序包含三个功能：1、结构数组的输入。2、结构数组的输出。3、统计平均工资。根据编程习惯，三功能要写成独立函数，方便扩展和调用。ps:员工数量定义成常量，也为编程习惯，便于修改。另外，日期验证我只写了月份检测给你参考。需...
c语言如何计算三角形的面积
计算三角形面积的c语言程序如下：计算三角形面积语言程序：include #include int main（）double a，b，c，S，area；printf（根据三角形的三边长计算它的面积n）；printf（输入边长a:）；scanf（%lf，&a）；printf（输入边长b:）；scanf（%lf，&b）；printf（输入边长c:）；scanf（%lf，&c）。S=...
没有电脑可以学习“c语言”吗?
当前，前提条件，应该灵活的掌握这三部分的基本知识，将第一部分应用自如后，再进行知识点的连接和贯穿。数组：数组从访问的效率来看可以说是最快的数据结构了，根据下标值可以真正访问到数组中的某块空间，而数组的连续存储也成为我们编程非常便利的地址使用的条件。指针：指针可以说是C语言的精华所在，...
C语言代码组成 - BSS、Data、Stack、Heap、Code、Const
一段C语言经过编译连接后，成为一段可以运行的代码，可运行的代码可以分为以下四个部分组成：全局变量\/静态变量区、堆、栈、代码区。其中全局变量\/静态变量区又分为未初始化变量区和初始化变量区，代码区又分为代码和常量区。即汇总下来，代码可以分为6部分组成，包括：BSS区（未初始化的全局变量\/静态...
学习C语言需要掌握哪些基本知识?
\/\/此声明声明了拥有3个成员的结构体,分别为整型的a,字符型的b和双精度的c \/\/同时又声明了结构体变量s1 \/\/这个结构体并没有标明其标签 struct { int a; char b; double c; } s1; \/\/此声明声明了拥有3个成员的结构体,分别为整型的a,字符型的b和双精度的c \/\/结构体的标签被命名为SIMPLE,没有声明变...
从逄二十： 快速排序:void QSort(int a[], int l, int r) //单关键字交换法快排 { int i = l, j = r, mid = (i + j) / 2; //二分[i,j]区间 while (i <= j) //让a[mid]左边都比a[mid]小,右边都比a[mid]大 { while (a[i] < a[mid]) //找到一个元素a[i]比a[mid]小 i++; while (a[j] > a[mid]) //找...
赛罕区13424028821： c语言给n个数排序 - ？
从逄二十： 常用的排序算法有:冒泡排序、选择排序、堆排序、SHELL排序、快速排序、归并排序、磁盘排序等等.但是每种排序算法都是各有优缺点.现在已经有 C 语言版的数据结构,且具有 C 语言源程序的教材可供参考.现在的主要任务是:只需要自己在程序开头数据类型定义部分、以及子函数调用部分,根据自己的任务需求,把教材上的数据类型,修改为自己需要的数据类型即可,非常容易.
赛罕区13424028821： 数据结构排序算法有哪些常用的 - ？
从逄二十： 最常用的是快速排序,基数排序,计数排序,归并排序,堆排序,(偶尔还有插入排序) 都有各自的应用,快排就是单纯的快,但是特殊数据下复杂度会退化 基数排序可以配合一些特定的算法,譬如后缀数组的构建 计数排序简单且常用,通常排序值域小但是数据量大的情况 归并直接用来排序并不多,但是可以用来求解一些其他问题,本身的思想也非常重要,有很多拓展的算法(不是排序算法) 堆排序胜在稳定,不论数据如何最坏都是O(nlogn),一般情况比快速排序慢些,但是极端情况下表现十分优秀,常用来配合快速排序,优化其稳定性 插入排序适合极少量数据的排序(几个到十几个),速度要比这些高级算法快一些
赛罕区13424028821： 数据结构中几种常见的排序算法之比较 - ？
从逄二十： 实话实说,关于数据结构中几种常见的排序算法(例如:冒泡排序、SHELL排序、归并排序、快速排序等)的性能好坏,还不只是学好了数据结构这门课程就能够解决的问题,还必须要学习好、且精通掌握计算机软件专业的另外一门非常重要的课程,才能够解决这个问题.即:计算机算法复杂性理论.只有同时把这门课程学好了,那么才能够真正掌握数据结构中的各种排序算法、以及各种查找算法中所有涉及到的:比较次数、以及交换次数,最终才能够根据具体的开发软件规模的不同,选择出一个适合开发该软件的最佳算法.
赛罕区13424028821： 求数据结构课程设计(C语言)—排序综合!利用随机函数产生N个随机整数(2万以上),至少使用三种方法实现 - ？
从逄二十： 冒泡法#include#include#include#define N 10000void init_a...
赛罕区13424028821： C语言实现七种排序算法的 演示代码!!! - ？
从逄二十： (1)“冒泡法” 冒泡法大家都较熟悉.其原理为从a[0]开始,依次将...
赛罕区13424028821： 数据结构中排序方法有多少种 - ？
从逄二十： 1、插入排序(直接插入排序和希尔排序) 2、选择排序(直接选择排序和堆排序) 3、交换排序(冒泡排序和快速排序) 4、归并排序 5、基数排序 直接插入排序:逐个将后一个数加到前面的排好的序中.在直接插入排序过程中,对其中一个记...
赛罕区13424028821： C语言数据结构排序 - ？
从逄二十： 这个问题简单,楼主的意思就是显示每一步执行后的中间结果,那只要加几个输出语句就可以了,过程很简单的,为简化起见用最常用的选择排序.程序在wn-tc和Dev-c++下调试通过. #include<stdio.h> #include<conio.h> #define MAX 50 main...
赛罕区13424028821： 用c语言排序有几种方法? - ？
从逄二十： 冒泡 选择
赛罕区13424028821： 数据结构课程设计(C版语言)二叉排序树算法 - ？
从逄二十： #include<stdio.h>#include<stdlib.h>#include<conio.h> typedef int DataType; //定义数据类型,以int为例 struct BSTNode //定义二叉排序树节点类型 { DataType data; struct BSTNode *lchild,*rchild; }; int insert(struct BSTNode **root,DataType data...
