堆排序算法流程图
⑴ 排序算法的N-S流程图
我敲代码敲了一年都未做过流程图啊，上机考试时老师甚至都不让我们带草稿纸，说用不着(真正的程序员是不需要流程图的)
以下是我以前敲过的代码，随便复制了一些
//直接插入排序
#include<iostream>
using namespace std;
void Print(int *ar,int n){
int i;
for(i=1;i<=n;i++)
cout<<ar[i]<<" ";
cout<<endl;
}
int main(){
int i,j,*ar,n;
cin>>n;
ar=new int[n+1];
for(i=1;i<=n;i++)
cin>>ar[i];
for(i=2;i<=n;i++){
if(ar[i-1]>ar[i]){
ar[0]=ar[i];
for(j=i-1;ar[0]<ar[j];j--)
ar[j+1]=ar[j];
ar[j+1]=ar[0];
}
Print(ar,n);
}
cout<<endl;
return 0;
}
//折半插入排序
#include<iostream>
using namespace std;
void Print(int *ar,int n){
int i;
for(i=1;i<=n;i++)
cout<<ar[i]<<" ";
cout<<endl;
}
int main(){
int i,n,*ar,h,l,m;
cin>>n;
ar=new int[n+1];
for(i=1;i<=n;i++)
cin>>ar[i];
for(i=2;i<=n;i++){
ar[0]=ar[i];
l=1;
h=i-1;
while(l<=h){
m=(l+h)/2;
if(ar[0]<ar[m])
h=m-1;
else
l=m+1;
}
for(m=i;m>h+1;m--)
ar[m]=ar[m-1];
ar[h+1]=ar[0];
Print(ar,n);
}
return 0;
}
//希尔排序
#include<iostream>
using namespace std;
void Print(int *ar,int n){
int i;
for(i=1;i<=n;i++)
cout<<ar[i]<<" ";
cout<<endl;
}
void ShellInsert(int *ar,int n,int dk){
int i,j;
for(i=1+dk;i<=n;i++){
if(ar[i-dk]>ar[i]){
ar[0]=ar[i];
for(j=i-dk;j>0&&ar[0]<ar[j];j-=dk)
ar[j+dk]=ar[j];
ar[j+dk]=ar[0];
}
}
}
void ShellSort(int *ar,int n){
int i;
for(i=n/2;i>0;i/=2){ //以n/2为dk
ShellInsert(ar,n,i);
Print(ar,n);
}
}
int main(){
int n,*ar,i;
cin>>n;
ar=new int[n+1];
for(i=1;i<=n;i++)
cin>>ar[i];
ShellSort(ar,n);
return 0;
}
//冒泡排序
#include<iostream>
using namespace std;
void Print(int *ar,int n){
int i;
for(i=0;i<n;i++)
cout<<ar[i]<<" ";
cout<<endl;
}
int main(){
int n,*ar,t,i,j;
bool b=0;
cin>>n;
ar=new int[n];
for(i=0;i<n;i++)
cin>>ar[i];
for(i=1;i<n;i++){
b=0;
for(j=0;j<n-i;j++){
if(ar[j]>ar[j+1]){
t=ar[j];
ar[j]=ar[j+1];
ar[j+1]=t;
b=1;
}
}
Print(ar,n);
if(b==0)
break;
}
return 0;
}
//快速排序
#include<iostream>
using namespace std;
void Print(int *ar,int n){
int i;
for(i=0;i<n;i++)
cout<<ar[i]<<" ";
cout<<endl;
}
int Por(int *ar,int l,int h){
int k=ar[l];
while(l<h){
while(l<h&&k<=ar[h])
h--;
ar[l]=ar[h];
while(l<h&&k>=ar[l])
l++;
ar[h]=ar[l];
}
ar[l]=k;
return l;
}
void QSort(int *ar,int l,int h,int n){
if(l<h){
int m=Por(ar,l,h);
Print(ar,n);
QSort(ar,l,m-1,n);
QSort(ar,m+1,h,n);
}
}
int main(){
int i,*ar,n;
cin>>n;
ar=new int[n];
for(i=0;i<n;i++)
cin>>ar[i];
QSort(ar,0,n-1,n);
return 0;
}
//简单选择排序
#include<iostream>
using namespace std;
void Print(int *ar,int n){
int i;
for(i=0;i<n;i++)
cout<<ar[i]<<" ";
cout<<endl;
}
int main(){
int i,j,t,*ar,n,max;
cin>>n;
ar=new int[n];
for(i=0;i<n;i++)
cin>>ar[i];
for(i=0;i<n-1;i++){
max=i;;
for(j=i+1;j<n;j++){
if(ar[max]>ar[j])
max=j;
}
t=ar[max];
ar[max]=ar[i];
ar[i]=t;
Print(ar,n);
}
return 0;
}
//堆排序
#include<iostream>
using namespace std;
void Print(int *ar,int n){
int i;
for(i=1;i<=n;i++)
cout<<ar[i]<<" ";
cout<<endl;
}
void HeapAdjust(int *ar,int i,int n){
int j,t=ar[i];
for(j=i*2;j<=n;j*=2){
if(j<n&&ar[j]<ar[j+1])
j++;
if(t>ar[j])
break;
ar[i]=ar[j];
i=j;
}
ar[i]=t;
}
void HeapSort(int *ar,int n){
int i;
for(i=n/2;i>=1;i--)
HeapAdjust(ar,i,n);
Print(ar,n);
for(i=n;i>1;i--){
ar[0]=ar[i];
ar[i]=ar[1];
ar[1]=ar[0];
HeapAdjust(ar,1,i-1);
Print(ar,n);
}
}
int main(){
int *ar,i,n;
cin>>n;
ar=new int[n+1];
for(i=1;i<=n;i++)
cin>>ar[i];
HeapSort(ar,n);
return 0;
}
//非递归归并排序
#include<iostream>
using namespace std;
void Print(int *ar,int n){
int i;
for(i=0;i<n;i++)
cout<<ar[i]<<" ";
cout<<endl;
}
void MergeSort(int *ar,int n){
int i,*ar2,p,q,t,l,h,m;
ar2=new int[n];
for(i=1;i<n;i*=2){
l=0;
while(l<n){
p=t=l;
q=m=l+i;
if(m>=n)
break;
h=m+i;
if(h>n)
h=n;
while(p<m||q<h){
if(q>=h||(p<m&&ar[p]<=ar[q]))
ar2[t++]=ar[p++];
else
ar2[t++]=ar[q++];
}
l=h;
}
for(t=0;t<h;t++)
ar[t]=ar2[t];
Print(ar,n);
}
}
int main(){
int i,n,*ar;
cin>>n;
ar=new int[n];
for(i=0;i<n;i++)
cin>>ar[i];
MergeSort(ar,n);
return 0;
}
//基数排序
#include<iostream>
using namespace std;
typedef struct{
int num[10];
int next;
}Node;
Node sq[100];
int e[100];
int f[100];
void Distribute(int i,int n){
int t,j,k=sq[0].next;
for(j=0;j<n;j++){
t=sq[k].num[i];
if(f[t]==0)
f[t]=k;
else
sq[e[t]].next=k;
e[t]=k;
k=sq[k].next;
}
}
void Collect(){
int i,j;
for(i=0;i<10;i++){
if(f[i]!=0){
sq[0].next=f[i];
j=e[i];
break;
}
}
for(i++;i<10;i++){
if(f[i]!=0){
sq[j].next=f[i];
j=e[i];
}
}
}
void Print(int max,int n){
int i,j,k=sq[0].next;
for(i=0;i<n;i++){
for(j=max-1;j>=0;j--)
cout<<sq[k].num[j];
cout<<" ";
k=sq[k].next;
}
cout<<endl;
}
void RadixSort(int max,int n){
int i,j;
for(i=0;i<=n;i++)
sq[i].next=i+1;
for(i=0;i<max;i++){
for(j=0;j<10;j++)
e[j]=f[j]=0;
Distribute(i,n);
Collect();
Print(max,n);
}
}
int main(){
int i,j,imp,n,max=0;
cin>>n;
for(i=1;i<=n;i++){
cin>>imp;
for(j=0;j<10&&imp!=0;imp/=10)
sq[i].num[j++]=imp%10;
if(max<j)
max=j;
while(j<10)
sq[i].num[j++]=0;
}
RadixSort(max,n);
return 0;
}
⑵ 堆排序法
堆排序法，就是通过堆这种数据结构来实现排序，算法复杂度为O(nlogn)。
堆是一种完全二叉树且所有的父节点均大于（或小于）其子节点。
堆排序就是将所有待排序的元素组成一个堆，然后不断弹出堆顶的元素并调用函数维持堆序，直到所有元素均被弹出后，排序完成。被弹出的元素序列即一个有序数列。
维持堆序的一般做法是这样：
当一个节点被插入时，将该节点放在堆的末尾（这是为了保证堆是完全二叉树）然后将该节点与它的父节点比较，看该节点是否大于（或小于）其父节点，即判断当前的堆是否满足堆序。如果不满足，则将该节点与其父节点交换。再将该节点与其新的父节点做比较，依此类推，直到该节点不再需要与其父节点交换为止。（即满足堆序时停止）
当一个根节点被弹出（即被从堆中删除）时，将堆最尾部的节点移动到头结点的位置，然后将该节点不断与其子节点比较，如果不符合堆序则交换，直到符合堆序为止。
以下是我自己写的一个C++的堆排序的程序，希望对你理解该算法有帮助。
#include<iostream>
using namespace std;
int heap[10000],size;
void Percup(int s)
{
if(s==1)
return ;
if(heap[s/2]<heap[s])
{
swap(heap[s/2],heap[s]);
Percup(s/2);
}
}
void Percdown(int s)
{
if(s*2+1<=size&&heap[s*2+1]>heap[s])
{
swap(heap[s*2+1],heap[s]);
Percdown(s*2+1);
}
if(s*2<=size&&heap[s*2]>heap[s])
{
swap(heap[s*2],heap[s]);
Percdown(s*2);
}
}
void Insert(int k)
{
heap[++size]=k;
Percup(size);
}
int Pop()
{
int h=heap[1];
heap[1]=heap[size--];
Percdown(1);
return h;
}
int main()
{
int a,n,i;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a;
Insert(a);
}
for(i=0;i<n;i++)
cout<<Pop()<<' ';
system("pause");
return 0;
}
⑶ 实现多种排序算法
#include "stdio.h"
#include "conio.h"
#define MAXSIZE 20
#define LT(a,b) ((a)<(b))
typedef int KeyType;
typedef int InfoType;
typedef struct{
KeyType key;
InfoType otherinfo;
}RedType;
typedef struct{
RedType r[MAXSIZE+1];
int length;
}SqList;
void InsertSort(SqList *L) /*简单插入排序*/
{ int i,j;
for(i=2;i<=L->length;++i)
if(LT(L->r[i].key,L->r[i-1].key)){
L->r[0]=L->r[i];
for(j=i-1; LT(L->r[0].key,L->r[j].key); --j)
L->r[j+1]=L->r[j];
L->r[j+1]=L->r[0];
}
}
void MaopaoSort(SqList *L) /*冒泡排序*/
{ int i,j,t,n;
n=L->length;
for(i=1;i<n; i++)
for(j=1;j<=n-i;j++)
if(L->r[j].key>=L->r[j+1].key)
{t=L->r[j].key;L->r[j].key=L->r[j+1].key;L->r[j+1].key=t;}
}
/*快速排序*/
/* QuickSort related function */
int Partition(SqList *L,int low,int high)
{
int pivotkey;
L->r[0]=L->r[low];
pivotkey=L->r[low].key;
while(low<high){
while(low<high&&L->r[high].key>=pivotkey) --high;
L->r[low]=L->r[high];
while(low<high&&L->r[low].key<=pivotkey) ++low;
L->r[high]=L->r[low];
}
L->r[low]=L->r[0];
return low;
}
void QSort(SqList *L,int low,int high)
{
int pivotloc;
if(low<high){
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}
/* End QuickSort related function*/
void merge_two(RedType a[],RedType b[],int i,int n,int m) /*归并排序*/
{ int k,j;
for(j=n+1,k=i;i<=n&&j<=m;++k){
if(a[i].key<a[j].key) b[k].key=a[i++].key;
else b[k].key=a[j++].key;
}
if(i<=n) for(;i<=n;i++,k++)b[k].key=a[i].key;
if(j<=m)for(;j<=m;j++,k++)b[k].key=a[j].key;
}
void print(SqList *L,int n)
{
int i;
printf("\nN=%d\n ",n);
for(i=1;i<=L->length;i++)
printf("%5d",L->r[i].key);
}
void Mergesort(SqList *L)
{ int n=1,i,m;
RedType B[100];
while(n<=L->length){
i=1;
while((i+n)<=L->length){
if((i+2*n)<=L->length) m=i+2*n-1;
else m=L->length;
merge_two(&L->r[0],B,i,i+n-1,m);
i=i+2*n;
}
for(i=1;i<=m;i++) /* back B to list*/
L->r[i].key=B[i].key;
print(L,n);
n=2*n;
}
}
typedef SqList HeapType; /*堆排序*/
void HeapAdjust(HeapType *H,int s,int m)
{
RedType rc;
int j;
rc=H->r[s];
for(j=2*s;j<=m;j*=2){
if(j<m&<(H->r[j].key,H->r[j+1].key)) ++j;
if(!LT(rc.key,H->r[j].key)) break;
H->r[s]=H->r[j];
s=j;
}
H->r[s]=rc;
}
void HeapSort(HeapType *H)
{
RedType t;
int i;
for(i=H->length/2;i>0;--i)
HeapAdjust(H,i,H->length);
for(i=H->length;i>1;--i){
t=H->r[1];
H->r[1]=H->r[i];
H->r[i]=t;
HeapAdjust(H,1,i-1);
}
}
main()
{
int a[]={49,38,65,97,76,13,27,49};
int i,k;
SqList s;
clrscr();
printf("\n\tThe record to be sort: ");
for(i=1;i<9;i++)
{
s.r[i].key=a[i-1];
printf("%5d",a[i-1]);
}
s.length=i-1;
printf("\n");
printf("\n\t1.Insert Sort");
printf("\n\t2.Maopao Sort");
printf("\n\t3.Quick Sort");
printf("\n\t4.Merge Sort");
printf("\n\t5.HeapSort");
printf("\n\tPress 1..5 to select a function!\n");
scanf("%d",&k);
switch(k){
case 1:
InsertSort(&s); /*简单插入排序*/
break;
case 2:
MaopaoSort(&s); /*冒泡排序*/
break;
case 3:
QuickSort(&s); /*快速排序*/
break;
case 4:
Mergesort(&s); /*归并排序*/
break;
case 5:
HeapSort(&s); /*堆排序*/
break;
default:printf("No function which you select.\n");
}
printf("\n\tThe records be sorted: ");
for(i=1;i<9;i++)
printf("%5d",s.r[i].key);
printf("\n\n\tPress any key to exit.\n");
getch();
}
给你一个用c写的
⑷ 跪求选择排序流程图
1、选择排序流程图：
(4)堆排序算法流程图扩展阅读：
基本选择排序：
选择排序输出的是原序列的一个重排＜a1＊，a2＊，a3＊，．．．，an＊＞；，使得a1＊＜＝a2＊＜＝a3＊＜＝．．．＜＝an＊
排序算法有很多，包括插入排序，冒泡排序，堆排序，归并排序，选择排序，计数排序，基数排序，桶排序，快速排序等。插入排序，堆排序，选择排序，归并排序和快速排序，冒泡排序都是比较排序，它们通过对数组中的元素进行比较来实现排序，其他排序算法则是利用非比较的其它方法来获得有关输入数组的排序信息。
思想
n个记录的文件的直接选择排序可经过n－1趟直接选择排序得到有序结果：
①初始状态：无序区为R［1．．n］，有序区为空。
②第1趟排序
在无序区R［1．．n］中选出关键字最小的记录R［k］，将它与无序区的第1个记录R［1］交换，使R［1．．1］和R［2．．n］分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R［1．．i－1］和R（i．．n）。该趟排序从当前无序区中选出关键字最小的记录R［k］，将它与无序区的第1个记录R交换，使R［1．．i］和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。［1］
解释
对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟它的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置（下标），
等到循环结束的时候，应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟它交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让它跟数组中第二个元素交换一下值，以此类推。
⑸ 如何轻松考过计算机二级
方法/步骤
全国计算机二级等级考试分为两个部分，第一项为二级公共基础，这是所有考生都要考的，第二项为你所选的分类，如c语言程序设计等等。
就我考试的经验来看，二级公共基础为最易得分项，主要考察考生对概念的理解及掌握。下面为我总结的二级公共基础中易考及必会的内容，我相信只要掌握了它，二级公共基础这项就可以轻松过关啦。
一。数据结构与算法：
算法的定义
算法是指解决方案的准确而完整的描述，是一系列解决问题的清晰指令。算法 ≠ 程序。
算法的5大特征
1. 至少1个输出：任何算法，必须有输出结果。2. 至少0个输入，足够的情报：对于复杂算法，情报越充足，效果越好。3. 有穷性：算法能在有限的执行步骤内、有限的时间内执行结束。4. 可行性：算法的每一个步骤都必须能够翻译成计算机可执行的基本操作。5. 确定性：算法的每一个步骤都必须描述准确，没有歧义。
算法的复杂度
【时间复杂度】以基本操作次数的数量级计数，不以秒计数。常见复杂度（越小越快）：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)【空间复杂度】算法执行过程中的空间开销。【二者关系】虽然算法中常常会以牺牲空间的方式来换取时间效率，但一般认为二者没有必然关系。
数据结构的定义
数据结构是指计算机组织、存储数据的方式。数据结构可分为逻辑结构和存储结构。其中：1. 逻辑结构又分为线性结构和非线性结构。2. 存储结构又分为顺序存储结构和链式存储结构
逻辑结构
逻辑结构不关心数据如何存储，只关心数据的组织方式。逻辑结构可分为线性结构和非线性结构。典型线性结构：栈、队列典型非线性结构：树（二叉树）、网状图
存储结构
存储结构不关心数据如何组织，只关心数据的存储方式。存储结构又分为顺序存储结构和链式存储结构。【顺序存储结构】1. 所有元素在内存中按顺序排列2. 查找、修改比较不方便3. 插入、删除比较方便【链式存储结构】1. 所有元素在内存中随机分布2. 插入、删除比较不方便3. 查找、修改比较方便4. 由于要存储下一元素的地址，所以需要更多的存储空间【二者关系】二者没有必然关系。
基本概念
1. 栈属于逻辑结构的概念，属于线性结构。2. 栈既可以用顺序存储结构实现，也可以用链式存储结构实现。3. 栈的特点是先进后出（FILO）。4. 进出过程中，栈底指针不变，栈顶指针移动。
计算规则
视栈顶和栈底指针的指向规则而定。一般的，栈底指向首元素的前一位置（比如0），栈顶指针指向尾元素（比如5），即栈中1、2、3、4、5各存储了一个数据。此时：栈中元素个数=栈顶指针-栈底指针（比如5-0=5）
基本概念
1. 队列属于逻辑结构的概念，属于线性结构。2. 队列既可以用顺序存储结构实现，也可以用链式存储结构实现。3. 队列的特点是先进先出（FIFO）。4. 队头负责出队，队尾负责入队。
循环队列
循环队列是专门针对顺序存储结构空间固定的特点而设计的，所以一般认为循环队列是顺序存储结构。其核心原理是：当队尾到达队列最大位置、而队头不在最小位置时如果继续入队，则队尾移至队列最小位置，从头开始移动，形成循环。出队时同理。
计算规则
视栈顶和栈底指针的指向规则而定。一般的，队头指向首元素的前一位置，队尾指针指向尾元素。假设队列容量为20：1. 若队尾>队头（比如队尾为7，队头为2）：队列元素个数=队尾指针-队头指针（7-2=5）2. 若队头>队尾（比如队尾为2，队头为7）：队列元素个数=队尾指针-队头指针+队列容量（2-7+20=15）其中，第二种情况只有循环队列中才会出现。
基本概念
1. 一个二叉树只有一个根节点。2. 在二叉树中，任何一个节点最多只能有2个子节点。3. 一个节点有几个子节点，则度为几。度为0的节点称为叶子节点。
常用公式
1. 第n层的节点数最多为2^(n-1)个。2. 层数为n的二叉树，总节点数最多为2^n-1个。3. 叶子节点数 = 度为2的节点数+14. 二叉树节点总数 = 度为2的节点数 + 度为1的节点数 + 叶子节点数
遍历规则
先序遍历：父节点、左子树、右子树中序遍历：左子树、父节点、右子树后序遍历：左子树、右子树、父节点其中左右子树按此规则继续拆分，拆分过程中也按其对应规则遍历，直到不能再拆分为止。
顺序查找
其算法复杂度为O(n)，长度为n的线性表，最多需要n次才能找到指定元素。
顺序查找最大/最小值
长度为n的线性表，所有元素随机排列，最多需要n-1次才能找到最大/最小值。
二分查找
其算法复杂度为O(logn)，长度为n的线性表，最多需要logn次就能找到指定元素。
二分查找使用条件
1. 使用顺序存储结构（如数组）。2. 所有元素按序排列。
按原理分类
交换类：冒泡排序、快速排序选择类：简单选择排序、堆排序插入类：简单插入排序、希尔排序
按稳定性分类
稳定：冒泡排序、简单插入排序……不稳定（快选希堆）：快速排序、简单选择排序、希尔排序、堆排序
按算法复杂度
O(n^2)：冒泡排序、简单选择排序、简单插入排序O(nlogn)：快速排序、堆排序、希尔排序在一般情况下，快速排序是已知常用算法中效率最高的。在最坏情况下，快速排序的算法复杂度是O(n^)2。
二。软件工程：
基本概念
可行性研究主要考虑：经济、技术、法律。需求分析阶段最重要的文档：《软件需求规格说明书》。《软件需求规格说明书》的任务是统一认识，所以必须追求准确，消灭歧义。
数据流图（DFD）
箭头：数据流圆形、椭圆形：数据的加工方框：系统和环境的接口半开口的方框、双杠：数据的存储文件
数据字典
1. 是数据流图的重要补充2. 应该包含数据流图中提到的所有数据
概要设计
耦合性：模块之间的关联程度内聚性：模块内部的关联程度设计原则：高内聚低耦合软件系统结构图：深度、宽度、扇入、扇出。
详细设计
【程序流程图】箭头：控制流矩形：执行步骤菱形：逻辑条件【N-S图】【PAD图】
基本原则
自顶向下、逐步求精、模块化使用3种基本控制结构，限制goto语句的使用
3种控制结构
顺序结构、选择结构、循环结构
基本概念
对象是类的实例。类由两个部分组成：属性、方法。由同一个类定义的对象，拥有相同的属性和方法
类的特征
封装型、继承性、多态性
基本概念
测试：发现错误调试：诊断并改正错误注意：没有一种方法可以保证软件没有错误
黑盒和白盒
【黑盒】根据软件的外部功能设计测试用例例如：等价类划分、边界值分析、错误推测法【白盒】根据软件的内部逻辑设计测试用例例如：基本路径覆盖测试、逻辑条件覆盖测试
测试流程
单元测试：对单一模块进行测试集成测试：对模块间的协作进行测试确认测试：对《软件需求规格说明书》的需求进行逐一确认系统测试：对安全、性能等系统指标进行测试回归测试：对调试后的代码重新进行测试
三。数据库系统：
基本概念
数据（Data）：信息的载体。包括类型和值两个属性。数据库（DB）：依照某种数据模型将数据组织并存放起来的集合。数据库管理系统（DBMS）：系统软件，是数据库系统的核心，为数据库提供底层服务。数据库管理系统（DBAS）：基于数据库管理系统设计的应用软件，面向普通用户使用。数据库管理员（DBA）：负责数据库设计、维护、性能、安全等工作的高科技人才。数据库系统（DBS）：包括以上所有概念，再加上其他相关软硬件环境的总和。
数据语言
数据定义语言：表的建立、修改和删除数据操纵语言：表中数据的增加、删除、修改和查询数据控制语言：负责表中的安全性和完整性的设置
发展阶段
人工管理阶段 -> 文件管理阶段 -> 数据库管理阶段数据库管理阶段主要解决的问题：数据共享。
独立性
逻辑独立性：逻辑结构修改时，应用程序不需要修改。物理独立性：物理结构修改时，应用程序不需要修改。
三级模式
概念模式（逻辑模式）：数据库逻辑结构的全局描述外模式（子模式）：用户能看到的数据库逻辑结构和描述内模式（物理模式）：数据库的物理存储结构和存取方法
基本概念
E(Entity)：实体R(RelationShip)：联系一对一：学生和学号、中国公民和身份证、考生和准考证号……一对多：班长和班级、宿舍和学生……多对多：学生和课程、老师和课程……
图示
实体：矩形联系：菱形属性：椭圆形
基本概念
层次模型：用“树”的方式组织数据网状模型：用“图”的方式组织数据关系模型：用“二维表”的方式组织数据【关系模型】 属性、元组【关系数据库】字段、记录元组的分量是关系模型中的最小不可再分单位
数据完整性
候选键（候选关键字）：可以标识记录唯一性的几个字段。主键（主关键字）：可以标识记录唯一性的一个字段。一个表只能有一个主关键字。外键（外部关键字）：如果当前表中某字段是其他表的主键，则称此字段为外键。实体完整性：主键和候选键不能为空。参照完整性：对一对多关系中父表和子表之间关系的制约。自定义完整性：其他设置。如域完整性，就是对字段取值范围进行设置。
基本概念
【交】计算前提：两个关系的属性完全相同属性规则：属性保持不变。元组规则：对两个关系中的元组求交集。【并】计算前提：两个关系的属性完全相同属性规则：属性保持不变。元组规则：对两个关系中的元组求并集。【差】R-S=T计算前提：两个关系的属性完全相同属性规则：属性保持不变。元组规则：表示取R中存在且S中不存在的元组形成结果T。【笛卡儿积】RxS=T计算前提：对属性无要求属性规则：对两个关系的属性求并集。元组规则：对两个关系的元组做全排列。【除】R/S=T计算前提：S的属性应是R的子集属性规则：取R中存在的属性而S中不存在的属性作为结果T的属性，即对属性做差运算。元组规则：在R中选择与各属性值完全相等的元组，将其对T中的属性做投影
基本概念
【交】计算前提：两个关系的属性完全相同属性规则：属性保持不变。元组规则：对两个关系中的元组求交集。【并】计算前提：两个关系的属性完全相同属性规则：属性保持不变。元组规则：对两个关系中的元组求并集。【差】R-S=T计算前提：两个关系的属性完全相同属性规则：属性保持不变。元组规则：表示取R中存在且S中不存在的元组形成结果T。【笛卡儿积】RxS=T计算前提：对属性无要求属性规则：对两个关系的属性求并集。元组规则：对两个关系的元组做全排列。【除】R/S=T计算前提：S的属性应是R的子集属性规则：取R中存在的属性而S中不存在的属性作为结果T的属性，即对属性做差运算。元组规则：在R中选择与各属性值完全相等的元组，将其对T中的属性做投影
生命周期
【需求分析】数据流图、数据字典、需求规格说明书【概念设计】设计E-R模型【逻辑设计】将E-R模型转换为数据模型（主要是关系模型）【物理设计】将关系模型转换为关系数据库
⑹ 计算机二级的中的“堆排序法”是怎么排的
堆排序就是将所有待排序的元素组成一个堆，然后不断弹出堆顶的元素并调用函数维持堆序，直到所有元素均被弹出后，排序完成。被弹出的元素序列即一个有序数列。
一般做法是这样：
当一个节点被插入时，将该节点放在堆的末尾（这是为了保证堆是完全二叉树）然后将该节点与它的父节点比较，看该节点是否大于（或小于）其父节点，即判断当前的堆是否满足堆序。如果不满足，则将该节点与其父节点交换。
再将该节点与其新的父节点做比较，依此类推，直到该节点不再需要与其父节点交换为止。（即满足堆序时停止） 当一个根节点被弹出（即被从堆中删除）时，将堆最尾部的节点移动到头结点的位置，然后将该节点不断与其子节点比较，如果不符合堆序则交换，直到符合堆序为止。
(6)堆排序算法流程图扩展阅读：
堆的操作
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
⑺ 堆排序算法的实现
#include<stdio.h>
#include<malloc.h>
#include<time.h>
#define LISTSIZE 100
#define MORESIZE 100
#define overflow -1
typedef struct
{
int data;
int fre;
}Cell;
typedef struct {
Cell *elem;
long int length;
unsigned long int count1;
unsigned long int count2;
long int listsize;
}SqList;
SqList L1;
clock_t start,end;
FILE *p,*w;
int main (void)
{
void assign(Cell *a,Cell *b);
int LT(int a,int b);
void HeapSort (SqList &H);
void HeapAdjust (SqList &H,int s , int m);
void exchange(Cell *a,Cell *b);
//读入
int time=0;
while(time<4)
{
switch (time)
{
case 0:
p=fopen("data01.txt","r");
w=fopen("sorted01.txt","w");
break;
case 1:
p=fopen("data02.txt","r");
w=fopen("sorted02.txt","w");
break;
case 2:
p=fopen("data03.txt","r");
w=fopen("sorted03.txt","w");
break;
case 3:
p=fopen("data04.txt","r");
w=fopen("sorted04.txt","w");
break;
}
L1.count1=0;
L1.count2=0;
time++;
L1.elem=(Cell *)malloc((LISTSIZE+1)*sizeof(Cell));
L1.listsize=LISTSIZE;
L1.length=1;
Cell *newbase;
while(!feof(p))
{
if (L1.length>L1.listsize){
newbase=(Cell *)realloc(L1.elem,(L1.listsize+MORESIZE+1)*sizeof(Cell));
if (!newbase)
return overflow;
L1.elem=newbase;
L1.listsize+=MORESIZE;}
fscanf (p,"%d (%d)\n",&((L1.elem+L1.length)->data),&((L1.elem+L1.length)->fre));
L1.length++;
}
L1.length--;
printf ("listsize=%d length=%d\n",L1.listsize,L1.length);
//排序
start=clock();//开始计时
HeapSort(L1); //堆排序
end=clock(); //结束计时
printf ("Time: %lf\n",(double)(end-start)/CLOCKS_PER_SEC);//输出时间
for (int i=1;i<L1.length+1;++i)
fprintf (w,"%d (%d)\n",(L1.elem+i)->data,(L1.elem+i)->fre);
fprintf (w,"比较次数%u,移动次数%u\n",L1.count1,L1.count2);
printf ("比较次数%u,移动次数%u\n",L1.count1,L1.count2);
fprintf (w,"Copyright Reserved,Cheng Xuntao,NWPU");
fclose(p);
fclose(w);
}
return 0;
}
int LT(int a,int b)//比较函数
{L1.count1++;<br/> if (a<b){<br/> <br/> return 1;}
else return 0;
}
void assign(Cell *a,Cell *b)//赋值函数
{
a->data=b->data;
a->fre=b->fre;
L1.count2++;
}
void exchange(Cell *a,Cell *b)//交换记录
{
int temp;
temp=a->data;
a->data=b->data;
b->data=temp;
temp=a->fre;
a->fre=b->fre;
b->fre=temp;
L1.count2+=3; //+=3
}
void HeapAdjust (SqList &H,int s , int m)//调节其成为堆
{
Cell *rc;
rc=(Cell *)malloc(sizeof(Cell));
int j;
assign(rc,H.elem+s); //暂存
for (j=2*s;j<=m;j*=2){ //沿值较大的孩子节点向下筛选
if (j<m && LT((H.elem+j)->data,(H.elem+j+1)->data ))
j++; //j为值较大的记录的下标
if (!LT(rc->data,(H.elem+j)->data))
break; //rc应插入在位置s上
assign((H.elem+s),(H.elem+j));
s=j;
}
assign((H.elem+s),rc); //插入
}//HeapAdjust
void HeapSort (SqList &H) //堆排序
{
int i;
for (i=H.length/2;i>0;--i) //把L.elem[1...H.length]建成堆
HeapAdjust(H,i,H.length);
for (i=H.length;i>1;--i)
{
exchange(H.elem+1,H.elem+i); //将堆顶记录和当前未经排序的子序列L.elem[i...i]中最后一个记录相互交换
HeapAdjust(H,1,i-1); //重新调整其为堆
}
}//HeapSort
⑻ 排序算法的设计（c语言）根据程序画流程图及对每句程序加注释
#include "stdio.h"//标准io头文件
#include "stdlib.h"//库文件
#include "time.h"//时间系头文件
#define N0 100000 //定义常量
typedef int keytype; //类型命名
typedef struct node //定义结构体
{ keytype key; //只是类型命名成keytype，其实就是int的
}Etp;//结构体类型叫做Etp
Etp R[N0+1]; // R[1]..R[n] //定义数组
int n=50, count;//全局变量
void readData( Etp R[], int n)//读数据的函数
{ int i;
count=0;
srand( time( NULL ));//初始化时间种子
for( i=1; i<=n; i++) //对数组初始化
R[i].key=1000+
(int)((9999.0-1000)*rand()/RAND_MAX); // 0..RAND_MAX
}
void printData( Etp R[], int n )//打印显示数据的函数
{ int i;
for( i=1; i<=n; i++)
printf("%8d%s", //格式化显示数组的数据
R[i].key, i%5==0?"\n":"");
printf("\ncount=%d\n", count);
}
void bubberSort( Etp R[], int n )//冒泡排序的函数
{ int i,j;//（这个函数块就是冒泡排序的算法程序）
bool swap;
for( i=1; i<=n-1; i++)
{ swap=false;
for( j=1; j<=n-i; j++)
if( count++,R[j].key>R[j+1].key )
{ R[0]=R[j];
R[j]=R[j+1];
R[j+1]=R[0];
swap=true;
}
if( !swap ) break;
}
}
void bubberSort1( Etp R[], int n )//这个也是另一个冒泡排序的函数
{ int j;//跟上面不同的是这个算法用的是递归的方式，上面的是非递归的
for( j=1; j<=n-1; j++)
if( count++,R[j].key>R[j+1].key )
{ R[0]=R[j];
R[j]=R[j+1];//________;//就是两个变量交换值
R[j+1]=R[0];
}
if( n>1 ) bubberSort1( R, n-1); //___________;//递归调用
}
void selectSort( Etp R[], int n )//这个是选择排序
{ int i,j,k;//（这个函数块就是选择排序的算法程序）
for( i=1; i<=n-1; i++)
{
k=i;
for( j=i+1; j<=n; j++)
if( count++,R[j].key<R[k].key ) k=j;
if( k!=i )
{ R[0]=R[i];
R[i]=R[k];
R[k]=R[0];
}
}
}
void insertSort( Etp R[], int n )//这个是插入排序
{ int i,j;
for( i=2; i<=n; i++)
{
R[0]=R[i];
j=i-1;
while( count++,R[j].key>R[0].key ) R[j+1]=R[j--];
R[j+1]=R[0];
count++;
}
}
void sift( Etp R[], int i, int m)//堆排序中的步骤
{ int k=2*i;
R[0]=R[i];
while( k<=m )
{ if( count++, k+1<=m && R[k+1].key>R[k].key) k++;
if( count++,R[0].key<R[k].key ) R[i]=R[k];
else break;
i=k;
k=2*i;
}
R[i]=R[0];
}
void heapSort( Etp R[], int n )//这个是堆排序
{ int j;
for( j=n/2; j>=1; j--) sift( R, j, n);
for( j=n; j>=2; j--)
{ R[0]=R[1];
R[1]=R[j];
R[j]=R[0];
sift( R, 1, j-1 );
}
}
int main()//主函数的进入口
{
readData( R, n );//读取数据
bubberSort1( R, n );//调用递归冒泡排序
printData( R, n);//显示数据
readData( R, n );//读取数据
selectSort( R, n );//调用选择排序
printData( R, n);//显示数据
readData( R, n );//读取数据
insertSort( R, n );//调用插入排序
printData( R, n);//显示数据
readData( R, n );//读取数据
heapSort( R, n );//调用堆排序
printData( R, n);//显示数据
return 0;
}
//诶·~注释完我总算看出来了，难道你要我解释各个排序的过程？
//那你还不如直接或者看书，你要是不理解原理是不可能看懂过程的。
//注释也只是语句的解释，但是过程的含义是无法描述的