0

以下は私のクラスの挿入ソートについてのpptで書かれています：

void insertionSort(DataType theArray[], int n) {
  for (int unsorted = 1; unsorted < n; ++unsorted) {

    DataType nextItem = theArray[unsorted];
    int loc = unsorted;

    for (;(loc > 0) && (theArray[loc-1] > nextItem); --loc)
       theArray[loc] = theArray[loc-1];

    theArray[loc] = nextItem;
  }
}

-

Running time depends on not only the size of the array but also the contents of the array.
Best-case:       O(n)
Array is already sorted in ascending order.
Inner loop will not be executed.
>>>> The number of moves: 2*(n-1)        O(n)
>>>> The number of key comparisons: (n-1)    O(n)
Worst-case:      O(n2)
Array is in reverse order:
Inner loop is executed p-1 times, for p = 2,3, …, n
The number of moves: 2*(n-1)+(1+2+...+n-1)= 2*(n-1)+ n*(n-1)/2   O(n2)
The number of key comparisons: (1+2+...+n-1)= n*(n-1)/2          O(n2)
Average-case:    O(n2)
We have to look at all possible initial data organizations.
So, Insertion Sort is O(n2)

移動とキーの比較は正確には何ですか？Googleで説明が見つかりませんでした。

4

2 に答える 2

0

移動は、データをソートするために実行する必要のあるスワップの数であり、キーは、比較されるデータです。

于 2012-10-07T09:28:43.040 に答える
0

最初にアルゴリズムについて説明します。

  • ある時点で、配列の2つの部分があると仮定します。index 0to indexloc - 1は昇順でソートされ、 indextoはソートさlocれn - 1ていません。
  • の要素から開始しloc、配列のソートされた部分で正しい場所を見つけて、そこに挿入します。

したがって、2つのループがあります。

  1. loc = 1最初の外側のループは、 toで始まりloc = n、基本的に配列をソートされた部分とソートされていない部分に分割します。
  2. 2番目の内側のループはloc、配列のソートされた部分（0to loc - 1）で要素の位置を見つけます。

内側のループでは、正しい場所を見つけるために、要素をloc、最悪の場合、配列のソートされた部分のすべての要素と比較する必要があります。これは重要な比較です。

挿入するには、の要素の配列のソートされた部分にボイドを作成する必要がありますloc。これは、ソートされた部分の各要素を次の要素に交換することによって行われます。これは動きです。

于 2012-10-07T09:30:13.717 に答える