排序演算法NS圖

Ⅳ 排序演算法的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;
}

Ⅵ NOIp的演算法具體考察范圍

這個，首先凸包是屬於計算機和的內容。noip歷史上只考過一道計算機和的題目，而且只是鳳毛麟角，一帶而過。所以，我以為可以忽視不記。
另，關於noip的考試范圍：
我認為主要演算法是：

動態規劃：各種動歸。個人認為動歸不會考得太難，基本都是可做的題目。

搜索：近幾年開始提倡優化。不過你放心，數據都不會太惡心，縱使題目很惡心……比如說傳染病預防，要是數據惡心，必然不A就死人，但是……

貪心：這個非常重要，至少我是這么想的，因為，貪心這玩意，用到搜索上叫做剪枝，用到動歸上叫做優化，用到不會做的題目上叫做騙分。而且在應用此演算法時，必須要有良好的貪心感覺，以及較好的數學論證功底。

圖論：說實在的，考得不多。基本懂了最短路，最小生成樹，再把dfs的幾個演算法學好（拓撲排序，scc，橋，掛點，lca等演算法學好不會有啥問題）。

窮舉：每年基本必然有一道。比較煩的窮舉可以嘗試打表。

分治：初賽考得很多，復賽考得很少。（在我映像中，好像還真就沒有……）

數學問題：看到數學問題不要抖，就是你不知道這個的數學定理，一般也是可以化作其他方法來做的。比如數論問題，可以化成hash+最短路啦。還有很多。當然要是知道些數學定理，很多動歸啦什麼什麼的問題都會簡單很多。

至於數據結構什麼什麼的基本可以無視之：知道最簡單的bst，最簡單的線段樹，以防他考到就差不多啦。

最後要說的是：（最關鍵的）別把noip想的太難！！不要看太多雜七雜八的演算法！！練好基本功才是王道！！
看見不會做的題目，千萬不要放棄。演算法時互通的。

Ⅶ 請教高手！！！

1。考試難度與以前差不多。

2。沒有上機考試，依然採取筆試方式。

3。與三級網路相比，就我個人認為，程序員考試相對要容易。三級網路既考筆試又考上機，且考試涉及的知識面和程序員差不多廣。
但主要還是由每個人的興趣愛好來決定。
程序員比較適合今後搞編程這行，而三級網路主要適合今後從事網路工程方面的工作。

附：

2007年程序員考試大綱

一考試說明
1．考試要求：
（1）掌握數據及其轉換、數據的機內表示、算術和邏輯運算，以及相關的應用數學基礎知識；
（2）理解計算機的組成以及各主要部件的性能指標；
（3）掌握操作系統、程序設計語言的基礎知識；
（4）熟練掌握計算機常用辦公軟體的基本操作方法；
（5）熟練掌握基本數據結構和常用演算法；
（6）熟練掌握C程序設計語言，以及C＋＋、Java、Visual Basic中的一種程序設計語言；
（7）熟悉資料庫、網路和多媒體的基礎知識；
（8）掌握軟體工程的基礎知識，了解軟體過程基本知識、軟體開發項目管理的常識；
（9）了解常用信息技術標准、安全性，以及有關法律、法規的基本知識；
（10）了解信息化、計算機應用的基礎知識；
（11）正確閱讀和理解計算機領域的簡單英文資料。
2．通過本考試的合格人員能根據軟體開發項目管理和軟體工程的要求，按照程序設計規格說明書編制並調試程序，寫出程序的相應文檔，產生符合標准規范的、實現設計要求的、能正確可靠運行的程序；具有助理工程師（或技術員）的實際工作能力和業務水平。
3．本考試設置的科目包括：
（1）計算機硬軟體基礎知識，考試時間為150分鍾，筆試；
（2）程序設計，考試時間為150分鍾，筆試。

二、考試范圍

考試科目1：計算機硬軟體基礎知識
1. 計算機科學基礎
1.1 數制及其轉換
二進制、十進制和十六進制等常用數制及其相互轉換
1.2 數據的表示
數的表示（原碼、反碼、補碼表示，整數和實數的機內表示方法，精度和溢出）
非數值表示（字元和漢字的機內表示、聲音和圖像的機內表示）
校驗方法和校驗碼（奇偶校驗碼、海明校驗碼）
1.3 算術運算和邏輯運算
計算機中二進制數的運算方法
邏輯代數的基本運算和邏輯表達式的化簡
1.4 數學應用
常用數值計算（矩陣、方程的近似求解、插值）
排列組合、應用統計（數據的統計分析）
1.5 常用數據結構
數組（表態數組、動態數組）、線性表、鏈表（單向鏈表、雙向鏈表、循環鏈表）、隊列、棧、樹（二叉樹、查找樹）、圖的定義、存儲和操作
1.6 常用演算法
常用的排序演算法、查找演算法、數值計算、字元串處理、數據壓縮演算法、遞歸演算法、圖的相關演算法
演算法與數據結構的關系，演算法效率，演算法設計，演算法描述（流程圖、偽代碼、決策表）
2． 計算機系統基礎知識
2.1 硬體基礎知識
2.1.1 計算機系統的組成，硬體系統、軟體系統及層次結構
2.1.2 計算機類型和特點
微機、工作站、伺服器、大型計算機、巨型計算機
2.1.3 中央處理器CPU
算器和控制器的組成，常用的寄存器、指令系統、定址方式、指令執行控制、處理機性能
2.1.4 主存和輔存
存儲器系統
存儲介質（半導體、硬碟、光碟、快閃記憶體、軟盤、磁帶等）
主存儲器的組成、性能及基本原理
Cache的概念、虛擬存儲的概念
輔存設備的類型、特性、性能和容量計算
2.1.5 I/O介面、I/O設備和通信設備
I/O介面（匯流排、DMA、通道、SCSI、並行口、RS232C、USB、IEEE1394）
I/O設備的類型和特性（鍵盤、滑鼠、顯示器、列印機、掃描儀、攝像頭，以及各種輔存設備）
I/O設備控制方式（中斷控制、DMA）
通信設備的類型和特性（Modem、集線器、交換機、中繼器、路由器、網橋、網關）及其連接方法和連接介質（串列連接、並行連接，傳輸介質的類型和特性）
2.2 軟體基礎知識
2.2.1 操作系統基礎知識
操作系統的類型和功能
操作系統的內核（中斷控制）和進程概念
處理機管理、存儲管理、設備管理、文件管理、作業管理
漢字處理
圖形用戶界面及其操作方法
2.2.2 程序設計語言和語言處理程序基礎知識
匯編、編譯、解釋系統的基礎知識
程序設計語言的基本成分（數據、運算、控制和傳輸）
過程（函數）調用
2.3 網路基礎知識
網路的功能、分類、組成和拓撲結構
網路體系結構與協議（OSI/RM，TCP/IP）
常用網路設備與網路通信設備，網路操作系統基礎知識和使用
Client/Server結構、Browser/Server結構
LAN基礎知識
Internet基礎知識
2.4 資料庫基礎知識
資料庫管理系統的主要功能和特徵
資料庫模型（概念模式、外模式、內模式）
數據模型，ER圖
數據操作（關系運算）
資料庫語言（SQL）
資料庫的主要控制功能
2.5 多媒體基礎知識
多媒體基礎概念，常用多媒體設備性能特徵，常用多媒體文件格式類型
簡單圖形的繪制，圖像文件的基本處理方法
音頻和視頻信息的應用
簡單多媒體應用製作方法
2.6 系統性能指標
響應時間、吞吐量、周轉時間等概念
可靠性、可維護性、可擴充性、可移植性、可用性、可重用性、安全性等概念
2.7 計算機應用基礎知識和常用辦公軟體的操作方法
信息管理、數據處理、輔助設計、自動控制、科學計算、人工智慧等概念
文字處理基礎知識和常用操作方法
電子表格處理基礎知識和常用操作方法
演示文稿製作方法
電子郵件處理操作方法
網頁製作方法
3． 軟體開發和運行維護基礎知識
3.1 軟體工程和項目管理基礎知識
軟體工程基本概念
軟體開發各階段的目標和任務
軟體過程基本知識
軟體工程項目管理基本知識
面向對象開發方法基礎知識
軟體開發工具與環境基礎知識（CASE）
軟體質量管理基礎知識
3.2 軟體需求分析、需求定義及軟體基礎知識
結構化分析概念（數據流圖（DFD）、實體關系圖（ER））
面向對象設計、結構化設計基礎知識
模擬設計、代碼設計、人機界面設計要點
3.3 程序設計基礎知識
結構設計程序設計，程序流程圖，NS圖，PAD圖
程序設計風格
面向對象設計基礎知識、可視化程序設計基礎知識
3.4 程序測試基礎知識
黑盒測試、白盒測試、灰盒測試基礎知識
測試工作流程
3.5 軟體開發文檔基礎知識
3.6 軟體運行和維護基礎知識
軟體運行基礎知識
軟體維護基礎知識
4． 安全性基礎知識
安全性基本概念
計算機病毒的防治，計算機犯罪的防範
訪問控制
加密與解密基礎知識
5． 標准化基礎知識
標准化基本概念
國際標准、國家標准、行業標准、企業標准基礎知識
代碼標准、文件格式標准、安全標准、軟體開發規范和文檔標准基礎知識
標准化機構
6． 信息化基本知識
信息化基本概念
全球信息化趨勢，國家信息化戰略，企業信息化戰略和策略常識
有關的法律、法規要點
過程教育、電子商務、電子政務等常識
企業信息資源管理常識
7． 計算機專業英語
掌握計算機技術的基本詞彙
能正確閱讀和理解本領域的簡單英文資料

考試科目2：程序設計
1. 內部設計
1.1 理解外部設計
1.2 功能劃分和確定結構
數據流圖、結構圖
1.3 物理數據設計
確定數據組織方式、存儲介質，設計記錄格式和處理方式
1.4 詳細輸入輸出設計
界面設計、報表設計
1.5 內部設計文檔
對程序介面、程序功能、人機界面、輸入輸出、測試計劃的描述
1.6 內部設計文檔
2． 程序設計
2.1 模擬劃分（原則、方法、標准）
2.2 編寫程序設計文檔
模塊規格說明書（程序處理邏輯的描述、輸入輸出數據格式的描述）
測試要求說明書（測試類型和目標、測試用例、測試方法）
2.3 程序設計評審
3． 程序實現
3.1 編程
編程方法和標准
程序設計語言的使用
人工走查
程序文檔化
3.2 程序測試
准備測試環境和測試工具
准備測試數據
寫出測試報告
4． 程序設計語言（C語言為必選，其他語言可以任選一種）
4.1 C程序設計語言（ANSI C標准）
程序結構，語法，數據類型說明，可執行語句，函數調用，標准庫函數，指針
4.2 C＋＋程序設計語言（ANSI C＋＋標准）
C＋＋和面向對象程序設計，語法和程序結構，類、成員、構造函數、析構函數、模板、繼承、多態
4.3 Java程序設計（Java 2）
Java和面向對象程序設計
語言機制（程序結構和語法，類、成員、構造函數、析構函數、繼承、介面）
4.4 Visual Basic程序設計（Visual Basic 6.0）
用戶界面設計
程序結構和語法
文件系統對象
訪問資料庫

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