堆排序演算法流程圖

⑴ 排序演算法的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;
}
//誒·~注釋完我總算看出來了，難道你要我解釋各個排序的過程？
//那你還不如直接或者看書，你要是不理解原理是不可能看懂過程的。
//注釋也只是語句的解釋，但是過程的含義是無法描述的