存档

2011年9月2日 的存档

Divide And Conquer

2011年9月2日 Jarod Lee 没有评论

Merge Sort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void Merge(int list[], int lowIndex, int highIndex, int midIndex)
{
   int *tempList = new int[highIndex-lowIndex+1];
   int firstLow = lowIndex;
   int secondLow = midIndex + 1;
   int index = 0;
   while(firstLow <= midIndex && secondLow <= highIndex)
   {
      if (list[firstLow] < list[secondLow])
         tempList[index++] = list[firstLow++];
      else
         tempList[index++] = list[secondLow++];
   }

   while (firstLow <= midIndex)
   {
      tempList[index++] = list[firstLow++];
   }

   while (secondLow <= highIndex)
   {
      tempList[index++] = list[secondLow++];
   }

   for (int ii = 0; ii < index; ii++)
   {
      list[lowIndex+ii] = tempList[ii];
   }
   delete[] tempList;
}

void MergeSort(int list[], int lowIndex, int highIndex)
{
   if (lowIndex < highIndex)
   {
      int midIndex = lowIndex + (highIndex-lowIndex)/2;
      MergeSort(list, lowIndex, midIndex);
      MergeSort(list, midIndex+1, highIndex);
      Merge(list, lowIndex, highIndex, midIndex);
   }
}
分类: C&&C++, Programming 标签: