Java クラシックアルゴリズム: カクテルソート

ソートアルゴリズムの中では、バブルソートが古典的です。カクテル ソートは、シェーカー ソートとも呼ばれ、改良されたバブル ソートです。以下はJavaで実装されています。

質問：

長さ n の配列があります。配列内の要素を小さいものから大きいものの順に並べ替えます。

アイデア:

カクテルソーティングのプロセスは次のとおりです。

（１）まず、配列を左から右へ（昇順で）バブルソートし、最大の要素を右端に移動します。

（２）次に、配列を右から左へ（降順）バブルソートし、最小の要素を左端に移動します。

このように、バブルの方向を順番に変えて、ソートされていない要素の範囲を継続的に狭めていきます。

例: 45、19、77、81、13、28、18、19、77 を並べ替える

左から右へ: 19、45、77、13、28、18、19、77、81

右から左へ: 13、19、45、77、18、28、19、77、81

左から右へ: 13、19、45、18、28、18、77、77、81

右から左へ: 13、18、19、45、18、28、77、77、81

左から右へ: 13、18、19、18、28、45、77、77、81

右から左へ: 13、18、18、19、28、45、77、77、81

この時点で、これ以上の交換は行われず、ソートは完了します。

コアコード:

静的  voidソート( int [] 配列) {
 int top = 配列の長さ - 1 ;
 int下 = 0 ;
ブールフラグ = true ;
整数i, j;
 while (フラグ) {
フラグ = false ;
 //小さいものから大きいものへ、昇順 
 (i = 下; i < 上; i++) {
 （配列＞配列[i + 1 ]）の場合{
 swap(配列、i、i + 1 );
フラグ = true ;
 }
 }
トップ - ;
 //大きいものから小さいものへ、降順 
 (j = 上; j > 下; j--) {
 （配列[j] < 配列[j - 1 ]）の場合{
 swap(配列、j、j - 1 );
フラグ = true ;
 }
 }
下++;
 }
 }
完全なコード:
パッケージcom.icescut.classic.algorithm;
公共 クラスCocktailSort {
公共 静的  void main(String[] args) {
 int [] array = { 10 , - 3 , 5 , 34 , - 34 , 5 , 0 , 9 }; // テストデータ 
ソート(配列);
 for ( int el : 配列) {
 System.out.print(el + " " );
 }
 }
静的  voidソート( int [] 配列) {
 int top = 配列の長さ - 1 ;
 int下 = 0 ;
ブールフラグ = true ;
整数i, j;
 while (フラグ) {
フラグ = false ;
 //小さいものから大きいものへ、昇順 
 (i = 下; i < 上; i++) {
 （配列＞配列[i + 1 ]）の場合{
 swap(配列、i、i + 1 );
フラグ = true ;
 }
 }
トップ - ;
 //大きいものから小さいものへ、降順 
 (j = 上; j > 下; j--) {
 （配列[j] < 配列[j - 1 ]）の場合{
 swap(配列、j、j - 1 );
フラグ = true ;
 }
 }
下++;
 }
 }
プライベート 静的  void swap( int [] 配列, int i, int j) {
 int tmp = 配列;
配列 = 配列[j];
配列[j] = tmp;
 }
 }

【編集者のおすすめ】

1. C++ ソートに関する 4 つの古典的な講義: 挿入ソート
2. C++ ソートに関する 4 つの古典的な講義: シェル ソート
3. C++ ソートに関する 4 つの古典的な講義: パート 3: 交換ソート
4. C++ ソートの 4 つの選択ソートによる古典的な 4 つの講義