この記事では主に 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 バージョンのダウンロード
以上がバブルとクイックソートに関するコード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。