第二章中給出的Merge算法,本質(zhì)是初始化兩個(gè)數(shù)組分別保存前后兩個(gè)已經(jīng)排序好了的數(shù)組,然后逐個(gè)掃描比較兩個(gè)數(shù)組中的元素把元素放在原來(lái)數(shù)組的合適的位置上.
不知道之前有沒有人做過這個(gè)算法,比起書上的那個(gè)并不見得高明,在最壞的情況下要交換元素(N/2)*(N/2)也就是N的平方數(shù)量級(jí)(這里N是數(shù)組的大小),這個(gè)最壞的情況就是前面的數(shù)組中的元素都比后面數(shù)組的元素大.
雖然不見得是最好的,不過至少是自己思考的結(jié)果,放上來(lái)也許對(duì)別人有啟發(fā).
// 如何證明算法的正確性?
// 我改進(jìn)的merge算法
void Merge1(int array[], int start, int mid, int end)
{
// 思想:設(shè)置兩個(gè)哨兵,分別指向前后兩個(gè)數(shù)組,
// 逐個(gè)把前面的數(shù)組的元素和后面數(shù)組的元素進(jìn)行比較
// 如果前面的元素不比后面的元素大,那么前面數(shù)組的哨兵前移一位
// 否則,交換兩個(gè)元素,并且對(duì)后面的數(shù)組進(jìn)行掃描,確保新的元素放在合適的位置
// 當(dāng)前面的數(shù)組掃描完畢之后循環(huán)結(jié)束
for (int i = start; i < mid + 1; ++i)
{
if (array[i] > array[mid + 1])
{
swap(&array[i], &array[mid + 1]);
// 把新放入后面數(shù)組的元素放到合適的位置去
for (int j = mid +1; j + 1 <= end && array[j] > array[j + 1]; ++j)
{
swap(&array[j], &array[j + 1]);
}
}
}
}
// 書上的算法實(shí)現(xiàn)
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;
// 拷貝前半部分?jǐn)?shù)組
for (int i = 0; i < n1; i++)
{
temp1[i] = array[start + i];
}
// 拷貝后半部分?jǐn)?shù)組
for (int i = 0; i < n2; i++)
{
temp2[i] = array[mid + i + 1];
}
// 把后面的元素設(shè)置的很大
temp1[n1] = temp2[n2] = 1000;
// 逐個(gè)掃描兩部分?jǐn)?shù)組然后放到相應(yīng)的位置去
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);
}
}
對(duì)外的接口:Merge_Sort(array, start, end);
即:傳入一個(gè)數(shù)組,和起始位置中止位置,比如數(shù)組array[10],那么就是Merge_Sort(arrry,0,9)