バブルとクイックソートに関するコード例-＆＃＆チュートリアル-php.cn

バブルとクイックソートに関するコード例

Y2J

リリース： 2017-05-15 09:34:13

オリジナル

1522 人が閲覧しました

この記事では主に Java バブルソートとクイックソートのサンプルコードを紹介します。必要な方は参考にしてください

バブルソート

バブルソートは単純な並べ替えアルゴリズムです。ソート対象のシーケンスを繰り返し調べて、一度に 2 つの要素を比較し、順序が間違っている場合はそれらを交換します。配列を訪問する作業は、それ以上の交換が必要なくなるまで繰り返されます。これは、配列がソートされたことを意味します。このアルゴリズムの名前は、小さい要素がスワッピングによって配列の先頭にゆっくりと「浮動」するという事実に由来しています。

バブルソートのアルゴリズムは次のように実装されています: [ソート後、配列を小さいものから大きいものへと並べる]

　　/**
  * 冒泡排序
  * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 
  * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 
  * 针对所有的元素重复以上的步骤，除了最后一个。
  * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 
  * @param numbers 需要排序的整型数组
  */
 public static void bubbleSort(int[] numbers)
 {
  int temp = 0;
  int size = numbers.length;
  for(int i = 0 ; i < size-1; i ++)
  {
  for(int j = 0 ;j < size-1-i ; j++)
  {
   if(numbers[j] > numbers[j+1]) //交换两数位置
   {
   temp = numbers[j];
   numbers[j] = numbers[j+1];
   numbers[j+1] = temp;
   }
  }
  }
 }

ログイン後にコピー

クイックソート

クイックソートの基本的な考え方:

1 回のパスで並べ替える並べ替えるレコードを 2 つの独立した部分に分割し、レコードの一方の部分のキーワードが他方の部分のキーワードよりも小さいようにし、シーケンス全体が整うまで 2 つの部分の並べ替えを続けます。。

シーケンス全体を配列として考え、0番目の位置を中心軸とみなして、それより小さい場合は交換し、大きい場合はそれ以降の処理は行われません。交換する場合、小さい方の端と比較してください。彼より小さいものは交換されませんが、彼より大きいものは交換されます。このようにループを往復させて、左側が中心軸より小さく、右側が中心軸より大きいものを分割統治法で並べ替えます。それぞれ 2 つの独立したアレイ。

コードは次のように実装されます:

1. 中央の軸の位置を見つけます (最下位ビットが中央の軸として使用されます)

　　/**
  * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
  * 
  * @param numbers 带查找数组
  * @param low 开始位置
  * @param high 结束位置
  * @return 中轴所在位置
  */
 public static int getMiddle(int[] numbers, int low,int high)
 {
  int temp = numbers[low]; //数组的第一个作为中轴
  while(low < high)
  {
  while(low < high && numbers[high] > temp)
  {
   high--;
  }
  numbers[low] = numbers[high];//比中轴小的记录移到低端
  while(low < high && numbers[low] < temp)
  {
   low++;
  }
  numbers[high] = numbers[low] ; //比中轴大的记录移到高端
  }
  numbers[low] = temp ; //中轴记录到尾
  return low ; // 返回中轴的位置
 }

ログイン後にコピー

2. 再帰的形式の分割統治アルゴリズム:

 /**
  * 
  * @param numbers 带排序数组
  * @param low 开始位置
  * @param high 结束位置
  */
 public static void quickSort(int[] numbers,int low,int high)
 {
  if(low < high)
  {
  　　int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
  　　quickSort(numbers, low, middle-1); //对低字段表进行递归排序
  　　quickSort(numbers, middle+1, high); //对高字段表进行递归排序
  }
 }

ログイン後にコピー

3. クイックソートメソッド呼び出しを提供します

 /**
  * 快速排序
  * @param numbers 带排序数组
  */
 public static void quick(int[] numbers)
 {
  if(numbers.length > 0) //查看数组是否为空
  {
  quickSort(numbers, 0, numbers.length-1);
  }
 }

ログイン後にコピー

分析:

クイックソートは、一般に、同じ桁のソートメソッドの中で最高の平均パフォーマンスを持つと考えられています (O(nlog2n)) 。ただし、最初のシーケンスがキーによって順序付けされている場合、または基本的に順序付けされている場合、クイックソートはバブルソートに退化します。これを改善するために、通常は「スリーインワン方式」を使用してベンチマークレコードを選択します。つまり、2つのエンドポイントとソート間隔の中点を中心とする3つのレコードキーが支点レコードとして調整されます。クイックソートは不安定な並べ替え方法です。

メソッドテスト

印刷関数:

public static void printArr(int[] numbers)
 {
  for(int i = 0 ; i < numbers.length ; i ++ )
  {
  System.out.print(numbers[i] + ",");
  }
  System.out.println("");
 }

ログイン後にコピー

テスト:

　public static void main(String[] args) 
 {
  int[] numbers = {10,20,15,0,6,7,2,1,-5,55};
  System.out.print("排序前：");
  printArr(numbers);
  bubbleSort(numbers);
  System.out.print("冒泡排序后：");
  printArr(numbers);
  quick(numbers);
  System.out.print("快速排序后：");
  printArr(numbers);
 }

ログイン後にコピー

結果:

並べ替え前: 、6、7、2、 1,-5,55,

バブルソート後: -5,0,1,2,6,7,10,15,20,55,

クイックソート後: -5,0,1,2, 6 ,7,10,15,20,55,

【関連推奨事項】

1. 特別な推奨事項: 「php Programmer Toolbox」V0.1 バージョンのダウンロード

2. Java 無料ビデオチュートリアル

3. Java アノテーションの包括的な分析

以上がバブルとクイックソートに関するコード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。