第二章中给出的Merge算法,本质是初始化两个数组分别保存前后两个已经排序好了的数组,然后逐个扫描比较两个数组中的元素把元素放在原来数组的合适的位置上.
不知道之前有没有人做过这个算法,比起书上的那个并不见得高明,在最坏的情况下要交换元素(N/2)*(N/2)也就是N的平方数量级(这里N是数组的大小),这个最坏的情况就是前面的数组中的元素都比后面数组的元素大.
虽然不见得是最好的,不过至少是自己思考的结果,放上来也许对别人有启发.
// 如何证明算法的正确性?
// 我改进的merge算法
void Merge1(int array[], int start, int mid, int end)
{
// 思想:设置两个哨兵,分别指向前后两个数组,
// 逐个把前面的数组的元素和后面数组的元素进行比较
// 如果前面的元素不比后面的元素大,那么前面数组的哨兵前移一位
// 否则,交换两个元素,并且对后面的数组进行扫描,确保新的元素放在合适的位置
// 当前面的数组扫描完毕之后循环结束
for (int i = start; i < mid + 1; ++i)
{
if (array[i] > array[mid + 1])
{
swap(&array[i], &array[mid + 1]);
// 把新放入后面数组的元素放到合适的位置去
for (int j = mid +1; j + 1 <= end && array[j] > array[j + 1]; ++j)
{
swap(&array[j], &array[j + 1]);
}
}
}
}
// 书上的算法实现
void Merge(int array[], int start, int mid, int end)
{
int temp1[10], temp2[10];
int n1, n2;
n1 = mid - start + 1;
n2 = end - mid;
// 拷贝前半部分数组
for (int i = 0; i < n1; i++)
{
temp1[i] = array[start + i];
}
// 拷贝后半部分数组
for (int i = 0; i < n2; i++)
{
temp2[i] = array[mid + i + 1];
}
// 把后面的元素设置的很大
temp1[n1] = temp2[n2] = 1000;
// 逐个扫描两部分数组然后放到相应的位置去
for (int k = start, i = 0, j = 0; k <= end; k++)
{
if (temp1[i] <= temp2[j])
{
array[k] = temp1[i];
i++;
}
else
{
array[k] = temp2[j];
j++;
}
}
}
void Merge_Sort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
Merge_Sort(array, start, i);
Merge_Sort(array, i + 1, end);
Merge1(array, start, i, end);
}
}
对外的接口:Merge_Sort(array, start, end);
即:传入一个数组,和起始位置中止位置,比如数组array[10],那么就是Merge_Sort(arrry,0,9)