求出一列数中的“逆序对”的个数;所谓“逆序对”就是指数的大小与其在序列中的顺序相反的一对数；例 如：<3,4,2,1,3>中“逆序对”有<3,2>,<3,1>,<4,2>,<4,1>,<4,3>这5个；要求时间复杂度为O(nlogn)；
#include <stdio.h>
void PrintTheRel(int i, int j);
void Sort(int Array[100], int end);
void GetTheRel(int Front[50],int len1, int Back[50], int len2);
void GetResult(int bundary, int source[100], int low, int high);
void main()
{
int Source[100];
int temp, length, times;
printf("Please enter the length:");
scanf("%d", &length);
printf("\nPlease enter the elements:");
for (temp=0; temp < length; temp++)
scanf("%d", &Source[temp]);
times = (int)(length/2);// 求界限
GetResult(times, Source, 0, length-1);
}
///////////////////////////////////////////////////////////////////////
//
// 函数名 : GetResult
// 功能描述 : 通过递归算法实现数列逆序列的求解
// 参数 : int bundary 二分法中涉及的分界点
// 参数 : int source[100] 一个待求序列
// 参数 : int low 序列的开始坐标
// 参数 : int high 序列的最后坐标
// 返回值 : void
//
///////////////////////////////////////////////////////////////////////
void GetResult(int bundary, int source[100], int low, int high)
{
int i,k=0;
int Front[50], Back[50];
if(high-low < 1) /*假如只有一个数就弹出递归堆栈 */
return;
else
{
for(i=low; i < bundary; i++)
Front[k++] = source[i];/*得到一个前一段的临时的数组 */
k=0;
for(i=bundary; i <= high; i++)
Back[k++] = source[i]; /*得到一个后一段的临时的数组 */
Sort(Front, bundary-1-low);/*对前一段进行排序 */
Sort(Back, high-bundary); /*对后一段进行排序 */
// 得到一组逆序对，这是求已经分好界的两边界的逆序对关系
GetTheRel(Front, bundary-low, Back, high - bundary + 1);
// 递归求左半部分
GetResult((int)((bundary-low +1) / 2)+low, source, low, bundary-1);
// 递归求右半部分
GetResult((int)((high-bundary+1) / 2)+bundary, source, bundary, high);
}
}
///////////////////////////////////////////////////////////////////////
//
// 函数名 : GetTheRel
// 功能描述 : 得到已经分成两半时的逆序对
// 参数 : int Front[50] 前一部分的己排序序列
// 参数 : int len1 前一个序列的长度
// 参数 : int Back[50] 后一部分的已排序序列
// 参数 : int len2 后一个序列的长度
// 返回值 : void
//
///////////////////////////////////////////////////////////////////////
void GetTheRel(int Front[50], int len1, int Back[50], int len2)
{
int i=0, j=0, k;
// 通过一次扫描可以将两个部分的逆序对全找出来
while ((i<len1) && (j <len2))
{
while (Front[i] > Back[j] && (i<len1) && (j <len2))
{
// 因为己经按递增排好序的所以将前半部分i下面的全部输出
for(k=i; k<len1;k++)
PrintTheRel(Front[k], Back[j]);
j++;/*当输出之后，后半部分指针加一 */
}
i++; /*前半部分没有比当前后半部分的值大将加一 */
}
}
///////////////////////////////////////////////////////////////////////
//
// 函数名 : Sort
// 功能描述 : 现在只是为了方便采用的是冒泡排序，可以采用O(nlogn)的算法。
// 参数 : int Array[100] 需要排序的数组
// 参数 : int end 数组默认从0开始，到end结束
// 返回值 : void
//
///////////////////////////////////////////////////////////////////////
void Sort(int Array[100], int end)
{
int i, j, temp;
// 自己认为这样的冒泡写法最清晰
for (i=end; i >0; i--)
for (j=0; j < i; j++)
if (Array[j] > Array[j+1])
{
temp = Array[j];
Array[j] = Array[j+1];
Array[j+1] = temp;
}
}
///////////////////////////////////////////////////////////////////////
//
// 函数名 : PrintTheRel
// 功能描述 : 格式打印
// 参数 : int i 参数1
// 参数 : int j 参数2
// 返回值 : void
//
///////////////////////////////////////////////////////////////////////
void PrintTheRel(int i, int j)
{
printf("<%d, %d>\n", i, j);
}
输入输出举例：
Please enter the length:10
Please enter the elements:9 8 7 6 5 4 3 2 1 0
<5, 0>
<6, 0>
<7, 0>
<8, 0>
<9, 0>
<5, 1>
<6, 1>
<7, 1>
<8, 1>
<9, 1>
<5, 2>
<6, 2>
<7, 2>
<8, 2>
<9, 2>
<5, 3>
<6, 3>
<7, 3>
<8, 3>
<9, 3>
<5, 4>
<6, 4>
<7, 4>
<8, 4>
<9, 4>
<7, 5>
<8, 5>
<9, 5>
<7, 6>
<8, 6>
<9, 6>
<8, 7>
<9, 7>
<9, 8>
<6, 5>
<3, 0>
<4, 0>
<3, 1>
<4, 1>
<3, 2>
<4, 2>
<4, 3>
<2, 0>
<2, 1>
<1, 0>
Press any key to continue
本文地址：http://com.8s8s.com/it/it32175.htm