数据结构_bubble

数据结构_bubble_sort

问题描述

给定一个 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

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 struct Node
 5 {
 6     int data;
 7     int pos;
 8     int num;
 9 };
10 
11 Node *buf;
12 
13 inline int max(int a, int b)
14 {
15     return a>b?a:b;
16 }
17 inline int min(int a,int b)
18 {
19     return a<b?a:b;
20 }
21 
22 void mergesort(Node *arr, int l,int r)
23 {
24     if(l>=r) return ;
25     if(l+1==r)
26     {
27         if(arr[l].data > arr[r].data)
28         {
29             Node tmp = arr[l];
30             arr[l] = arr[r];
31             arr[r] = tmp;
32             arr[r].num++;
33         }
34     }
35     
36     int m = (l+r)/2;
37     int i,j,k;
38     int num=0;
39     mergesort(arr,l,m);
40     mergesort(arr,m+1,r);
41     for(i=l;i<=r;i++) buf[i] = arr[i];
42     for(k=l,i=l,j=m+1 ; k<=r; k++)
43     {
44         if(i>m)
45         {
46             arr[k] = buf[j++];
47         }
48         else if(j>r)
49         {
50             arr[k] = buf[i++];
51             arr[k].num += num;
52         }
53         else if(buf[i].data < buf[j].data)
54         {
55             arr[k] = buf[i++];
56             arr[k].num += num;
57         }
58         else
59         {
60             arr[k] = buf[j++];
61             num++;
62         }
63     }
64 }
65 
66 int main()
67 {
68     int i,j,k;
69     int n;
70     scanf("%d",&n);
71     Node *arr = (Node *)malloc(sizeof(Node)*(n+1));
72     buf = (Node *)malloc(sizeof(Node)*(n+1));
73     for(i=1;i<=n;i++)
74     {
75         scanf("%d",&arr[i].data);
76         arr[i].pos = i;    
77         arr[i].num = 0;
78     }
79     mergesort(arr,1,n);
80     for(i=1;i<=n;i++)
81     {
82         if(i==1)
83             printf("%d",arr[i].num+arr[i].pos-min(arr[i].data,arr[i].pos));
84         else
85             printf(" %d",arr[i].num+arr[i].pos-min(arr[i].data,arr[i].pos));
86     }
87     printf("
");
88     
89     free(arr);
90     free(buf);
91     return 0;
92 }