データ構造におけるソートアルゴリズム
面接と筆記試験では、ソートアルゴリズムが簡単に試験できるので、データ構造のソートアルゴリズムを簡単に復習しました.データ構造という本の章では、ソートについて話しています.ほとんどが偽コードを提供しています.偽コードがあれば実現しやすいです.実は多くの机の试験问题、例えば:数字の问题、その中の数字の规则を见るだけで、简単に机に乗って実现して、もし见えなければ、それは难しくなります.もう一度証明して、思想はとても重要で、アルゴリズムを理解して、頭の中でこのアルゴリズムの実行過程に対してとてもはっきりしていて、コードが実現できないことを恐れません
よし、くだらないことは言わないで、次は本の中の偽コードを結びつけて、例をあげます.
この例では、単純なテストをしただけで、直接データを配列に入れることができます.もちろん、ユーザーが入力する場合は、mallocで配列サイズを動的に割り当てるか、C++のvectorで実現する必要があります.mallocを使用する場合はfreeで空間を解放する必要があります.
上の例では、スタックソートや集計ソートなどのソートアルゴリズムのようないくつかの容易なソートアルゴリズムが与えられているだけで、実装は少し複雑で、スタックソートは再帰的なプロセスであり、スタックは完全な二叉木であり、出力ノードの後、このノードを動的に削除し、スタック全体を再構築する必要がある.これらのソートアルゴリズムが出現する確率は例に挙げられているいくつかのソートアルゴリズムほど確率が高いわけではないので、後で時間があれば見てみましょう.
よし、くだらないことは言わないで、次は本の中の偽コードを結びつけて、例をあげます.
#include <iostream>
using namespace std;
//
void straightsort(int list[],int n){
int i,j;
for(i=2;i<n;i++){
list[0]=list[i];//list[0] , ,
j=i-1;
while(list[0]<list[j]){
list[j+1]=list[j];//
j--;
}
list[j+1]=list[0];// i
}
}
//
void bubblesort(int list[],int n){
int i,j,flag,temp;
for(i=n-1;i>0;i--){
flag=1;
for(j=0;j<i;j++){
if(list[j]<list[j+1]){//
flag=0;
temp=list[j];//
list[j]=list[j+1];//
list[j+1]=temp;
}
}
if(flag)return;
}
}
//
int quickpass(int list[],int low,int high){
int pivotkey=list[low];//
while(low<high){//
while(low<high && list[high]>=pivotkey){
--high;
}
list[low]=list[high];//
while(low<high && list[low]<=pivotkey){
++low;
}
list[high]=list[low];//
}
list[low]=pivotkey; //
return low; //
}
//
void quicksort(int list[],int low,int high){
int pos;
if(low<high){ // 1
pos=quickpass(list,low,high); // list[low..high]
quicksort(list,low,pos-1); // ,pos
quicksort(list,pos+1,high); //
}
}
//
void selectsort(int list[],int n){
int i,k,j,temp;
for(i=0;i<n-1;i++){
k=i;
for(j=i+1;j<n;j++){ //
if(list[j]<list[k]){
k=j;
}
}
if(k!=i){
temp=list[i];//
list[i]=list[k];
list[k]=temp;
}
}
}
void main(){
int data[]={1,3,5,8,6,2,4};//
int n=7;
//straightsort(data,n);
//bubblesort(data,n);
//quicksort(data,0,n-1);
selectsort(data,n);
for(int i=0;i<n;i++){
cout<<data[i]<<" ";
}
}
この例では、単純なテストをしただけで、直接データを配列に入れることができます.もちろん、ユーザーが入力する場合は、mallocで配列サイズを動的に割り当てるか、C++のvectorで実現する必要があります.mallocを使用する場合はfreeで空間を解放する必要があります.
上の例では、スタックソートや集計ソートなどのソートアルゴリズムのようないくつかの容易なソートアルゴリズムが与えられているだけで、実装は少し複雑で、スタックソートは再帰的なプロセスであり、スタックは完全な二叉木であり、出力ノードの後、このノードを動的に削除し、スタック全体を再構築する必要がある.これらのソートアルゴリズムが出現する確率は例に挙げられているいくつかのソートアルゴリズムほど確率が高いわけではないので、後で時間があれば見てみましょう.