[[433768]]ソートアルゴリズムのトップ10のアイデアのまとめ手書きのソートアルゴリズムは面接中によく遭遇するので、この記事では簡単にまとめます。アルゴリズムの詳細については紹介せず、一般的な説明のみを行います。 交換クラス: ソートは要素をペアで交換することで実現されます 挿入: 数字を2つの部分に分割し、順序のない数字を順序付けられたシーケンスに1つずつ挿入します。 選択クラス: ソートするシーケンスから最小または最大の要素を見つけ、ソートされたシーケンスの後に置きます。 「カウンティング ソートと基数ソートはバケット ソートの特別な実装と見なすことができますが、どちらも要素を比較することによってソートを実現するものではありません。」 バブルソートバブルソートは最初から始まり、配列内の隣接する 2 つの要素を順番に比較します。後者の数値が前者の数値より大きい場合は 2 つの数値が交換され、そうでない場合は交換されません。各比較の後、配列内の最大の要素が最後に配置されます。 下の図に示すように、比較ラウンドのプロセスは次のようになります。 配列に n 個の要素がある場合、必要な比較は n 回だけであり、配列全体が整列します。 - 公共 静的voidバブルソート( int []a){
- // i 回の比較を実行する
- ( int i = 0; i < a.length - 1; i++) {
- ( int j = 0; j < a.length - 1 - i; j++) {
- もし(a[j] > a[j + 1])であれば{
- スワップ(a, j, j + 1);
- }
- }
- }
- }
-
- 公共 静的void swap( int [] a, int i, int j) {
- 整数 temp = a[i];
- 関数 i は、次の式で表されます。
- a[j] =一時;
- }
クイックソートクイックソートの実行プロセスは主に次の3つのステップに分かれています。 シーケンスから基数として数字を取ります 分割し、それより大きい数字はすべて右側に、それより小さいか等しい数字はすべて左側に置く 各間隔に数字が 1 つだけになるまで、左と右の間隔に対して 2 番目の手順を繰り返します。 - 公共 静的voidクイックソート( int []a, int 左、 int 右) {
- (左>=右)の場合{
- 戻る;
- }
- 整数 インデックス= sort(a, left , right );
- quickSort(a,左,インデックス- 1);
- quickSort(a,インデックス+ 1,右);
- }
-
- 公共 静的 intソート( int [] a, int 左、 int 右) {
- 整数 キー= a[左];
- (左<右){
- // high が指す位置から前方に検索して、 keyより小さいキーワードを持つ最初のレコードを見つけ、それをkeyと交換します。
- while (左<右&& a[右] >=キー) {
- 右
- }
- a[左] = a[右];
- // low が指す位置から逆方向に検索し、 keyより大きいキーワードを持つ最初のレコードを見つけて、 keyと交換します。
- while (左<右&& a[左] <=キー) {
- 左++;
- }
- a[右] = a[左];
- }
- //キー値を入れると、左と右が同じになります
- a[左] =キー;
- 戻る 左;
- }
次の図はパーティションのプロセスを示しています 「古典的なトップ K 面接の質問は、通常、クイック ソートとヒープ ソートを使用して解決できます。」次のセクションで分析してみましょう。 挿入ソート配列を順序付き配列と順序なし配列の両端に分割し、順序なし配列の値を順序なし配列に 1 つずつ挿入します。 下の図に示すように、3 6 7 は順序付き配列であり、4 2 は順序なし配列です。順序付けられていない配列に 4 と 2 を順番に挿入します。 図に示すように、4を挿入するプロセスは次のとおりです。 プログラムは順序付き配列と順序なし配列をどのように分割するのでしょうか? 最初の要素を順序付き配列と考えることができ、後続の値は順番に挿入することができます。 - 公共 静的void挿入ソート( int []a){
- ( int i = 1; i < a.length; i++) {
- ( int j = i; j > 0; j {
- (a[j] < a[j - 1]) である間 {
- スワップ(a, j, j - 1);
- }
- }
- }
- }
-
- 公共 静的void swap( int [] a, int i, int j) {
- 整数 temp = a[i];
- 関数 i は、次の式で表されます。
- a[j] =一時;
- }
「無駄なスワッピング処理がたくさんあることがわかります。スワップする要素を直接特定して、スワップを実行できます。挿入ソート コードの改善」 - 公共 静的void挿入ソート( int []a){
- ( int i = 1; i < a.length; i++) {
- 整数 temp = a[i];
- 整数j;
- // 適切な挿入位置を見つけて挿入する
- (j = i - 1; j >= 0 && a[j] > temp ; j の場合{
- 1 は 0 です。
- }
- a[j + 1] =温度;
- }
- }
シェルソート「シェルソートは挿入ソートをベースに改良したアルゴリズムです。データの移動回数が多すぎると効率が悪くなります。そこで、まず配列全体を整然とした状態にして(移動範囲を最初は大きくし、後半は小さくする)、移動回数を減らして効率を上げます。」 元のアドレス: Blog Park「グラフィカルソートアルゴリズム (II) - ヒルソート」 - 公共 静的voidシェルソート( int []a){
- ( intステップ = a.length / 2; ステップ > 0; ステップ /= 2) {
- ( int i = ステップ; i < a.length; i++) {
- 整数 temp = a[i];
- 整数j;
- ( j = i - ステップ; j >= 0 && a[j] > temp ; j -= ステップ) {
- a[j + ステップ] = a[j];
- }
- a[j + ステップ] = temp ;
- }
- }
- }
選択ソート最初の反復では、最小の値が配列の位置 0 に配置されます。2 番目の反復では、2 番目に小さい値が配列の位置 1 に配置されます。 - 公共 静的void選択ソート( int []a){
- ( int i = 0; i < a.length; i++) {
- 整数 インデックス= i;
- ( int j = i + 1; j < a.length; j++) {
- if (a[インデックス] > a[j]) {
- インデックス= j;
- }
- }
- if (インデックス!= i ) {
- swap(a,インデックス, i);
- }
- }
- }
-
- 公共 静的void swap( int [] a, int i, int j) {
- 整数 temp = a[i];
- 関数 i は、次の式で表されます。
- a[j] =一時;
- }
ヒープソートヒープソートを手動で記述してみましょう。まず、ヒープとは何かを説明しましょう。 - ヒープは、次の特性を満たす必要があるデータ構造です。
- ヒープは完全な二分木です(ノードが生成される順序は左から右、上から下です)
ヒープ内のノードの値は、常にその親ノードの値より大きくも小さくもありません。 「最大のルート ノードを持つヒープは最大ヒープまたはビッグ ルート ヒープと呼ばれ、最小のルート ノードを持つヒープは最小ヒープまたはスモール ルート ヒープと呼ばれます。」 大きな根杭と小さな根杭を下図に示します。 次のような完全な二分木があるとします。これをヒープに合わせて調整するにはどうすればよいでしょうか。 10 とその子ノードは条件を満たし、3 とその子ノードは条件を満たし、ノード 4 は条件を満たしていないことがわかります。 「そこで、ノード 4 を調整する必要があります。調整プロセスはヒープ化と呼ばれます。」 - ノード4の左右のノードから大きなノード(つまりノード10)を探し、それをノード4と交換する。
- 交換後、交換したノードが条件を満たさなくなる可能性があるため、調整が必要になります(調整プロセスは1と同様です)
- 最後に、ノード 4 と 5 が交換されます。バイナリツリーがヒープになる
実際の開発プロセスでは、ヒープを表すためにツリー構造ではなく配列を使用します。下付き文字の特性から、次のような規則をまとめることができる。 配列内のノードのノードインデックスがiの場合、 親ノードの添え字は: parent = (i - 1) / 2 左ノードの添え字は: c1 = 2 * i + 1 右ノードの添え字は: c2 = 2 * i + 2 したがって、上図のヒープは[10, 5, 3, 4, 1, 2, 0]という配列で表されます。 ヒープを配列で表現する方法がわかったので、次のノード 4 をヒープ化するプロセスを記述してみましょう。 - /**
- * @param 配列
- * @param n 配列の長さ
- * @param i ヒープ化されるノード
- */
- 公共 静的voidヒープ化( int []a, intn , inti ){
- // 再帰終了
- もし (i >= n) {
- 戻る;
- }
- //左ノードの添え字
- c1 = 2 * i + 1;整数
- // 右ノードの添え字
- 整数c2 = 2 * i + 2;
- 整数 最大値= i;
- c1 < n && a[c1] > a[ max ]の場合{
- 最大値c1;
- }
- c2 < n && a[c2] > a[ max ]の場合{
- 最大値c2;
- }
- //左ノードと右ノードの最大値を親ノードと交換する
- (最大値!= i)の場合{
- swap(a, max , i);
- ヒープ化(a, n, max );
- }
- }
- @テスト
- パブリックボイドヒープ化() {
- int [] 配列 = 新しいint []{4, 10, 3, 5, 1, 2};
- // 調整後: 10、5、3、4、1、2
- HeapSort.heapify(配列、配列の長さ、0);
「完全な二分木をヒープに変換するにはどうすればよいでしょうか?」 「非リーフ ノードを左から右、下から上にヒープ化するだけです。」次の図に示すように、10、3、4 を順番にヒープ化するだけです。 - 公共 静的voidビルドツリー( int []a){
- // 最後の非リーフノードを見つける
- int lastNode = a.length - 1;
- int親 = (lastNode - 1) / 2;
- ( int i = 親; i >= 0; i {
- ヒープ化(a, a.length, i);
- }
- }
テストしてみましょう - @テスト
- パブリックボイドビルドツリー() {
- int [] 配列 = 新しいint []{3, 5, 7, 2, 4, 9, 6};
- // 9 5 7 2 4 3 6
- HeapSort.buildTree(配列);
- }
ヒープがどのように生成され、どのように調整されるかがわかれば、ヒープソートのプロセスを分析するのは非常に簡単になります。 最大ヒープを例にとると、最大値はルートノードである必要があります。 - ルートノードを最後のリーフノードと交換し、リーフノードをヒープから削除します。
- このとき、ルートノードは要件を満たしていないため、ルートノードをヒープ化した後、再びヒープになります。
- 手順 1 と 2 を繰り返して、残りのノードの中で最大値を見つけます。
毎回見つかる最大値は配列の最後の位置にあるため、実際にヒープを削除する必要はありません。ヒープ化するときに、配列の長さを徐々に減らすだけで済みます。最終的な配列は昇順です - 公共 静的voidヒープソート( int []a){
- // 最初にヒープを構築します
- ツリーを構築します。
- // 毎回、ルートノードとヒープの最後のノードを交換し、ヒープ化します
- ( int i = a.length - 1; i >= 0; i {
- スワップ(a, i, 0);
- ヒープ化(a, i, 0);
- }
- }
最終的なヒープソートコードは次のようになります。 - パブリッククラスHeapSort {
-
- 公共 静的voidヒープソート( int []a){
- ツリーを構築します。
- ( int i = a.length - 1; i >= 0; i {
- スワップ(a, i, 0);
- ヒープ化(a, i, 0);
- }
- }
-
- 公共 静的voidビルドツリー( int []a){
- // 最後の非リーフノードを見つける
- int lastNode = a.length - 1;
- int親 = (lastNode - 1) / 2;
- ( int i = 親; i >= 0; i {
- ヒープ化(a, a.length, i);
- }
- }
-
- /**
- * @param 配列
- * @param n 配列の長さ
- * @param i ヒープ化されるノード
- */
- 公共 静的voidヒープ化( int []a, intn , inti ){
- もし (i >= n) {
- 戻る;
- }
- c1 = 2 * i + 1;整数
- 整数c2 = 2 * i + 2;
- 整数 最大値= i;
- c1 < n && a[c1] > a[ max ]の場合{
- 最大値c1;
- }
- c2 < n && a[c2] > a[ max ]の場合{
- 最大値c2;
- }
- (最大値!= i)の場合{
- swap(a, max , i);
- ヒープ化(a, n, max );
- }
- }
-
- 公共 静的void swap( int [] a, int i, int j) {
- 整数 temp = a[i];
- 関数 i は、次の式で表されます。
- a[j] =一時;
- }
- }
ここでは、ヒープの構築方法とヒープソートのプロセスがどのようなものかのみを説明します。 「完全なヒープ実装には、ノードを挿入し、ルート ノードを削除するメソッドも提供する必要があります。」実装は書きませんが、図を使ってプロセスを説明します。興味があれば書き留めておいてもいいでしょう。「ほとんどの言語には組み込みのヒープ実装、つまり優先度キュー (Java では PriorityQueue) があるので、ヒープが必要なときは PriorityQueue を使うだけで済みます。」 ヒープにノードを挿入する ノードがヒープ内に挿入されると、挿入された位置は完全なバイナリ ツリーの最後の位置になります。たとえば、値 8 を持つ新しいノードを挿入します。 8 をその親ノードと比較します。8 > 5 の場合、新しいノードを浮かせて、親ノードと位置を交換します。 スワップ後、親ノードとの比較を続けます。8<9 の場合、調整は必要ありません。 ヒープ削除ノード ヒープからノードが削除されると、ヒープの最上部のノードが削除されます。例えば、最大ヒープの9番目のノードを削除します ヒープ構造を維持するために、ヒープの最後のノード 6 をヒープの先頭に追加します。 次に、ヒープの最上位ノードをその左と右の子ノードと比較します。左と右の子のうち最大のノードがノード 6 より大きい場合、ノード 6 は下に移動します。 次に、左のノードと右のノードを比較します。3<6 の場合、調整は必要ありません。 最初のK高周波要素 タイトルアドレス: オファー40。kの最小数 整数配列 arr を入力し、その中の最小の k 個の数値を見つけます。たとえば、4、5、1、6、2、7、3、8 の 8 つの数字を入力した場合、最小の 4 つの数字は 1、2、3、4 になります。 - 入力: arr = [3,2,1]、k = 2
- 出力: [1,2] または [2,1]
制限: 0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000 "ヒープ" 大きなトップ ヒープを維持します。ヒープ内に k に対して十分な要素がない場合は、ヒープに要素を追加し続けます。ヒープ内の要素が k 以上になった場合は、ヒープの最上部の要素と新しく追加された要素を比較します。新しく追加された要素がヒープの最上部の要素よりも小さい場合は、ヒープの最上部の要素を削除し、新しく追加された要素をヒープに配置する必要があります。これにより、ヒープ内の要素は常に最小の k になります。 - 公共 int [] getLeastNumbers( int [] arr, int k) {
- (arr.length == 0 || k == 0)の場合{
- 新しいint [0]を返します。
- }
- PriorityQueue<整数> キュー = 新しい PriorityQueue<>((num1, num2) -> num2 - num1);
- for ( int num : arr ) {
- キューサイズ() < kの場合
- キューに数値を追加します。
- }そうでない場合 (num < queue.peek()) {
- キュー.ポーリング();
- キューに数値を追加します。
- }
- }
- int [] 結果 = 新しいint [k];
- ( int i = 0; i < k; i++) {
- 結果[i] = queue.poll();
- }
- 結果を返します。
- }
「クイックソート」 クイックソートのプロセスを変更するだけで済みます。配列全体をソートするのではなく、ベンチマーク値と k の位置に基づいて、左セグメントと右セグメントのどちらをソートするかを決定できます。 - クラスソリューション{
-
- 公共 int [] getLeastNumbers( int [] arr, int k) {
- (arr.length == 0 || k == 0)の場合{
- 新しいint [0]を返します。
- }
- quickSort(arr, 0, arr.length - 1, k - 1) を返します。
- }
-
- 公共 int [] クイックソート( int [] 数値, int 左、 int 右、 int k) {
- 整数 インデックス= sort(nums, left , right );
- if (インデックス== k ) {
- Arrays.copyOf(nums, k + 1) を返します。
- }
- //インデックスと kの位置に基づいて、左または右のセグメントをカットするかどうかを決定します
- 戻る index > k の場合、quickSort(nums, left , index - 1, k) : quickSort(nums, index + 1, right , k);
- }
-
- 公共 intソート( int [] a, int 左、 int 右) {
- 整数 キー= a[左];
- (左<右){
- while (左<右&& a[右] >=キー) {
- 右
- }
- a[左] = a[右];
- while (左<右&& a[左] <=キー) {
- 左++;
- }
- a[右] = a[左];
- }
- a[左] =キー;
- 戻る 左;
- }
- }
「数え順」 質問には 0 <= arr[i] <= 10000 という条件があり、これは配列内の要素が比較的集中していることを意味するため、カウントソートを使用してこの問題を解決できます。 arr[i] の最大値は 10000 なので、毎回 10001 の配列を直接開きます。 - 公共 int [] getLeastNumbers( int [] arr, int k) {
- (arr.length == 0 || k == 0)の場合{
- 新しいint [0]を返します。
- }
- int [] countArray = 新しいint [10001];
- for ( int num : arr ) {
- countArray[num]++;
- }
- int [] 結果 = 新しいint [k];
- 整数 インデックス= 0;
- ( int i = 0; i < countArray.length &&インデックス< k; i++) {
- countArray[i] > 0 &&インデックス< k である間 {
- countArray[i]
- 結果[インデックス++] = i;
- }
- }
- 結果を返します。
- }
マージソートまず配列を 1 つの要素だけに分割し、分割した配列を結合します。結合時に行うべき主なことは、結合した配列が正しい順序になっていることを確認することです。結合が完了すると、配列全体が正しい順序になります。 - 公共 静的void mergeSort( int [] a, int 左、 int 右) {
- // 配列を1つの要素のみを持つセグメントに分割します
- if (左==右) {
- 戻る;
- }
- int中央 = (左+右) / 2;
- mergeSort(a, left , mid);
- mergeSort(a, 中央 + 1,右);
- マージ(a、左、中央、右);
- }
-
- 公共 静的voidマージ( int []a, int 左、 int中央、 int 右) {
- int [] temp = 新しいint [右-左+ 1];
- int i =左;
- 整数j = ミッド + 1;
- 整数k = 0;
- (i <= 中央 && j <=右) の間 {
- もし(a[i] < a[j])であれば{
- temp [k++] = a[i++];
- }それ以外{
- temp [k++] = a[j++];
- }
- }
- // 左の配列の残りの値をコピーします
- (i <= 中間) {
- temp [k++] = a[i++];
- }
- // 右側の配列の残りの値をコピーします
- (j <=右) の間 {
- temp [k++] = a[j++];
- }
- 整数 インデックス= 0;
- (左<=右){
- a[左++] = temp [インデックス++];
- }
- }
カウントソート新しい配列が作成され、num[i]は元の配列に値iを持つ数値がnum[i]個あることを意味します。したがって、このアルゴリズムには大きな制限があり、配列要素の範囲が大きくないシナリオにのみ適しています。 - 公共 静的void countingSort( int [] a) {
- 整数 最大値= Integer.MIN_VALUE ;
- for ( int数値: a ) {
- max =整数。max ( max , num) ;
- }
- int [] count = 新しいint [ max + 1];
- for ( int num : a ) {
- [数値]++をカウントします。
- }
- 整数 インデックス= 0;
- ( int i = 0; i < count .length; i++) {
- (カウント[i]> 0){
- a[インデックス++] = i;
- カウント[i]
- }
- }
- }
上記のアルゴリズムには実は欠陥があります。配列内の要素が 10000、10001、10002 の場合、サイズ 10003 の配列を作成する必要がありますが、これは非現実的です。したがって、マッピング関係num[i]を変更して、元の配列内のi+minの値の数がnum[i]であることを意味することができます。 上級バージョン - 公共 静的void countingSort( int [] a) {
- 整数 最大値= Integer.MIN_VALUE ;
- 整数 最小値= Integer.MAX_VALUE ;
- for ( int num : a ) {
- max =整数。max ( max , num) ;
- min =整数。min ( min , num) ;
- }
- int [] count = 新しいint [最大値-最小値+ 1];
- for ( int num : a ) {
- count [数値 -最小値]++;
- }
- 整数 インデックス= 0;
- ( int i = 0; i < count .length; i++) {
- (カウント[i]> 0){
- a[インデックス++] = i + min ;
- カウント[i]
- }
- }
- }
「面接の過程では、配列の過半数を見つける問題によく遭遇しますが、カウントソートの考え方を使ってそれを解決することができます。」 基数ソート「面接ではスナップショットやマージソートについてたくさん聞かれました。応用シナリオも豊富です。」基数ソートについては基本的に聞かれなかったので説明はしません。 バケットソート「先ほど述べたカウンティング ソートと基数ソートは、バケット ソートの考え方を特別に表現したものと言えます。つまり、配列要素を比較する必要がないということです。」基本的には聞かれなかったので説明しませんでした。 さまざまなソートアルゴリズムの応用面接でよく聞かれるトップ k の質問については、まず並べ替えてからトップ k の要素を見つけることができます。さまざまなソート アルゴリズムの効率は、次の図に示されています。「より効率的なアイデアは、ヒープ ソートとクイック ソートを使用することです。Top K 問題を問う方法は多数ありますが、上位 K 個の最大要素、上位 K 個の最小要素、上位 K 個の高頻度要素を見つけるなど、基本的なアイデアは同じです。」 この記事はWeChatのパブリックアカウント「Java Knowledge Hall」から転載したものです。以下のQRコードからフォローできます。この記事を転載する場合は、Java Knowledge Hall 公式アカウントまでご連絡ください。 |