• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            bon

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(2)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            Recently, I began to peruse the CLRS (Introduction to Algorithms).

            Now I would like to scan all basic algorithms, especially sorting and searching.

            Let me first present a classic sorting algorithm - merge sort. Here is my code. Before I reach here, some mistakes are made, thus I note these "pitfalls" in the code

            #include <stdlib.h>
            #include <stdio.h>
            #define MAX 1e9    // the biggest possible value of a int number is 2^31 - 1 which is approximately 10^9
            #define SIZE 10

            int *a;
            int *b;
            int *c;

            // merge [p, q] and [q+1, r], where within each range number are sorted
            void merge(int p, int q, int r)
            {
                int k;
                int length = r - p +1;            // the length the range to be merge
                for (k = 0; k < q - p + 1; k++) {
                    b[k] = a[p + k];             // copy number in a[p, q] to b
                }
                b[k] = MAX;             // b[k] = MAX, not b[k+1]=MAX
                for (k = 0; k < r - q; k++) {
                    c[k] = a[q + 1 + k];             // copy number in a[q+1, r] to c
                }
                c[k] = MAX;             // c[k] = MAX, not c[k+1]=MAX

                /* BEGIN merging */
                int i = 0;
                int j = 0;
                for (k=0;k<length;k++) {             // do exactly length times of copy
                    if (b[i] < c[j]) {
                        a[p + k] = b[i++];          // be careful! a[p, r] is a whole range now, and watch out the base "p"
                    } else {
                        a[p + k] = c[j++];
                    }
                }
            }

            void merge_sort(int l, int u)
            {
                if (l == u) return;             // when to stop recursion? only one number needs no sorting
                int m = (l + u)/2;
                merge_sort(l, m);
                merge_sort(m + 1, u);
                merge(l, m, u);
            }

            int main()
            {
                a = (int*)malloc(SIZE * sizeof(int));
                b = (int*)malloc(SIZE * sizeof(int));          // cache, avoid many "malloc" in the merge function
                c = (int*)malloc(SIZE * sizeof(int));          // this trick is from "Programming Pearls"
                int i;
                for (i = 0; i < SIZE; i++) {
                    a[i] = SIZE - i;
                }
                merge_sort(0, SIZE - 1);                    // watch out the range
                for (i = 0; i < SIZE; i++) {
                    printf("%d\n", a[i]);
                }
                return 1;
            }

            posted on 2009-04-30 13:57 bon 閱讀(261) 評論(0)  編輯 收藏 引用
            Google PageRank 
Checker - Page Rank Calculator
            97久久精品人妻人人搡人人玩| 国产激情久久久久影院| 久久久青草青青国产亚洲免观| 91精品国产综合久久久久久| 亚洲中文久久精品无码ww16 | 亚洲av成人无码久久精品| 亚洲国产成人精品女人久久久 | 国产—久久香蕉国产线看观看| 国产成人无码久久久精品一| 精品综合久久久久久888蜜芽| 久久综合久久自在自线精品自| 色综合久久无码中文字幕| 久久久久成人精品无码中文字幕| 久久影院综合精品| 久久精品免费一区二区三区| 一本一道久久精品综合| 久久久久久噜噜精品免费直播| 欧美精品丝袜久久久中文字幕 | 久久综合九色综合久99| 久久精品日日躁夜夜躁欧美| 久久天堂AV综合合色蜜桃网| 狠狠色噜噜狠狠狠狠狠色综合久久| 久久99国产精品久久| 久久久人妻精品无码一区| 久久精品一本到99热免费| AV无码久久久久不卡蜜桃| 嫩草影院久久99| 久久国语露脸国产精品电影| 国产99精品久久| 久久亚洲精品无码aⅴ大香 | 99久久国产亚洲高清观看2024 | 77777亚洲午夜久久多人| 国产精品久久久久影院嫩草 | 国产精品久久成人影院| 久久久久久青草大香综合精品| 亚洲成色www久久网站夜月| 91超碰碰碰碰久久久久久综合| 亚洲伊人久久综合中文成人网 | 91精品国产91久久久久久| 国内精品久久久久久久久电影网| 伊人色综合久久天天|