婷婷色国产第一,毛片在线观看999,精品久久久久在线观看

計(jì)算機(jī)筆試經(jīng)典排序方法總結(jié)如下：

計(jì)算機(jī)經(jīng)典排序算法

按照上圖我們依次介紹不同排序算法及其具體代碼實(shí)現(xiàn)(升序)。

1.直接插入排序

實(shí)現(xiàn)原理：將一個(gè)數(shù)據(jù)插入到已排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的，個(gè)數(shù)加一的有序數(shù)據(jù)，在數(shù)據(jù)量較小時(shí)比冒泡排序和簡單選擇排序性能好一些。

插入排序

時(shí)間復(fù)雜度： $O(n^2)$

空間復(fù)雜度： $O(1)$

穩(wěn)定性：穩(wěn)定（相同大小的數(shù)據(jù)，在原無序記錄和排好序的記錄中前后順序不被交換）

c++代碼：

vector<int> InsertSort::sort(vector<int> ivec) {
    int j = 0;
    for (int i = 1; i < ivec.size(); i++) {
        if (ivec[i] < ivec[i - 1]) {
            j = i;
            while (j > 0 && ivec[j] < ivec[j - 1]) {
                swap(ivec[j], ivec[j - 1]);
                j --;
            }
        }
    }
    return ivec;
}

2.冒泡排序

實(shí)現(xiàn)原理：比較相鄰兩數(shù)的大小關(guān)系，在一趟冒泡排序過程中可以從原數(shù)據(jù)中選取最大或最小值，在循環(huán)過程中從剩余數(shù)據(jù)中依次選取最值。

冒泡排序

時(shí)間復(fù)雜度： $O(n^2)$
空間復(fù)雜度： $O(1)$
穩(wěn)定性：穩(wěn)定

算法

比較相鄰的元素，如果前大于后，交換；

對(duì)每一對(duì)相鄰元素進(jìn)行該操作，直到結(jié)尾則此時(shí)最后元素最大；

重復(fù)以上步驟，每次除去上一輪最后一個(gè)元素；

重復(fù)步驟1-3直到排序完成。

C++代碼：

vector<int> BubboSort::sort(vector<int> ivec) {
     for (int i = 0; i < ivec.size(); i ++) {
         for (int j = 1; j < ivec.size() - i; j++) {
             if (ivec[j - 1] > ivec[j]){
                 swap(ivec[j], ivec[j - 1]);
             }
         }
     }
     return ivec;
 }

3.快速排序

實(shí)現(xiàn)原理：通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。

快速排序

時(shí)間復(fù)雜度： $O(nlogn)$
空間復(fù)雜度： $O(logn)$

算法

從數(shù)據(jù)中挑出一個(gè)元素，稱為“基準(zhǔn)”（pivot）；

重新排序數(shù)列，所有元素比基準(zhǔn)值小放在基準(zhǔn)值前，大放在后，相同均可。則這次分區(qū)后該基準(zhǔn)處于數(shù)列中間位置，稱為“分區(qū)”（partition）操作；

遞歸地(recursive)把小于基準(zhǔn)值的元素的數(shù)列和大于基準(zhǔn)值的數(shù)列進(jìn)行排序。

C++代碼：

void quickSort(vector<int> &vec, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = vec[left], l = left, r = right;
    while (l < r) {
        while (l < r && vec[r] >= pivot) {
            r --;
        }
        while (l < r && vec[l] <= pivot) {
            l ++;
        }
        if (l < r) {
            swap(vec[l], vec[r]);
        }
    }
    swap(vec[left], vec[l]);
    quickSort(vec, left, l - 1);
    quickSort(vec, l + 1, right);
}

vector<int> QuickSort::sort(vector<int> ivec) {
    int left = 0;
    int right = ivec.size()-1;
    quickSort(ivec, left, right);
    return ivec;
}

4.選擇排序

實(shí)現(xiàn)原理：首先在未排序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)找最?。ù螅┰?，放到已排序列末尾。

選擇排序

時(shí)間復(fù)雜度： $O(n^2)$
空間復(fù)雜度： $O(1)$
穩(wěn)定性：不穩(wěn)定

算法

初始狀態(tài)：無序區(qū)為R[1,2,...,n]，無序區(qū)為空；

第i趟排序（i=1,2,...,n-1）開始前，當(dāng)前有序區(qū)和無序區(qū)分別為R[1,2,...,i-1]和R[i,i+1,...,n]。該趟從無序區(qū)中選出關(guān)鍵字最小的記錄R(k)，將他與無序區(qū)第1個(gè)記錄R(i)交換，使R[1,2,...,i]和R[i+1,...,n]分別變?yōu)閭€(gè)數(shù)增加1的新有序區(qū)和記錄個(gè)數(shù)減少1的新無序區(qū)；

n-1趟結(jié)束，數(shù)列變?yōu)橛行颉?/li>

C++代碼：

vector<int> InsertSort::sort(vector<int> ivec) {
    for (int i = 0; i < ivec.size(); i ++) {
        int minIndex = i;
        for (int j = i + 1; j < ivec.size(); j++) {
            if (ivec[j] < ivec[minIndex]) {
                minIndex = j;
            }
        }
        swap(ivec[i], ivec[minIndex]);
    }
    return ivec;
}

5.堆排序

實(shí)現(xiàn)原理：利用堆這種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一種算法，堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或大于）其父結(jié)點(diǎn)。

堆排序

堆的定義：n個(gè)元素的序列 $\{ k_1,k_2,...,k_n\}$ 當(dāng)且僅當(dāng)滿足以下條件時(shí)稱為堆。
小頂堆 $\left\{\begin{aligned} k_i \leq k_{2i} \\ k_i \leq k_{2i+1}\end{aligned}\right.(i = 1,2,...)$
大頂堆 $\left\{\begin{aligned} k_i \geq k_{2i} \\ k_i \geq k_{2i+1}\end{aligned}\right.(i = 1,2,...)$
時(shí)間復(fù)雜度： $O(nlogn)$
空間復(fù)雜度： $O(1)$
穩(wěn)定性：不穩(wěn)定

算法

將初始待排序關(guān)鍵字序列 $R[1,2,...,n]$ 構(gòu)成大頂堆，此堆為初始無序區(qū)

將堆頂元素 $R[1]$ 與最后一個(gè)元素 $R[n]$ 交換，此時(shí)得到新的無序區(qū) $R[1,2,...,n-1]$ 和新的有序區(qū) $R[n]$ ，且滿足 $R[1,2,...,n-1] \leq R[n]$ 。

交換后對(duì)當(dāng)前無序區(qū) $R[1,2,...,n-1]$ 調(diào)整為新堆，然后再次將 $R[1]$ 與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū) $R[1,2,...,n-2]$ 和新的有序區(qū) $R[n-1,n]$ ，不斷重復(fù)此過程直到有序區(qū)元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成

C++代碼

//遞歸方法進(jìn)行堆調(diào)整
void heapAjust(vector<int> &ivec, int p, int lenl) {
    //p待調(diào)整的節(jié)點(diǎn)下標(biāo)
    //len待調(diào)整的數(shù)組長度
    int parent = p;
    int leftchild = 2 * parent + 1;
    int rightchild = 2 * parent + 2;
    if (leftchild < lenl && ivec[leftchild] > ivec[parent]) {
        parent = leftchild;
    }
    if (rightchild < lenl && ivec[rightchild] > ivec[parent]) {
        parent = rightchild;
    }
    if (parent != p) {
        swap(ivec[parent], ivec[p]);
        heapAjust(ivec, parent, lenl);
    }
}
//非遞歸方法進(jìn)行堆調(diào)整
void heapAjust(vector<int> &ivec, int p, int len){
//每次判斷根節(jié)點(diǎn)和左右孩子節(jié)點(diǎn)的大小關(guān)系，比最大的孩子節(jié)點(diǎn)小則交換
        for(int i = 2*p +1; i < len; i = 2*i + 1){
              if(i + 1 < len && ivec[i] < ivec[i + 1]) i++;
              if(ivec[i] > ivec[p]){
                  swap(ivec[i], ivec[p]);
                  p = i;
              }
              else break;
        }
}
vector<int> HeapSort::sort(vector<int> ivec){
    int len = ivec.size();
    //初始化堆
    for (int i = len / 2; i >= 0; i--) {
        heapAjust(ivec, i, len);
    }
    //排序
    for (int t = len - 1; t >= 0; t--) {
        swap(ivec[0], ivec[t]);
        heapAjust(ivec, 0, t);
    }
    return ivec;
}

6.歸并排序

實(shí)現(xiàn)原理：歸并排序（MERGE-SORT）是利用完全二叉樹數(shù)據(jù)結(jié)構(gòu)與歸并的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略
時(shí)間復(fù)雜度： $O(nlogn)$
空間復(fù)雜度： $O(n)$
穩(wěn)定性：穩(wěn)定

歸并排序

//合并函數(shù)
void merge(vector<int> &ivec, vector<int> &tmp, int left, int mid, int right) {
    int k = 0, i = left, j = mid + 1;
    while (i <= mid && j <= right){
        if (ivec[i] <= ivec[j]) tmp[k++] = ivec[i++];
        if (ivec[i] > ivec[j]) tmp[k++] = ivec[j++];
    }
    while (i <= mid) tmp[k++] = ivec[i++];
    while (j <= right) tmp[k++] = ivec[j++];
    for (int n = 0; n < k; n++) ivec[left + n] = tmp[n];
}
vector<int> MergeSort::sort(vector<int> ivec) {
    vector<int> tmp = ivec;
    int left = 0;
    int right = ivec.size()-1;
    mergeSort(ivec, tmp, left, right);
    return ivec;
}

//非遞歸
//以間隔為1開始進(jìn)行歸并，也就是(1,2),(3,4)依次分別進(jìn)行歸并
//以間隔2開始進(jìn)行歸并，也就是(1,2,3,4),(5,6,7,8)依次進(jìn)行歸并
//再以間隔2*2開始進(jìn)行歸并，直到全部排完
 void  mergeSort(vector<int> &ivec, vector<int> &tmp){
        int i = 1, length = ivec.size();
        while(i < length){
            int l = 0;
            while(l < length){
                mid = l + i - 1;
                r = min(l+ 2*i -1, length-1);
                if mid < r and mid < length:
                    merge(ivec, tmp, l, mid, r);
                l += 2*i;
            }
            i *= 2;
      }
}

//遞歸結(jié)構(gòu)
void mergeSort(vector<int> &ivec, vector<int> &tmp, int left, int right) {
    if (left >= right) { return; }
    int mid = (left + right) / 2;
    mergeSort(ivec, tmp, left, mid);
    mergeSort(ivec, tmp, mid + 1, right);
    merge(ivec, tmp, left, mid, right);
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

計(jì)算機(jī)經(jīng)典排序算法——C++實(shí)現(xiàn)

計(jì)算機(jī)經(jīng)典排序算法——C++實(shí)現(xiàn)

1.直接插入排序

2.冒泡排序

3.快速排序

4.選擇排序

5.堆排序

6.歸并排序

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

計(jì)算機(jī)經(jīng)典排序算法——C++實(shí)現(xiàn)

1.直接插入排序

2.冒泡排序

3.快速排序

4.選擇排序

5.堆排序

6.歸并排序

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av