排序演算法ns流程

1. 快速排序法的平均時間復雜度和最壞時間復雜度分別是多少

快速排序的平均時間復雜度和最壞時間復雜度分別是O(nlgn)、O(n^2)。

當排序已經成為基本有序狀態時，快速排序退化為O(n^2)，一般情況下，排序為指數復雜度。

快速排序最差情況遞歸調用棧高度O(n)，平均情況遞歸調用棧高度O(logn)，而不管哪種情況棧的每一層處理時間都是O(n)，所以，平均情況（最佳情況也是平均情況）的時間復雜度O(nlogn)，最差情況的時間復雜度為O(n^2)。

(1)排序演算法ns流程擴展閱讀

快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序，它採用了一種分治的策略，通常稱其為分治法。快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：

（1）首先設定一個分界值，通過該分界值將數組分成左右兩部分。

（2）將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。

（3）然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。

（4）重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。

2. 用選擇法對10個整數由大到小排序。要求畫出流程圖

選擇排序的過程如下：

1. 從待排序的n個元素中找到最大的元素，將其鋒嘩與第n個元素交換位置。

2. 在剩餘的n-1個元素中，再找到最大的元素，將其與第n-1個元素交換位置。

3. 重復上述步驟，直到只剩下一個元素為止。

其中，每經過一輪，就能確定出一個元素的位置。通過n-1輪選擇，就能將這n個元素按照從大到小的順序排好序。選擇排序的時間復雜度為O(n^2)。

下面是銀改行使用C語言實現選擇排序演算法的示例代碼：

#include <stdio.h>

void selection_sort(int arr[], int n)

{

int i, j, max_idx;

for (i = 0; i < n - 1; i++) {

max_idx = i;

for (j = i + 1; j < n; j++) {

if (arr[j] > arr[max_idx]) {

max_idx = j;

}

}

// 將找到的最大元素與當前位置交換

int temp = arr[i];

arr[i] = arr[max_idx];

arr[max_idx] = temp;

}

}

int main()

{

int i, n;

int arr[10] = {23, 4, 56, 77, 12, 45, 89, 34, 67, 90};

n = sizeof(arr) / sizeof(arr[0]);

// 輸出排序前的列表

printf("排序前： ");

for (i = 0; i < n; i++) {

printf("%d ", arr[i]);

}

printf(" ");

// 調用選擇排序函數

selection_sort(arr, n);

// 輸出排序後的列表

printf("殲猛排序後： ");

for (i = 0; i < n; i++) {

printf("%d ", arr[i]);

}

printf(" ");

return 0;

}

選排序流程圖：

3. 有3個數a、b、c,要求按從大到小順序把它們輸出.用自然語言、傳統流程圖和N-S圖表示求解的演算法.

//簡單的方法就是對三個數按大小排序。先將最小的數放到首位，如果發現有大內小順序不對的，就將它容們交換位置。

#include<stdio.h>

int main()

{

int a,b,c,t;

printf("請輸入三個整數：");

scanf("%d%d%d",&a,&b,&c);

if(a>b){t=a; a=b; b=t;} //a與b若大小順序不對，就交換位置

if(a>c){t=a; a=c; c=t;} //a與c若大小順序不對，就交換位置；到此a肯定是最小

if(b>c){t=b; b=c; c=t;} //b與c若大小順序不對，就交換位置；到此c肯定是最大

printf("這三個數從小到大排列是：%d %d %d ",a,b,c);

getch();

return 0;

}

例如：

實現思路，用偽代碼寫出解此題的演算法：

1、if a>b 將a和b對換 （a是a，b中的小者）

2、if a>c 將a和c對換 （a是a，c中的小者，因此a是三者中最小者）

3、if b>c 將b和c對換 （b是b，c中的小者，也是三者中次小者）

(3)排序演算法ns流程擴展閱讀：

程序框圖表示程序內各步驟的內容以及它們的關系和執行的順序。它說明了程序的邏輯結構。框圖應該足夠詳細，以便可以按照它順利地寫出程序，而不必在編寫時臨時構思，甚至出現邏輯錯誤。流程圖不僅可以指導編寫程序，而且可以在調試程序中用來檢查程序的正確性。

如果框圖是正確的而結果不對，則按照框圖逐步檢查程序是很容易發現其錯誤的。流程圖還能作為程序說明書的一部分提供給別人，以便幫助別人理解你編寫程序的思路和結構。

4. 排序方法有哪幾種 排序方法的相關知識

1、排序方法有10種，悉旅緩分別是：冒泡排序、選擇排序、插入排序、希爾排序、歸並排序、快速排序、堆排序、計數排序、桶排序、基數排序。

2、冒泡排序演算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和演算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。

3、選擇排序演算法的基本思路是為每一個位置睜模選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。

4、插入排序算鎮森法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。

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