Java でよく使われる 7 つのソートアルゴリズムの概要

しばらく時間が空いたので、Java でよく使われる 7 つのソートアルゴリズムをまとめてみました。後でまた見返せるといいのですが。

1. 挿入ソートアルゴリズム

挿入ソートの基本的な考え方は、配列をトラバースする過程で、シリアル番号 i の前の要素、つまり [0..i-1] がソートされていると想定することです。このトリップでは、i に対応する要素 x の正しい位置 k を見つける必要があり、この位置 k を見つける過程で、比較する要素を 1 つずつ 1 つずつ後ろに移動して要素 x のための「スペースを確保」し、最後に k に対応する要素値を x に割り当てます。一般に、挿入ソートの時間計算量と空間計算量は、それぞれ O(n2) と O(1) です。

 /**
 * @param int[] ソートされていない配列
* @return int[] ソートされた配列
*/   
 
公共  int [] sortInsert( int [] 配列){
 ( int i = 1 ;i < array.length;i++){
 int temp = 配列[i];
整数j;
 ( j=i- 1 ;j >= 0 && temp< 配列[j]; j--){
配列[j + 1 ] = 配列[j];
 }
配列[j + 1 ] = temp;
 }
配列を返します。
 }

2. 選択ソートアルゴリズム

選択ソートの基本的な考え方は、配列をトラバースすることです。i はソートする必要がある現在のシーケンス番号を表します。残りの [i...n-1] で最小値を見つけ、見つかった最小値を i が指す値と交換する必要があります。要素を決定するたびに、最適な値を選択するサブプロセスがあるため、比喩的に選択ソートと呼ばれます。選択ソートの時間計算量と空間計算量はそれぞれO(n2)とO(1)です。

 /**
 * @param int[] ソートされていない配列
* @return int[] ソートされた配列
*/   
 
公共  int [] ソート選択( int [] arr){
 ( int i = 0 ; i < arr.length; i++) {
 int miniPost = i;
 ( int m = i + 1 ; m < arr.length; m++) {
 （arr[m] < arr[miniPost]）の場合{
ミニポスト = m;
 }
 } 
 
 （arr[i] > arr[miniPost]）の場合{
整数温度;
 temp = arr[i];
 arr[i] = arr[miniPost];
 arr[miniPost] = temp;
 }
 }
 arrを返します。
 }

3. バブルソートアルゴリズム

バブルソートは、大きい数字を下に、小さい数字を上に並べるソートです。

 /**
 * @param int[] ソートされていない配列
* @return int[] ソートされた配列
*/   
 
公共  int [] ソートバブル( int [] 配列){
整数温度;
 // 第 1 レベルのループ: 比較回数を示します。たとえば、長さの要素がある場合、比較回数は長さ - 1 になります (それ自体と比較する必要はありません)  
 ( int i = 0 ; i < 配列の長さ- 1 ; i++) {
 ( int j = array.length - 1 ; j > i; j--) {
 （配列[j] < 配列[j - 1 ]）の場合{
 temp = 配列[j];
配列[j] = 配列[j - 1 ];
配列[j - 1 ] = temp;
 }
 }
 }
配列を返します。
 }

4. クイックソートアルゴリズム

並べ替えのプロセスを通じて、レコードの1つの部分のキーワードが2つの独立した部分に分かれています。ベースが小さい場合は、ベースが右側の位置（一時的な高い位置として記録）に移動します。ベースの左側は、上記の2つのステップを低く繰り返します。

 /**
 * @param int[] ソートされていない配列
* @return int[] ソートされた配列
*/   
 
公共  int [] sortQuick( int [] 配列){
 quickSort(配列、 0 、配列の長さ - 1 )を返します。
 } 
 
プライベート  int [] クイックソート( int [] arr, int下限, int上限) {
 （低さ < 高さ）の場合{
 int除算 = パーティション (arr、low、high);
クイックソート(arr, low, division - 1 );
クイックソート(arr, 分割 + 1 , 高さ);
 }
 arrを返します。
 } 
 
 // 流域、ベース、左側のものはこの位置より小さく、右側のものは大きい 
プライベート  intパーティション ( int [] arr, int低, int高) {
 int base = arr[low]; //サブテーブルの最初のレコードをピボット（ウォーターシェッド）レコードとして使用します 
 while (low < heigh) { //テーブルの両端から中央まで交互にスキャンする 
 (low < heigh && arr[heigh] >= base)の場合{
高さ--;
 }
 // ベースは現在の高さ位置に割り当てられ、ここでベースは移動（スワップ）され、高さ位置の右側はベースよりも大きくなります 
 swap(arr,heigh,low);
 (low < height && arr[low] <= base)の場合{
低++;
 }
 // 左の値が基本値より大きい場合は位置を変更します 
 swap(arr,heigh,low);
 }
 // 現在 low = high;  
低く戻る;
 } 
 
プライベート  void swap( int [] arr, int a, int b) {
整数温度;
 temp = arr[a];
 arr[a] = arr[b];
 arr[b] = 一時;
 }

5. マージソートアルゴリズム

マージソートは再帰的に実装され、「分割統治」方式に属します。ターゲット配列は中央から 2 つに分割され、2 つの配列は別々にソートされます。ソートが完了すると、ソートされた 2 つの配列が「マージ」されます。マージソートで最も重要なことは、「マージ」プロセスです。マージプロセスには、マージする 2 つの配列と同じ長さの追加スペースが必要です。

 /**
 * @param int[] ソートされていない配列
* @return int[] ソートされた配列
*/  
プライベート  int [] ソート( int [] 数値, int下限, int上限) {
 int中間 = (低 + 高) / 2 ;
 （低<高）の場合{
 // 左 
並べ替え(数値、低、中);
 // 右 
並べ替え(数値、中央 + 1 、高);
 // 左と右をマージ 
マージ(数値、低、中、高);
 }
数値を返します。
 } 
 
プライベート  void merge( int [] nums, int low, int mid, int high) {
 int [] temp =新しい  int [高 - 低 + 1 ];
 int i = low; // 左ポインタ 
 int j = mid + 1 ; // 右ポインタ 
整数k = 0 ;
 // 小さい数字をまず新しい配列に移動します 
 ( i <= 中間 && j <= 高) {
 （数値[i] < 数値[j]）の場合{
 temp[k++] = nums[i++];
 }それ以外{
 temp[k++] = nums[j++];
 }
 }
 // 残りの数字を左側の配列に移動する 
 (i <= 中間) {
 temp[k++] = nums[i++];
 }
 // 残りの数字を右側の配列に移動する 
 (j <= 高さ)の間{
 temp[k++] = nums[j++];
 }
 // nums配列を新しい配列の数字で上書きします 
 ( int k2 = 0 ; k2 < temp.length; k2++) {
 nums[k2 + 下限] = temp[k2];
 }
 } 
 
公共  int [] sortMerge( int [] 配列) {
 sort(配列、 0 、配列の長さ - 1 )を返します。
 }

6. シェルソートアルゴリズム

シェルソートが誕生したのは、挿入ソートでは大きな配列を処理するときに移動しなければならない要素が多すぎるという問題に遭遇したためです。ヒルソートの考え方は、大きな配列をギャップで分割されたいくつかの小さな配列に「分割して征服する」ことです。たとえば、配列[1、2、3、4、5、6、7、8]は、ギャップ= 2で分割すると、[1、3、5、7]と[2、4、6、8]の2つの配列に分割できます（同様に、ギャップ= 3の場合、分割された配列は[1、4、7]、[2、5、8]、[3、6]です）。次に、分割された配列に対してそれぞれ挿入ソートを実行します。各サブ配列がソートされた後、ギャップ値が減らされ、ギャップ= 1になるまで、つまり配列全体が挿入されてソートされるまで、前の手順が繰り返されます。この時点で、配列は基本的にソートされているため、移動する必要がある要素は非常に小さくなり、挿入ソートが大きな配列を処理するときに移動回数が多いという問題が解決されます。

シェルソートは挿入ソートの改良版です。データ量が多い場合の効率向上に非常に役立ちます。データ量が少ない場合は、挿入ソートを直接使用することをお勧めします。

 /**
 * @param int[] ソートされていない配列
* @return int[] ソートされた配列
*/   
 
公共  int [] sortShell( int [] 配列) {
 // 増分を取得する 
 intステップ = 配列の長さ / 2 ;
 (ステップ >= 1 )の間{
 for ( int i = step; i < array.length; i++) {
 int temp = 配列[i];
整数j = 0 ;
 // 挿入ソートとの違いはここ 
 ( j = i - ステップ; j >= 0 && temp < 配列[j]; j -= ステップ) {
配列[j + ステップ] = 配列[j];
 }
配列[j + ステップ] = temp;
 }
ステップ /= 2 ;
 }
配列を返します。
 }

7. ヒープソートアルゴリズム

要点は、まずビッグトップヒープを作成し、親が子よりも大きく、ルートノードが *** ノードであり、*** ノード (ルート) を末尾ノード (より小さい *** ノード) と交換して、*** 末尾ノードを *** に残し、残りは *** 要素から末尾ノードの前の位置まで、ビッグトップヒープを再帰的に構築することです。

 /**
 * @param int[] ソートされていない配列
* @return int[] ソートされた配列
*/  
公共  int [] sortHeap( int [] 配列) {
 buildHeap(array); // ヒープを構築 
 int n = 配列の長さ;
整数i = 0 ;
 (i = n - 1 ; i >= 1 ; i--)の場合{
 swap(配列, 0 , i);
ヒープ化(配列、 0 、i);
 } 
 
配列を返します。
 } 
 
プライベート  void buildHeap( int [] 配列) {
 int n = array.length; // 配列内の要素数 
 ( int i = n / 2 - 1 ; i >= 0 ; i--)の場合
ヒープ化(配列、i、n);
 } 
 
プライベート  voidヒープ化( int [] A, int idx, int max) {
 int left = 2 * idx + 1 ; // 左の子のインデックス（存在する場合）  
 int right = 2 * idx + 2 ; // 左の子のインデックス（存在する場合）  
 int largest = 0 ; // 3つのノードの中で最大の値を持つノードのインデックスを見つける 
 (左 < 最大値 && A[左] > A[idx])の場合
最大 = 左;
それ以外 
最大 = idx;
 if (right < max && A[right] > A[largest])
最大 = 右;
 （最大 != idx）の場合{
 swap(A, 最大, idx);
ヒープ化(A, 最大, 最大);
 }
 }
 }
 // [s, m] に s のみが存在すると仮定してヒープ関数を作成する 
 // 対応するキーワードはビッグヒープ定義を満たしていません。調整して [s, m] をビッグヒープにします ==============================================================  
公共 静的  void heapAdjust( int [] 配列, int s, int m) {
 // 0 の添え字要素を一時記憶単位として使用します 
配列[ 0 ] = 配列[s];
 // 大きな子ノードに沿ってフィルタリングする 
 ( int j = 2 * s; j <= m; j *= 2 )の場合{
 // j がより大きな子ノードの添え字であること、j < m であること、j+1 <= m であること、境界を越えないことを保証 
 (j < m && 配列[j] < 配列[j + 1 ])の場合{
 j++;
 }
配列[ 0 ] < 配列[j]) の場合
壊す;
 }
 // S が小さい場合は、大きい方の子を上に移動する必要があります 
配列[s] = 配列[j];
 // 大きい子の値は S 位置の小さい値になり、トップヒープの不均衡を引き起こす可能性があるため、その子が配置されているヒープはスクリーニングされます。  
 s = j;
 }
 // S ビットが大きい場合、値は変更されません。それ以外の場合、S ビットは 2*s、4*s などに移動します。 。 。  
配列[s] = 配列[ 0 ];