皆さん、こんにちは！さまざまなタイプのアルゴリズムが、思っているよりも頻繁にプロジェクトで使用されます。たとえば、手間をかけずにデータ内を移動できるように、特定のパラメータ (列) に従ってデータを並べ替える必要があります。したがって、採用面接中に何らかの基本的なアルゴリズムについて質問され、おそらくコードを使用してそれを実装するタスクが与えられるという事実は何も不思議ではありません。 ![面接で聞かれること: アルゴリズムのレビュー、パート 1 - 1]()
あなたがこのサイトにアクセスしているということは、Java で書いているのではないかと思います。したがって、今日は、いくつかの基本的なアルゴリズムと Java でのその実装の具体的な例について理解していただくことをお勧めします。一部の人とは、次のことを意味します。
![面接で聞かれること: アルゴリズムのレビュー、パート 1 ～ 2]()
Java での実装を見てみましょう。
![Java-университет]()
![面接で聞かれること: アルゴリズムのレビュー、パート 1 ～ 3]()
![面接で聞かれること: アルゴリズムのレビュー、パート 1 ～ 4]()
これを Java で見てみましょう。Item クラスは次のようになります。
![面接で聞かれること: アルゴリズムのレビュー、パート 1 ～ 5]()
- 配列ソートアルゴリズムの概要:
- バブルソート、
- 選択ソート、
- 挿入ソート、
- シェルソート、
- クイックソート、
- マージソート。
- 貪欲なアルゴリズム。
- 経路探索アルゴリズム:
- 深く這う
- 広い散歩道。
- トランスポートアルゴリズムはダイクストラアルゴリズムです。
1. ソートアルゴリズムの概要
バブルソート
この並べ替えアルゴリズムは主にその単純さで知られていますが、同時に実行速度が最も遅いアルゴリズムの 1 つです。例として、数値を昇順でバブルソートすることを考えてみましょう。ランダムに配置された数字のチェーンを想像してみましょう。チェーンの先頭から次の手順が実行されます。- 2 つの数値を比較します。
- 左側の数字が大きい場合は、それらを交換します。
- 位置を 1 つ右に移動します。
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}選択による並べ替え
このアルゴリズムはバブル ソートに似ていますが、動作が少し速くなります。もう一度例として、昇順に並べたい一連の数値を考えてみましょう。アルゴリズムの本質は、すべての数値を順番に調べて最小の要素を選択し、それを取得して左端の要素 (0 要素) と交換することです。ここではバブル ソートと似た状況になりますが、この場合、ソートされた要素は最小の要素になります。したがって、要素を通過する次のパスは、インデックス 1 の要素から始まります。これらのパスも、すべての要素が並べ替えられるまで繰り返されます。Java での実装:public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // внешний обычный цикл
int min = i;
for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // вставка отссортиованного числа, в положеную ему ячейку
array[i] = array[min];
array[min] = temp;
}
}
}挿入ソート
もう一度例として、昇順に並べたい一連の数値を考えてみましょう。このアルゴリズムは、マーカーを配置することで構成され、その左側に要素はすでに部分的にソートされています。アルゴリズムの各ステップで、要素の 1 つが選択され、既にソートされているシーケンス内の目的の位置に配置されます。したがって、すべての要素が確認されるまで、ソートされた部分は拡大し続けます。「既にソートされており、その後にマーカーを配置する必要がある要素のその部分はどこで入手できるのでしょうか?」と疑問に思うかもしれません。でも、最初の要素の配列はすでにソートされていますね。
Java での実装を見てみましょう。
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i - разделяющий маркер
int temp = array[i]; // делаем копию помеченного element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
array[j] = array[j - 1]; // сдвигаем элементы вправо
--j;
}
array[j] = temp; // вставляем отмеченный элемент, в положеное ему место
}
}
}シェルソート
この並べ替えは、その性質上、修正された挿入並べ替えです。私は何について話しているのでしょうか？順番に行きましょう。ステップが選択されますが、この選択にはさまざまなアプローチがあります。この問題についてはあまり詳しく説明しません。配列を半分に分割して特定の数値を取得しましょう - これが私たちのステップになります。したがって、配列に9 つの要素がある場合、ステップは9/2 = 4.5になります。配列インデックスは整数のみであるため、小数部分を破棄して4を取得します。このステップでは、グループの接続を作成します。要素のインデックスが 0 の場合、そのグループ内の次の要素のインデックスは0+4、つまり4 になります。3 番目の要素のインデックスは4+4、4 番目の要素のインデックスは 8+4などとなります。2 番目のグループの場合、最初の要素は 1,5,9... になります。3 番目と 4 番目のグループでも、状況はまったく同じになります。その結果、数値の配列{6,3,8,8,6,9,4,11,1}から4 つのグループが得られます: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} これらは一般配列内での位置を保持しますが、私たちにとっては同じグループのメンバーとしてマークされます: { 6 , 3 , 8 , 8 , 6 , 9 , 4 ,さらにこれらのグループ内で、上記の挿入ソート、その後グループは次のようになります: I - {1,6,6} II - {3,9} III - {4,8} IV - { 8 ,11} 一般的な配列では、グループが占めるセルは同じままですが、セル内の順序は上記のグループの順序に従って変わります: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } 配列はもう少し順序付けられていますね。次のステップは 2 で割られます: 4/2 = 2 2 つのグループがあります: I - {1,4,6,8,6} II - {3,8,9,11} B 一般配列: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } 挿入ソートアルゴリズムを使用して両方のグループを調べ、配列 { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8を取得します。これで、配列はほぼソートされました。アルゴリズムの最後の反復が残ります。ステップを 2 で割ります: 2/2 = 1。グループ、配列全体を取得します: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 }これを挿入ソート アルゴリズムに通して次の結果を取得します: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } このソートを Java コードで表示する方法を見てみましょう。public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) {//sorting вставкой внутри группы
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // уменьшаем наш шаг
}
}
}クイックソート
これは最も人気のあるアルゴリズムの 1 つであるため、特別な注意を払う価値があります。このアルゴリズムの本質は、要素のリストからピボット要素が選択されることです。基本的には、残りの値を並べ替える必要がある任意の要素です。それより小さい値は左側、それより大きい値は右側です。次に、右側と左側の部分もサポート要素によって選択され、同じことが起こります。値がこれらの要素に関連してソートされ、次にサポート要素が結果の部分から選択されます。これがソートされた結果が得られるまで繰り返されます。行。Java のこのアルゴリズムは再帰を使用して実装されます。public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0)// condition выхода из рекурсии, если длина массива равна 0
return;
if (min >= max) //выходим, так How нечего уже делить
return;
int middle = min + (max - min) / 2; // выбираем середину
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // относительно element middle определяемменьшие элементы слева, большие справа
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { //меняем местами
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // запускаем рекурсию с elementми меньшими чем middle
recursionFastSort(array, min, j);
if (max > i)// запускаем рекурсию с elementми большими чем middle
recursionFastSort(array, i, max);
}
}マージソート
この仕分けも人気です。これは、「分割統治」の原理に基づいて動作するアルゴリズムのタイプの 1 つを指します。このアルゴリズムでは、まずタスクを最小限の部分に分割します (クイック ソートもそのようなアルゴリズムの代表です)。では、このアルゴリズムの本質は何でしょうか?
分ける：
配列はほぼ同じサイズの 2 つの部分に分割され、これら 2 つの部分のそれぞれがさらに 2 つに分割され、分割できない最小部分が残るまで同様に繰り返されます。最も分割できない部分は、各配列に 1 つの要素がある場合です。これは、そのような配列が自動的にソート済みであるとみなされることを意味します。征服する:
ここで、アルゴリズムに名前を付けるプロセスが始まります (マージ)。これを行うには、結果として得られる 2 つの順序付けされた配列を取得し、それらを 1 つにマージします。この場合、2 つの配列の最初の要素のうち最小のものが結果の配列に書き込まれ、2 つの配列に要素がなくなるまでこの操作が繰り返されます。つまり、2 つの最小配列{6}と{4}がある場合、それらの値が比較され、結果が{4,6}として書き込まれます。ソートされた配列{4,6}と{2,8}がある場合、最初に値4と2が比較され、そのうちの2 が結果の配列に書き込まれます。この後、4と8を比較し、4を書き留め、最後に6と8を比較します。したがって、6 が書き込まれ、その後にのみ 8 が書き込まれます。その結果、配列 { 2,4,6,8}が得られます。これは Java コードではどのように見えるでしょうか? このアルゴリズムを処理するには、再帰を使用すると便利です。public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length);// массив для сортировки
int[] bufferArr = new int[array1.length];// буферный массив
return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
return sortArr;
}
// запускаем рекурсию, чтобы получить два отсортированных массива:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);
// Слияние отсортированных массивов:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}2. 貪欲なアルゴリズム
貪欲アルゴリズムは、各段階で局所的に最適な決定を行い、最終的なソリューションも最適であると想定するアプローチです。「最適な」ソリューションとは、特定のステップ/段階で最も明白かつ即座に利益をもたらすソリューションです。このアルゴリズムを検討するために、バックパックに関するかなり一般的な問題を選択します。少しの間、あなたが泥棒であるふりをしてみましょう。バックパックを背負って夜の店に侵入すると、目の前には盗める商品がたくさんあります。しかし同時に、バックパックの容量は限られており、従来のユニットは 30 個を超えません。同時に、バックパックに収まる最大限の価値のあるグッズ一式を持ち歩きたいと考えています。何を入れるかはどうやって決めるのですか？したがって、ナップザック問題の貪欲アルゴリズムは次のステップで構成されます (すべてのオブジェクトがナップザックに収まると仮定します)。- まだ触れていないアイテムの中から最も高価なものを選択します。
- バックパックに収まる場合はそこに入れ、そうでない場合は飛ばしてください。
- 全ての項目を整理しましたか？そうでない場合は、ポイント 1 に戻ります。イエスの場合、ここでの目的は完了したため、店から逃げます。
これを Java で見てみましょう。Item クラスは次のようになります。
public class Item implements Comparable<Item> {
private String name;
private int weight;
private int cost;
public Item(String name, int weight, int cost) {
this.name = name;
this.weight = weight;
this.cost = cost;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getCost() {
return cost;
}
@Override
public int compareTo(Item o) {
return this.cost > o.cost ? -1 : 1;
}
}public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentCost;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentCost = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentCost() {
return currentCost;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentCost += item.getCost();
}
}- maxWeightはバックパックの容量で、オブジェクトの作成時に設定されます。
- アイテム— バックパック内のオブジェクト。
- currentWeight、currentCost - バックパック内のすべての物の現在の重量とコスト。addItemメソッドで新しいアイテムを追加するときに増加します。
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("гитара",7, 800));
items.add(new Item("утюг",6, 500));
items.add(new Item("чайник",3, 300));
items.add(new Item("лампа",4, 500));
items.add(new Item("телевизор",15, 2000));
items.add(new Item("ваза",2, 450));
items.add(new Item("миксер",1, 400));
items.add(new Item("блендер",3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
}public static void fillBackpack(Bag bag, List<Item> items) {
for (Item item : items) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
bag.addItem(item);
}
}
}
バックパックの重量は 29、バックパック内の物の合計コストは 3700
実際、これは貪欲なアルゴリズムの例です。各ステップで局所的に最適なソリューションが選択され、最終的にはグローバルに最適なソリューションが得られます。私たちの場合、最良の選択肢は最も高価なアイテムです。しかし、これが最善の解決策なのでしょうか? ソリューションを少し近代化して、より高い総コストでバックパックを装備できるようにできると思いませんか? これをどのように行うかを見てみましょう。
public static void effectiveFillBackpack(Bag bag, List<Item> items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getCost() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());
バックパックの重量は 29、バックパックに入っているものの合計コストは 4150
少しは良くなりましたね。貪欲なアルゴリズムは、最終的なソリューションも最適であることを期待して、各ステップで局所的に最適な選択を行います。これは常に正当化されるわけではありませんが、多くの問題に対して貪欲なアルゴリズムは最適値を提供します。このアルゴリズムの時間計算量はO(N)で、これはかなり優れていますね。さて、これでこの記事の前半は終了です。グラフとそれに関連するアルゴリズムについて説明するこの記事の続きに興味がある場合は、ここで見つけることができます。
GO TO FULL VERSION