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)

什么是移动和关键比较？我在谷歌上找不到解释。

4

2 回答 2

0

移动是为了对数据进行排序而必须执行的交换次数，键是被匹配的数据。

于 2012-10-07T09:28:43.040 回答
0

让我先说一下算法。

  • 假设在给定时间数组有两部分。index 0to indexloc - 1按升序排序， index locton - 1未排序。
  • 从元素 at 开始，loc在数组的排序部分找到它的正确位置并将其插入那里。

所以现在有两个循环：

  1. loc = 1第一个外部循环以to开头loc = n，基本上将数组划分为已排序和未排序的部分。
  2. 第二个内部循环在loc数组的排序部分 ( 0to loc - 1) 中找到元素的位置。

对于内部循环，要找到正确的位置，您必须将元素loc与在最坏的情况下，数组排序部分中的所有元素进行比较。这是关键比较。

要插入，您必须在数组的已排序部分中为元素 at 创建一个 void loc。这是通过将排序部分中的每个元素交换到下一个元素来完成的。这是动。

于 2012-10-07T09:30:13.717 回答