資源簡(jiǎn)介
數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)題 5.1 排序
★實(shí)驗(yàn)任務(wù)
通過交換元素位置實(shí)現(xiàn)排序的算法通常稱為交換排序算法。如果只允許交換相鄰元素的位置，則稱為相鄰交換排序算法，如冒泡排序算法。
給定 n 個(gè)待排成升序的整數(shù)，求出相鄰交換排序算法交換元素位置的最少次數(shù)。
★數(shù)據(jù)輸入
輸入第一行為一個(gè)正整數(shù) n (n < =500000)
輸入第二行為 n 個(gè)整數(shù)，這些整數(shù)可能有相同的。
★數(shù)據(jù)輸出
輸出相鄰交換排序算法交換元素位置的最少次數(shù)。
PS:請(qǐng)用 long long 來計(jì)算次數(shù),輸入輸出請(qǐng)用 scanf，printf
★實(shí)驗(yàn)任務(wù)
通過交換元素位置實(shí)現(xiàn)排序的算法通常稱為交換排序算法。如果只允許交換相鄰元素的位置，則稱為相鄰交換排序算法，如冒泡排序算法。
給定 n 個(gè)待排成升序的整數(shù)，求出相鄰交換排序算法交換元素位置的最少次數(shù)。
★數(shù)據(jù)輸入
輸入第一行為一個(gè)正整數(shù) n (n < =500000)
輸入第二行為 n 個(gè)整數(shù)，這些整數(shù)可能有相同的。
★數(shù)據(jù)輸出
輸出相鄰交換排序算法交換元素位置的最少次數(shù)。
PS:請(qǐng)用 long long 來計(jì)算次數(shù),輸入輸出請(qǐng)用 scanf，printf
代碼片段和文件信息
#include
using?namespace?std;
int?a[500005]m[500005]n;
long?long?ans=0;//記錄逆序?qū)?br/>void?msort（int?lint?r）
{
if（l==r）?return;
int?mid=（l+r）/2;
msort（lmid）msort（mid+1r）;
int?i=lj=mid+1k=l;
while（i<=mid&&j<=r）
{
if（a[i]<=a[j]）
{
m[k]=a[i];
k++;
i++;
}
else?if（a[i]>a[j]）
{
m[k]=a[j];
k++;- 上一篇：x新安江模型c++
- 下一篇：Quicksum（C語(yǔ)言）
評(píng)論
共有 條評(píng)論
川公網(wǎng)安備 51152502000135號(hào)