データ構造:並べ替え

並べ替えは、一般的に、並べ替え、並べ替え、並べ替え、並べ替え、並べ替えに分けられます.
 
1.並べ替え、基本的な考えを挿入します.並べ替え記録は毎回、前に並べられたサブファイルの中の適切な位置にキーサイズで挿入します.すべてのレコードが挿入されるまで.時間複雑度:O(n^2)安定しています.
  アルゴリズムの説明:
 

//  
void insertSort(SeqList R){
 int i,j;
 for(i=2; i<=n; i++){
  if(R[i].key < R[i-1].key){
   R[0] = R[i];
   j = i-1;
   do{
     R[j+1] = R[j];
     j--;
   }while(R[0]<R[j]);
  }// end if
 }//end for
}

 
 
  直接挿入順序:順序付け記録が配列R［1.N］に保存されていると仮定すると、最初はR［1］が順序付きゾーンとなり、無秩序ゾーンはR［2.N］となる.i=2からi=nまで順次R[i]を現在の順序領域R[1.i-1]に挿入し、n個の記録を含む順序領域を生成する.
  直接挿入順序:
      簡単な方法:まず、現在の順序領域R[1.i-1]でR[i]が位置kに正しく挿入されていることを見つけ、R[k,i-1]を全部後に一桁移動し、k位置を空けてR[i]を挿入する.
      改善の方法:挿入されるR[i]を右から左へ順に秩序ゾーンR[j]と比較し、R[j]R[i]であれば、R[j]が1ビットシフトし、R[j]<=R[i]であれば、検索が終了し、j＋1はR[i]挿入位置となる.
 
2.ヒルの順序付けも挿入順序の一つです.基本的な考え:まずnより小さい整数d 1を取って、最初の増分として、ファイルのすべての記録をd 1グループに分けます.全ての距離がd 1の倍数である記録は同じグループに入れられます.まず各グループに直接挿入して並べ替えを行います.次に、第2の増分d 2＜d 1＞を取得して、取得された増分dt=1まで上記のパケットと並べ替えを繰り返し、実質的にはパケット挿入順序付けである.不安定です

//d    ,        
void shellPass(int d, int n){
	int i,j;
	
	for(i=d+1; i<=n; i++){
		if(R[i] < R[i-d]){
			R[0] = R[i];
			j = i - d;
			do{
				R[j+d] = R[j];
				j = j - d;
			}while(j>0 && R[0] < R[j]);
			R[j+d] = R[0];
		}//end if
	}//end for
}

  
3.発泡体の並べ替え

void bubbleSort(int n){
	int i,j,t;
	int changed;
	
	for(i=1; i<n; i++){
		changed = 0;
		for(j=n-1; j>=i; j--){
			if(R[j+1] < R[j]){
				R[0] = R[j+1];
				R[j+1] = R[j];
				R[j] = R[0];
				changed = 1;
			}
		}
		if(!changed) return;
	}
} 

 
4.快速的に並べ替えて、交換順序を分けて、分割の策略を採用する.問題をいくつかの小規模に分解したが、構造が元の問題と似ているサブ問題は、これらのサブ問題を再帰的に解いて、サブ問題の解を元の問題の解に結合する.
基本思想:(1)分解、R[low.high]はいずれも一つの記録を基準とするPivotを選択し、左右のサブ区間に分け、左のサブ区間のすべての記録をPivotより小さくし、右の区間はPivotに等しい.(2)ソルバーを解く.高速並べ替えを再帰的に呼び出して、左右のサブ区間を高速に並べ替えます.(3)組み合わせ.クイックソートは不要です

int partition(int low, int high){
	int pivot = R[low];
	while(low<high){
		while(low<high && R[high]>=pivot){
			high--;
		}
		if(low<high){
			R[low++] = R[high];
		}
		while(low<high && R[low]<=pivot){
			low++;
		}
		if(low<high){
			R[high--] = R[low];
		}//end while 
	}
	R[low] = pivot;
	return low;
}

void quickSort(int low,int high){
	int pivotPos;
	if(low < high){
		pivotPos = partition(low,high);
		quickSort(low,pivotPos-1);
		quickSort(pivotPos+1,high);
	}
}

 
5.並べ替えを選択し、基本思想:並べ替え待ちの記録からキーワードの最小記録を選択し、並べ替え済みのサブファイルの最後に並べ替えて、全部の記録がソートされるまで順番を決める.常に直接選択して並べ替えと積み上げがあります.
  直接選択並べ替え:n個の記録されたファイルの直接選択並べ替えは、n-1回の直接選択を経て順序付けされた結果を得ることができます.
 

void selectSort(int n){
	int i,j,k;
	for(i=1; i<=n; i++){
		k=i;
		for(j=i+1; j<=n; j++){
			if(R[j] <R[k]){
				k=j;	
			}
			if(k!=i){
				R[0] = R[i];
				R[i] = R[k];
				R[k] = R[0];
			}
		}
	}
}

 
ヒープの並べ替え: