数据结构_bubble

问题描述

给定一个 1~N 的排列 P，即 1 到 N 中的每个数在 P 都只出现一次。现在要
对排列 P 进行冒泡排序，代码如下：
for (int i = 1; i <= N; ++i)
for (int j = N, t; j > i; ‐‐j)
if (P[j ‐ 1] > P[j])
t = P[j], P[j] = P[j ‐ 1], P[j ‐ 1] = t;
在排序过程中，数字的位置可能会发生变化。对于 1~ N 的每个数字，你需
要输出过程中达到的最左位置下标和最右位置下标的差的绝对值。

★数据输入
第一行为 N，表示排列长度。
第二行为排列 P。
数据保证:
80%的数据， N <= 1000
100%的数据， N <= 100000

★数据输出
输出一行，第 i 个数字表示数字 i 最左与最右位置的差的绝对值。

输入示例	输出示例
4 3 2 1 4	2 1 2 0

★注释
样例冒泡排序过程：
swap 2 1： 3 2 1 4 > 3 1 2 4
swap 3 1： 3 1 2 4 > 1 3 2 4
swap 3 2： 1 3 2 4 > 1 2 3 4

思路

　　定义结构体，成员有：data(数据值、排序后下标)、pos(排序前下标)、num(当前数右边比它小的数)

　　归并，过程中统计数右边比它小的数，更新num

　　最大下标为pos+num，最小下标为data或pos

　　PS:好像用树状数组做也可以，但是我不会╮(๑•́ ₃•̀๑)╭

code

 #include <stdio.h>

 #include <stdlib.h>

 struct Node

 {

     int data;

     int pos;

     int num;

 };

 Node *buf;

 inline int max(int a, int b)

 {

     return a>b?a:b;

 }

 inline int min(int a,int b)

 {

     return a<b?a:b;

 }

 void mergesort(Node *arr, int l,int r)

 {

     if(l>=r) return ;

     if(l+==r)

     {

         if(arr[l].data > arr[r].data)

         {

             Node tmp = arr[l];

             arr[l] = arr[r];

             arr[r] = tmp;

             arr[r].num++;

         }

     }

     int m = (l+r)/;

     int i,j,k;

     int num=;

     mergesort(arr,l,m);

     mergesort(arr,m+,r);

     for(i=l;i<=r;i++) buf[i] = arr[i];

     for(k=l,i=l,j=m+ ; k<=r; k++)

     {

         if(i>m)

         {

             arr[k] = buf[j++];

         }

         else if(j>r)

         {

             arr[k] = buf[i++];

             arr[k].num += num;

         }

         else if(buf[i].data < buf[j].data)

         {

             arr[k] = buf[i++];

             arr[k].num += num;

         }

         else

         {

             arr[k] = buf[j++];

             num++;

         }

     }

 }

 int main()

 {

     int i,j,k;

     int n;

     scanf("%d",&n);

     Node *arr = (Node *)malloc(sizeof(Node)*(n+));

     buf = (Node *)malloc(sizeof(Node)*(n+));

     for(i=;i<=n;i++)

     {

         scanf("%d",&arr[i].data);

         arr[i].pos = i;

         arr[i].num = ;

     }

     mergesort(arr,,n);

     for(i=;i<=n;i++)

     {

         if(i==)

             printf("%d",arr[i].num+arr[i].pos-min(arr[i].data,arr[i].pos));

         else

             printf(" %d",arr[i].num+arr[i].pos-min(arr[i].data,arr[i].pos));

     }

     printf("\n");

     free(arr);

     free(buf);

     return ;

 }

巴特西

数据结构_bubble_sort

最新文章

热门文章