快速排序！！

快速排序的實(shí)現(xiàn)過程包括兩個(gè)主要部分：分割和遞歸。

創(chuàng)新互聯(lián)是專業(yè)的王屋網(wǎng)站建設(shè)公司，王屋接單;提供成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、成都外貿(mào)網(wǎng)站建設(shè)公司,網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行王屋網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

1. 首先選取一個(gè)基準(zhǔn)元素（通常是數(shù)組的第一個(gè)元素）。

2. 從數(shù)組的左端開始，掃描整個(gè)數(shù)組，如果當(dāng)前元素小于基準(zhǔn)元素，就交換它和基準(zhǔn)元素前面的元素，掃描結(jié)束后，基準(zhǔn)元素左邊的元素都比它小，右邊的元素都比它大。

3. 然后將基準(zhǔn)元素與數(shù)組的最后一個(gè)元素交換，這樣基準(zhǔn)元素就位于數(shù)組的中間位置，左邊的元素都比它小，右邊的元素都比它大。

4. 接下來，對(duì)基準(zhǔn)元素左右兩邊的子數(shù)組分別重復(fù)上述過程，直到左右子數(shù)組的元素個(gè)數(shù)小于等于1。

5. 整個(gè)排序過程通過遞歸來實(shí)現(xiàn)，遞歸的終止條件是左右子數(shù)組的元素個(gè)數(shù)小于等于1。

通過這樣的分治和遞歸過程，可以將原始數(shù)組排序?yàn)橛行驍?shù)組。

需要注意的是，在選擇基準(zhǔn)元素時(shí)需要注意避免最壞情況發(fā)生，例如每次都選擇大或最小的元素作為基準(zhǔn)元素。

快速排序的時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(logn) ~ O(n)

代碼模板

#includeusing namespace std;

void qsort(int a[], int l, int r) {
    int i = l, j = r, flag = a[(l + r) / 2];
    do {
        while (a[i]< flag) i++;
        while (a[j] >flag) j--;
        if (i<= j) swap(a[i], a[j]), i++, j--;
    } while (i<= j);

    if (i< r) qsort(a, i, r);
    if (j >l) qsort(a, l, j);
}

int main() {
    int n;
    cin >>n;
    int a[n];
    for (int i = 0; i< n; i++)
        scanf("%d", &a[i]);
    qsort(a, 0, n - 1);

    for (int i = 0; i< n; i++)
        cout<< a[i]<< ' ';

    return 0;
}
//注意模板中有很多小細(xì)節(jié)

sort函數(shù)

sort(a, a+n)  //表示從a[0]到a[n-1]升序排列
sort(a+1, a+n+1)  //表示從a[1]到a[n]升序排列
sort(a, a+n, cmp)  //cmp是自定義函數(shù)，返回的是排序規(guī)則，比如return x >y,表示前一個(gè)大于后一個(gè)，也就是降序排列

例題1：獎(jiǎng)學(xué)金（洛谷P1093） 優(yōu)化前

#includeusing namespace std;

const int N = 305;
int student[N][4], number[N], sum[N];

bool cmp(int x, int y) {
    return ((sum[x] >sum [y]) || (sum[x] == sum[y] && student[x][1] >student[y][1]) ||
            (sum[x] == sum[y] && student[x][1] == student[y][1] && x< y));
}

int main() {
    int n;
    cin >>n;
    for (int i = 1; i<= n; i++) {
        number[i] = i;
        cin >>student[i][1] >>student[i][2] >>student[i][3];
        sum[i] = student[i][1] + student[i][2] + student[i][3];
    }
    sort(number + 1, number + 1 + n, cmp);
    for (int i = 1; i<= 5; i++) {
        cout<< number[i]<< ' '<< sum[number[i]]<< endl;
    }
    return 0;
}

優(yōu)化后

#include#include 

using namespace std;

const int N = 305;
int chinese[N], id[N], sum[N];  //改成一維數(shù)組，只記錄語文成績

bool cmp(int x, int y) {
    return
    sum[x] >sum [y] ||
    sum[x] == sum[y] && chinese[x] >chinese[y] ||
    sum[x] == sum[y] && chinese[x] == chinese[y] && x< y;
}

int main() {
    int n;
    cin >>n;
    for (int i = 1; i<= n; i++) {
        int math, english;  //英語和數(shù)學(xué)成績不重要，不用記錄
        id[i] = i;
        cin >>chinese[i] >>math >>english;
        sum[i] = chinese[i] + math + english;
    }

    sort(id + 1, id + 1 + n, cmp);
? ? 
? ? //比如原來id[1]=1,id[2]=2...
? ? //現(xiàn)在 id[1]=5,id[2]=6...
? ? //成績最好的成績記為編號(hào)1，他的學(xué)號(hào)是id[1],成績是sum[id[i]]

    for (int i = 1; i<= 5; i++) {
        cout<< id[i]<< ' '<< sum[id[i]]<< endl;
    }

    return 0;
}

兩種不常用算法 冒泡排序

冒泡排序是一種簡單的排序算法，它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。

冒泡排序的實(shí)現(xiàn)過程如下：

1. 首先，將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，如果第一個(gè)元素大于第二個(gè)元素，就交換這兩個(gè)元素的位置。

2. 接著，將第二個(gè)元素與第三個(gè)元素進(jìn)行比較，如果第二個(gè)元素大于第三個(gè)元素，就交換這兩個(gè)元素的位置。

3. 按照上面的方式，重復(fù)地將相鄰的元素進(jìn)行比較和交換，直到比較到數(shù)組的最后一個(gè)元素。

4. 此時(shí)，數(shù)組的最后一個(gè)元素就是大的元素。

5. 重復(fù)上面的過程，但是不再比較最后一個(gè)元素，因?yàn)樗呀?jīng)是大的元素了。

6. 接著，重復(fù)上面的過程，但是不再比較倒數(shù)第二個(gè)元素，因?yàn)樗呀?jīng)是第二大的元素了。

7. 以此類推，直到整個(gè)數(shù)組都有序。

冒泡排序的時(shí)間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(1)

代碼模板

#includeusing namespace std;

const int N = 100;

int main() {
    int a[N];
    int n;
    cin >>n;
    for (int i = 0; i< n; i++)
        cin >>a[i];
        
    for(int i = 0; i< n-1; i++) 
        for(int j = 0; j< n-i-1; j++){
            if(a[j] >a[j+1]) swap(a[j], a[j+1]);
        }
        
    for (int i = 0; i< n; i++)
        cout<< a[i]<< ' ';
        
    return 0;
}

計(jì)數(shù)排序

計(jì)數(shù)排序是一種非比較型排序算法，它適用于數(shù)據(jù)范圍較小的情況。

它的基本思想是，對(duì)于待排序的數(shù)組中的每一個(gè)元素，確定其在整個(gè)數(shù)組中出現(xiàn)的次數(shù)，然后根據(jù)這個(gè)次數(shù)將元素放到最終結(jié)果的對(duì)應(yīng)位置上。

具體實(shí)現(xiàn)過程如下：

1. 創(chuàng)建一個(gè)計(jì)數(shù)數(shù)組 counts，用來存儲(chǔ)每個(gè)元素在數(shù)組中出現(xiàn)的次數(shù)。

2. 遍歷待排序的數(shù)組，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，存入 counts 數(shù)組中。

3. 遍歷 counts 數(shù)組，將 counts[i] 個(gè)元素 i 放入結(jié)果數(shù)組的對(duì)應(yīng)位置。

4. 返回結(jié)果數(shù)組。

由于計(jì)數(shù)排序是一種線性排序算法，因此時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(k)，其中 n 為數(shù)組大小，k 為數(shù)據(jù)范圍。

由于計(jì)數(shù)排序不需要進(jìn)行元素之間的比較，因此它是一種穩(wěn)定排序算法。但是，由于它的空間復(fù)雜度隨著數(shù)據(jù)范圍的增大而增大，所以它在數(shù)據(jù)范圍較大的情況下不太適用。

計(jì)數(shù)排序需要預(yù)先知道數(shù)據(jù)的范圍

代碼模板

#includeusing namespace std;

const int MAX = 100;  //數(shù)組元素的大值 
const int N = 100;
int arr[N], counts[MAX];

int main() {
    int n;  //數(shù)組的長度
    cin >>n;
    for (int i = 0; i< n; i++) {
        cin >>arr[i];
        counts[arr[i]]++;
    }

    int j = 0;
    for (int i = 0; i< MAX; i++) { //遍歷0到大值，根據(jù)之前統(tǒng)計(jì)的每個(gè)數(shù)字的個(gè)數(shù)，來給數(shù)組重新賦值
        while (counts[i]--) {
            arr[j++] = i;
        }
    }

    for (int i = 0; i< n; i++) {
        cout<< arr[i]<< " ";
    }

    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：快速排序及自定義函數(shù)-創(chuàng)新互聯(lián)
文章路徑：http://www.yijiale78.com/article32/hhdpc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、定制網(wǎng)站、虛擬主機(jī)、網(wǎng)站內(nèi)鏈、服務(wù)器托管、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)