Closer's Space

梦河之上, 一叶扁舟

快速排序


快排

算法思想

  • 分治

性能:

最差是$O(n^2)$, 平均是$O(nlogn)$且在数据达到一定规模时比堆排序和归并排序的性能更好

版本1

#include <bits/stdc++.h>
using namespace std;
int debug = 0;
#define Debug cout << "Debug: " << ++debug << endl;
int elem[110];
int N;

void read(){
        cin >> N;
        for(int i = 1; i <= N; ++i)
                cin >> elem[i];
}

void output(){
        for(int i = 1; i <= N; ++i)
                cout << elem[i] << ' ';
        cout << endl;
}

int partition(int a[], int l, int r){
        int tmp = a[r];
        while(l < r){
                while(l < r && a[l] <= tmp) ++l;
                if(l == r) break;
                a[r--] = a[l];
                while(r > l && a[r] >= tmp) --r;
                if(l == r) break;
                a[l++] = a[r];
        }
        a[l] = tmp;
        return l;
}

void quickSort(int a[], int l, int r){
        if(l >= r) return;
        int mid = partition(a, l, r);
        quickSort(a, l, mid - 1);
        quickSort(a, mid + 1, r);
        return;
}

int main(){
        freopen("in.txt", "r", stdin);
        read();
        quickSort(elem, 1, N);
        output();
        return 0;
}

版本2

#include <bits/stdc++.h>
using namespace std;
int debug = 0;
#define Debug cout << "Debug: " << ++debug << endl;
int elem[110];
int N;

void read(){
        cin >> N;
        for(int i = 1; i <= N; ++i)
                cin >> elem[i];
}

void output(){
        for(int i = 1; i <= N; ++i)
                cout << elem[i] << ' ';
        cout << endl;
}

int partition(int a[], int l, int r){
        int pos = l - 1;
        for(int i = l; i < r; ++i){
                if(a[i] <= a[r])
                        swap(a[++pos], a[i]);
        }
        swap(a[r], a[++pos]);
        return pos;
}

void quickSort(int a[], int l, int r){
        if(l >= r) return;
        int mid = partition(a, l, r);
        quickSort(a, l, mid - 1);
        quickSort(a, mid + 1, r);
        return;
}

int main(){
        freopen("in.txt", "r", stdin);
        read();
        quickSort(elem, 1, N);
        output();
        return 0;
}

博文最后更新时间:


评论

  • Keleagege
    kelLesect@emaill.host

    Online0yarmacy4save [url=http://cheapvia25mg.com]online pharmacy[/url] Buy Free Shipping Acticin Medication In Internet Overseas Plavix Copay Discount Card

  • Lestheori
    lestoow@cmail.host

    Comprar Propecia En Brasil where to buy cialis online safely Cialis Senza Ricetta Roma Order Propecia Online Male Pattern Baldness

发表评论

来访统计

访问量:204

评论总数:2