減算でソートする

Question

私はこのソートアルゴリズムをJavaで開発していました。具体的には、このアルゴリズムは非常に大きな数の範囲で非常に大きなリストをソートするためのものです。あなたがそれを見たか、またはアルゴリズムを強化するための示唆があれば、それについて以下に何か言いたいことがありますか？私は間違っていない場合、それはあなたの標準問題バブルソートで、

public static int[] sort(int[] nums) 
{ 
    int lowest = Integer.MAX_VALUE; 

    for (int n : nums) 
    { 
     if (n < lowest) 
      lowest = n; 
    } 

    int index = 0; 

    int down = 0; 

    while (index < nums.length) 
    { 
     for (int i = index; i < nums.length; i++) 
     { 
      if (nums[i] == lowest) 
      { 
       int temp = nums[i] + down; 
       nums[i] = nums[index]; 
       nums[index] = temp; 

       index++; 
      } 
      else 
       nums[i]--; 
     } 
     down++; 
    } 

    return nums; 
} 

Answer 1

：私はここのコードを持っています。実装は簡単ですが、パフォーマンスが悪い：O（n^2）。 2つのネストされたループに注目してください。配列のサイズが大きくなると、アルゴリズムの実行時間が指数関数的に増加します。

Bubble Sortという名前が付けられています。これは、一番小さい値がアレイの前面に1つずつ「バブル」するためです。あなたはそれについての詳細を読むことができますon Wikipedia。

Answer 2

アルゴリズムは機能しているようですが、そのプロセスでは多くの不必要な作業があります。

基本的には、xを元に戻す前にxを減算してから、xを配列の最小値と最小値の差に置き換えようとするときに、必然的にxを減算する必要があります。たとえば、[99、1]とする。あなたのアルゴリズムでは、最初のforループ反復で配列を[98,1]に更新し、次にswap [1、98]を実行すると、ダウン変数を98に戻すために97回の反復を行う必要がありますそしてあなたの配列を[1,1]の状態にすると、それに98を加えて、それ自身でそれを入れ替えます。その興味深いテクニックは確かですが、それほど効率的ではありません。

特定のジョブの最適なアルゴリズムは、実際にあなたのデータについて知っているものによって決まります。他の並べ替えアルゴリズムを調べて、自分が何をしているのか、なぜそうするのかを感じてください。あなたが作ったアルゴリズムを見て、不要なステップを取り除こうとしていることを確認してください。

アルゴリズムを最初に強化するには、セットの中で最も低いものを見つけなくて、加算と減算のステップを削除します。あなたの数値がすべて特定の範囲内の整数であることがわかっている場合は、バケットソートを検討してください。それ以外の場合、マージまたはクイックソートアルゴリズムを試すことができます。