如何为通用的ArrayList实现插入排序方法?

huangapple go评论71阅读模式
英文:

How Do I Implement an Insertion Sort Method for A Generic ArrayList?

问题

@Override
public <T extends Comparable<T>> void insertionSort(ArrayList<T> data) {
    int i, x = 0;
    T key;
    for (i = 1; i < data.size(); i++) {
        key = data.get(i);
        x = i - 1;
        while (x >= 0 && data.get(x).compareTo(key) > 0) {
            data.set(x + 1, data.get(x));
            x--;
        }
        data.set(x + 1, key);
    }
}
英文:

I am meant to create a simple insertion sort method which sorts a series of generic names into alphabetical order. This should be simple, and I have already reviewed many other examples of insertion sort online, including on this site, yet I still cannot seem to obtain the correct output despite comparing my code, line-by-line, with other versions and being unable to identify what I have done different than some supposedly successful insertion sort methods.

The following code is the main class which I am not meant to alter:

  public static void main(String[] args) {
    GenericTools t = new ToolBox();
    ArrayList&lt;String&gt; data = new ArrayList&lt;&gt;();
    data.add(&quot;Carlos&quot;);
    data.add(&quot;Alice&quot;);
    data.add(&quot;Bob&quot;);
    data.add(&quot;Zebra&quot;);
    data.add(&quot;Fred&quot;);

    t.insertionSort(data);
    data.forEach(x -&gt; System.out.println(x));
}

And, this is the GenericTools interface referenced above, for the record:

public &lt;T&gt; void swap(ArrayList&lt;T&gt; data, int p1, int p2);

Finally, this is my code which should be correctly sorting this list:

@Override
    public &lt;T extends Comparable&lt;T&gt;&gt; void insertionSort(ArrayList&lt;T&gt; data) {
        int i, x =0;
        T key;
        for (i=1;i&lt;data.size();i++){
            key= data.get(i);
            while (x&gt;=0 &amp;&amp; data.get(x).compareTo(key) &gt; 0){
                data.set(x+1,data.get(i));
                x--;
            }
            data.set(x+1,key);
        }
      }

However, instead produces the following output:

Fred
Alice
Bob
Zebra
Fred

As opposed to correct output of:

Alice
Bob
Carlos
Fred
Zebra

答案1

得分: 1

所以你打算在 ArrayList 的已排序部分(索引从 0 到 i - 1)上进行迭代,以降序的方式,并且同时将相对大于 key 的元素向右移动一个位置,同时找到放置 key(data.get(i))的正确位置。你的算法是正确的,但在那里你犯了两个简单的错误:

  1. 你忘记在内部的 while 循环之前将变量 x 初始化为 i - 1

  2. 当当前元素在字母上大于 key 时,你应该将 当前元素(data.get(x))右移一步,而不是 data.get(i)

    @Override
    public <T extends Comparable<T>> void insertionSort(ArrayList<T> data) {
        int i, x = 0;
        T key;
        for (i = 1; i < data.size(); i++) {
            key = data.get(i);
            x = i - 1; // 将 x 设置为 i - 1
            while (x >= 0 && data.get(x).compareTo(key) > 0) {
                data.set(x + 1, data.get(x)); // 移动 data.get(x) 而不是 data.get(i)。
                x--;
            }
            data.set(x + 1, key);
        }
    }
英文:

So you intended to iterate over the sorted part (indices between 0 and i - 1) of the ArrayList in descending order and shift elements relatively greater than key in right direction by one position at the same time, and find the correct position where to put the key (data.get(i)). Your algorithm is right, but there are two simple mistakes you've made there:

  1. you forgot to initialize variable x to i - 1 before inner while-loop.

  2. when current element is alphabetically greater than the key, you should move current element (data.get(x)) one step right instead of data.get(i).

    @Override
    public &lt;T extends Comparable&lt;T&gt;&gt; void insertionSort(ArrayList&lt;T&gt; data) {
        int i, x =0;
        T key;
        for (i=1; i&lt;data.size(); i++){
            key= data.get(i);
            x = i - 1; // set x to i - 1
            while (x &gt;= 0 &amp;&amp; data.get(x).compareTo(key) &gt; 0){
                data.set(x+1, data.get(x)); // move data.get(x) instead of data.get(i).
                x--;
            }
            data.set(x+1,key);
        }
    }

huangapple
  • 本文由 发表于 2020年10月24日 05:46:47
  • 转载请务必保留本文链接:https://go.coder-hub.com/64507683.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定