冒泡排序深入理解

冒泡排序深入理解

對于冒泡排序有一個小性質: 每一次都會把序列未排好序的最大數"沉底", 即推到序列尾部

1.P4378 Out of Sorts S

留意著農場之外的長期職業生涯的可能性,奶牛Bessie開始在不同的在線編程網站上學習算法。

她到目前為止最喜歡的算法是“冒泡排序”。這是Bessie的對長度為N的數組A進行排序的奶牛碼實現。

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

顯然,奶牛碼中的“moo”指令的作用只是輸出“moo”。奇怪的是,Bessie看上去執著于在她的代碼中的不同位置使用這個語句。

給定一個輸入數組,請預測Bessie的代碼會輸出多少次“moo”。

題意即進行多少次冒泡排序

對于一個序列, 我們稱之為有序的, 當且僅當對于任意一個位置前面沒有比它大的數(可以模擬一下)

比如:6 1 2 3 4 5 進行一次為 1 2 3 4 5 6

那么對于位置i, 冒泡排序進行到i-1時, \(a_{i-1}\)為前i1個數中最大的一個, 如果它大于\(a_i\)那么它就會到\(a_i\)的后面

由此可推知, 每一次位置i前都會將一個比\(a_i\)大的數推至其后, 直至沒有比它大的

那么我們對每位置求一下它前面有幾個比它大就好啦(注意要將答案加一)

具體來說先進行離散化, 再樹狀數組求解即可

代碼:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100500;
int d[N], n;
int read(void) {
    int x = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)){
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x;
}
struct node{
    int val, pos;
    bool operator < (const node &i) const{
        if (val == i.val) return pos < i.pos;
        return val < i.val;
    }
}p[N];
inline int low(int x) {
    return x & -x;
}
int get(int x) {
    int tmp = 0;
    for (;x;x -= low(x)) tmp += d[x];
    return tmp;
}
void add(int x) {
    for (;x <= n; x += low(x)) d[x]++;
}
bool cmp(node i,node j) {
    return i.pos < j.pos;
}
int main() {
    n = read();
    for (int i = 1;i <= n; i++) p[i] = (node){read(),i};
    sort(p + 1,p + n + 1);
    for (int i = 1;i <= n; i++) p[i].val = i;
    sort(p + 1,p + n + 1, cmp);
    int ans = 0;
    for (int i = 1;i <= n; i++) {
        add(p[i].val);
        ans = max(ans, i - get(p[i].val));
    }
    printf ("%d\n", ans+1);
    return 0;
}

2.P4375 Out of Sorts G

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

給定一個輸入數組,請預測Bessie的代碼會輸出多少次“moo”。

題意:求雙向冒泡排序的排序次數

對于一個序列, 我們稱之為有序的, 當且僅當對于任意一個位置前面沒有比它大的數(可以模擬一下)

我們暫且稱它為平衡條件吧

首先將序列離散化

相比較于Out of Sorts S, 本題思路在于不動的位置, 結論為對于位置x, ans = max{ans, 前面有幾個數的數值大于x}

為什么呢

在x不滿足平衡條件的時候

首先第一波操作的時候,對于前x個位置一定會換出一個大于x的數

因為它不滿足平衡條件

第二波操作時, 又會有一個小于等于x的數插回來

因為回來的時候一定會冒泡出一個位置在x后的最小值, 因為x不滿足平衡條件, 所以最小值小于等于x, 就又插了回來

有人可能會問為什么Out of Sorts S不能用這個式子嘞, 因為每次換出的一定大于x, 但x+1位置上的數可能換過來, 而它有可能大于x

由此可知, 求每個位置前大于其的數就行啦

代碼:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100500;
int d[N], n;
int read(void) {
    int x = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)){
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x;
}
struct node{
    int val, pos;
    bool operator < (const node &i) const{
        if (val == i.val) return pos < i.pos;
        return val < i.val;
    }
}p[N];
inline int low(int x) {
    return x & -x;
}
int get(int x) {
    int tmp = 0;
    for (;x;x -= low(x)) tmp += d[x];
    return tmp;
}
void add(int x) {
    for (;x <= n; x += low(x)) d[x]++;
}
bool cmp(node i,node j) {
    return i.pos < j.pos;
}
int main() {
    n = read();
    for (int i = 1;i <= n; i++) p[i] = (node){read(),i};
    sort(p + 1,p + n + 1);
    for (int i = 1;i <= n; i++) p[i].val = i;
    sort(p + 1,p + n + 1, cmp);
    int ans = 1;
    for (int i = 1;i <= n; i++) {
        add(p[i].val);
        ans = max(ans, i - get(i));
    }
    printf ("%d\n", ans);
    return 0;
}
/*
6
2 5 6 3 1 4

*/

3.P4372 Out of Sorts P

留意著農場之外的長期職業生涯的可能性,奶牛Bessie開始在不同的在線編程網站上學習算法。她最喜歡的兩個算法是“冒泡排序”和“快速排序”,但是不幸的是Bessie輕易地把它們搞混了,最后實現了一個奇怪的混合算法! 如果數組A中A[...i]的最大值不大于A[i+1…]的最小值,我們就稱元素i和i+1之間的位置為一個“分隔點”。Bessie還記得快速排序包含對數組的重排,產生了一個分隔點,然后要遞歸對兩側的A[...i]和A[i+1…]排序。然而,盡管她正確地記下了數組中所有的分隔點都可以在線性時間內被求出,她卻忘記快速排序應該怎么重排來快速構造一個分隔點了!在這個可能會被證明是排序算法的歷史中最糟糕的算法性失誤之下,她做出了一個不幸的決定,使用冒泡排序來完成這個任務。

以下是Bessie最初的對數組AA進行排序的實現的概要。她首先寫了一個簡單的函數,執行冒泡排序的一輪:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

她的快速排序(相當快)函數的遞歸代碼是按下面的樣子構成的:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A) 
   divide A at all partition points; recursively quickish_sort each piece
}

Bessie好奇于她的代碼能夠運行得多快。簡單起見,她計算出她得主循環的每一輪都消耗線性時間,所以她相應增加一個全局變量work_counter的值,以此來跟蹤整個算法總共完成的工作量。

給定一個輸入數組,請預測quickish_sort函數接收這個數組之后,變量work_counter的最終值。

這道題用到了一個套路, 就是"橫向變縱向"

求每一次冒泡排序的長度, 不如求每一個點被冒泡排序了幾次

定義分割點為i與i+1的分割線,不妨假設它就在i上吧

再次定義序列排好序的標準

我們稱一個序列是有序的當且僅當所有點(除了n)都是分割點

那么接下來我們要求分割點的出現時間t數組

為什么求:

對于每個點它不用在進行冒泡排序了當且僅當兩邊都已成為分割點, 也就是兩邊出現時間的最大值

依據t數組,我們可以求出每個點被排了幾次

怎么求(敲重點):

首先離散化

對于一個點x來說, 所有小于它的數卻在它后面的, 每一次都會向前走一次

那么它出現的時間就是離它最遠的小于它的點冒泡到它前面的時間

即那個點到它的距離, 具體見代碼

所以單調隊列或指針都可以維護

代碼:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100500;
int d[N], n;
int read(void) {
    int x = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)){
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x;
}
struct node{
    int val, pos;
    bool operator < (const node &i) const{
        if (val == i.val) return pos < i.pos;
        return val < i.val;
    }
}p[N];
bool cmp(node i,node j) {
    return i.pos < j.pos;
}
int t[N], k;
int main() {
//  freopen("hs.in","r",stdin);
    n = read();
    for (int i = 1;i <= n; i++) p[i] = (node){read(),i};
    sort(p + 1,p + n + 1);
    for (int i = 1;i <= n; i++) p[i].val = i;
    sort(p + 1,p + n + 1, cmp);
    long long ans = 0;
    k = n;
    for (int i = n;i >= 1; i--) {
        while (p[k].val > i) k--;
        t[i] = max(p[k].pos - i, 1);
    }
    for (int i = 0;i < n; i++) ans += max(t[i], t[i+1]);
    printf ("%lld\n", ans);
    return 0;
}
/*
6
2 5 6 3 1 4

*/

4.T99343 奇怪的排序

您有一個正整數序列, 您可以選擇任意相鄰的兩個數\(a_i,a_{i+1}\)插入另兩個數之間,或序列首和尾;
假如序列為: 1 2 4 3 5 6
可以選2 4
插在序列首 2 3 4 3 5 6
插到3后 1 3 2 4 5 6
插到5后 4 3 5 1 2 6
插在6后 1 3 5 6 2 4
現在hs-black需要判斷是否進行若干次操作能使序列變得有序(無論正序倒序), 蒟蒻hs-black當然不會啦, 請您幫幫他.....

這道題來源于一位數競大佬提供的靈感

再次定義一個序列有序

我們稱一個序列是有序的,當且僅當它的逆序對數為0或n*(n-1)/2;

引理1: 交換序列中相鄰的兩個數會改變原序列逆序對個數的奇偶性

引理2: 將序列相鄰兩個數插入別處不會改變原序列逆序對個數的奇偶性

? 證明: \(a_1...a_ia_j...a_q...a_n\) 不斷將\(a_j\)與它右邊的數字交換直至正好換到\(a_q\)\(a_1...a_ja_i...a_n\) 此時共交換了q - j 次

? 再將\(a_i\)向右與相鄰數字交換q-1-i次到\(a_j\)左側 ,此時共交換2 * (q - j) 次,為偶數次,所以奇偶性不變

那么說明逆序對數與排序好的逆序對數奇偶性不同時不能滿足要求

下面證明相同時可以滿足要求

以正序為例, 每次將序列最小的數和后面的數插到已排序部分的后面, 如果最小數在最后時就將后2,3個數插在它后面

當未排序列只剩兩個數時, 逆序對個數也一定是偶數, 只可能是0

即序列有序, 證畢

具體實現是討論一下n*(n-1)/2的奇偶性, 并樹狀數組求出原序列逆序對個數

代碼:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
const int M = 500005;
using namespace std;
int n, sum[M];
struct Num{
    int val,num;
    inline friend bool operator < (Num a,Num b){
        return a.val > b.val;
    }
}p[M];
inline int lowbit(int x){
    return x&-x;
}
void add(int k,int x){
    while(k<=n){
        sum[k]+=x;
        k+=lowbit(k);
    }
}
int getsum(int k){
    int tmp=0;
    while(k>0){
        tmp+=sum[k];
        k-=lowbit(k);
    }
    return tmp;
}
long long Ans=0;
char ss[1<<17],*A=ss,*B=ss;
inline char gc()
{if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
    cin >> x ; 
}
int main(){
    int t;
    read(t);
    while(t--) {
        Ans = 0;
        memset(sum, 0, sizeof(sum));
        read(n);
        for(int i=1;i<=n;i++){
            read(p[i].val);
            p[i].num=i;
        }
        sort(p+1,p+n+1);
        for(int i=1;i<=n;i++){
            add(p[i].num,1);
            Ans+=getsum(p[i].num-1);
        }
//      printf ("%lld\n", Ans);
        if (n % 4 > 1) 
            printf("Yes\n");
        else if (Ans % 2 == 1) 
            printf("No\n");
        else 
            printf("Yes\n");
    }
    return 0;
}
posted @ 2019-10-05 23:11 Hs-black 閱讀(...) 評論(...) 編輯 收藏
福彩快三怎么样