gogo专业大尺度亚洲高清人体,美女张开双腿让男生桶,亚洲av无码一区二区三区鸳鸯影院,久久久久国产精品人妻

算法基礎(chǔ)（一）

排序：

我們?yōu)楹我�研究排序�?br/>         1. 有時(shí)候應(yīng)用程序本身需要對(duì)信息進(jìn)行排序。
        2. 許多程序把排序程序作為關(guān)鍵子程序。
        3. 排序是我們學(xué)習(xí)編程的基本的訓(xùn)練，對(duì)于程序的優(yōu)化有很重要的作用。

我們之前已經(jīng)學(xué)過(guò)簡(jiǎn)單排序法和冒泡排序法。接下來(lái)我們介紹一下插入排序和合并排序。
        1. 插入排序
        輸入：n個(gè)數(shù)(a 1 ,a 2 ,.....a n)
        輸出：輸入序列的一個(gè)排序(b1,b2....bn),使得b1 <= b2 <=....<=bn

插入排序的機(jī)制和打牌時(shí)整理手中的牌做法差不多。摸牌的時(shí)候，需要將摸到的牌插入到手中一把牌中的正確的位置上。為了要找到這張牌的位置，我們需要將它與手中每張牌從右到左進(jìn)行比較。無(wú)論何時(shí)，左手中的牌都是排好序的。

這個(gè)算法中，所有的元素都是原地排序（sorted in place），就意味著這些數(shù)字就是在數(shù)組本身中重新排序的。

算法如下：
        1、數(shù)組被分為兩部分，一部分為排好序的，一部分為未排好序。
        2、選取一個(gè)key值，就是將要排序的元素，通過(guò)比較方式，將其插入到已排好順序的部分。
        3、循環(huán)處理，直到該數(shù)組全部排好序。

偽代碼：

代碼（c語(yǔ)言實(shí)現(xiàn)）：

//a 是一個(gè)數(shù)組，size_a是這個(gè)數(shù)組的元素個(gè)數(shù)
        void insertion_sort( int * a, int size_a){

                int i,j;
                int key = 0 ;

                for (j = 1 ;j < size_a;j ++ ){

                        key = a[j];
                        i = j - 1 ;
                        while (i > = 0 << a[i] > key){
                                a[i + 1 ] = a[i];
                                i = i - 1 ;
                        }
                        a[i + 1 ] = key;
                }

                return ;
        }

插入排序算法的時(shí)間復(fù)雜度是O(n 2 ) 。當(dāng)然算法的執(zhí)行速度，和n的大�。ㄝ斎胍�(guī)模）以及樣本的結(jié)構(gòu)有關(guān)系�？紤]壞的情況，就是輸入的n個(gè)數(shù)為逆序排列，此時(shí)插入排序算法，隨著n的增大，運(yùn)算時(shí)間的增長(zhǎng)與 n 2 同數(shù)量級(jí)。

2.分治法策略
        很多算法在結(jié)構(gòu)上是遞歸的：為了解決一個(gè)給定的問(wèn)題，算法要一次或多次地遞歸調(diào)用其自身來(lái)解決相關(guān)的子問(wèn)題。這些算法通常采用分治策略：將原問(wèn)題劃分為n個(gè)規(guī)模較小而結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題；遞歸地解決這些子問(wèn)題，然后再合并其結(jié)果，就得到原問(wèn)題的解。         分治模式在每一層遞歸上都有三個(gè)步驟：

分解（divide）：講原有問(wèn)題分解成為一系列子問(wèn)題；
        解決（Conquer）：遞歸地解各子問(wèn)題。若子問(wèn)題足夠小，則直接求解；
        合并（Combine）：講子問(wèn)題的結(jié)果合并成原問(wèn)題的解。

合并排序
        合并排序的關(guān)鍵步驟在于合并步驟中的合并兩個(gè)已排序子序列。為做合并，引入一個(gè)輔助過(guò)程merge(a,p,q,r)，其中a是一個(gè)數(shù)組，p，q和r是下標(biāo)，滿足p <＝ｑ< r。該過(guò)程的子數(shù)組 a[p...q]和a[q+1.... r] 都已排好序，并將他們合并成一個(gè)已排好的子數(shù)組代替當(dāng)前子數(shù)組a[p.....r]。

merge過(guò)程的代價(jià)是O(n)。其中n = r - p + 1是待合并的元素個(gè)數(shù)。
        以下為合并的偽代碼：

為了能檢查兩個(gè)子數(shù)組是否是空，其想法是在每一個(gè)數(shù)組底部放一個(gè)“哨兵”，它包含了特殊值，用于簡(jiǎn)化代碼。

具體來(lái)說(shuō)，merge過(guò)程是這樣工作的：第一行計(jì)算子數(shù)組a[p...q]的長(zhǎng)度n1,第二行計(jì)算子數(shù)組a[q+1...r]的長(zhǎng)度n2.在第三行中，創(chuàng)建了數(shù)組L和R，長(zhǎng)度各位n1 +1,n2 + 1.第四到第五行中的for循環(huán)將子數(shù)組a[p...q]復(fù)制到L[1....n1]中去。 第六到第七行中的for循環(huán)將子數(shù)組a[q+1...r]復(fù)制到R[1....n2]中去。第八九行講哨兵置于L和R的末尾。第十到第十七行，是合并的具體過(guò)程。通過(guò)比較，將兩子數(shù)組按照從小到大的方式合并，存入數(shù)組A中。

c語(yǔ)言描述如下所示

void merge( int * a, int p, int q, int r){

                int n1 = q - p + 1 ;
                int n2 = r - q;
                //為左數(shù)組和右數(shù)組分配空間，為max預(yù)留空間。
                //max為哨兵，標(biāo)志數(shù)組的結(jié)束。
                int * L = ( int * )malloc( sizeof ( int ) * (n1 + 1 ));
                int * R = ( int * )malloc( sizeof ( int ) * (n2 + 1 ));

                for ( int i = 0 ;i < n1;i ++ ){
                        L[i] = a[p + i];
           &nnbsp;    }

                for ( int i = 0 ;i < n2;i ++ ){
                        R[i] = a[q + i + 1 ];
                }

                L[n1] = MAX;
                R[n2] = MAX;
                //從小到大將左數(shù)組和友數(shù)組合并。
                int i,j,k;
                for (i = 0 ,j = 0 ,k = p;k < = r;k ++ ){
                        if (L[i] < = R[j]){
                                a[k] = L[i];
                                i ++ ;
                        } else {
                                a[k] = R[j];
                                j ++ ;
                        }
                }
                free(L);
                L = NULL;
                free(R);
                R = NULL;
                return ;
        }

合并merge過(guò)程就可以作為合并排序中的一個(gè)子程序來(lái)使用。偽代碼如下：

c語(yǔ)言描述過(guò)程為：

void merge_sort( int * a, int p, int r){
                int q = 0 ;

                if (p < r){
                         q= (p + r) / 2 ;
                        merge_sort(a,p,q);
                      &nbsnbsp; merge_sort(a,q + 1 ,r);
                        merge(a,p,q,r);
                }
                return ;
        }

合并程序的具體圖示：

關(guān)于分治法排序的簡(jiǎn)要分析：

我們將一個(gè)規(guī)模為n的問(wèn)題，拆分成n個(gè)規(guī)模為1的子問(wèn)題。拆分的過(guò)程經(jīng)歷了 lg n + 1層，在合并時(shí)，每一層的問(wèn)題規(guī)模為n，則總代價(jià)為O (n * lg n + n ) ，忽略低階項(xiàng)和常數(shù)項(xiàng)，因此合并排序法的時(shí)間復(fù)雜度為O(n lg n )。

接下來(lái)會(huì)介紹一下堆排序和快速排序。以上的所有排序方法，都是比較排序。也就是說(shuō)，他們通過(guò)對(duì)數(shù)組元素比較來(lái)實(shí)現(xiàn)排序。比較排序法是有極限的，從壞的輸入情況，比較排序法的時(shí)間復(fù)雜度是 O(n lg n )。我們介紹的合并排序以及快速排序，都是漸進(jìn)優(yōu)的比較排序方式。我們還會(huì)介紹可以突破比較排序極限的排序方式——計(jì)數(shù)排序。