Skip to content

11226: 【原1226】qsort

题目

题目描述

author: DS TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1226

Description

P322.8

Input Format

第一行输入一个数 N

第二行输入 N 个数构成待排序数组A

Output Format

输出排序好的N个元素,用空格隔开

Sample Input

5
5 4 3 2 1

Sample Output

1 2 3 4 5

Tips

按要求利用快速排序解决问题!

BugenZhao's solution

//
// Created by BugenZhao on 2019/5/12.
//

#ifndef SBL_BQSORT_H
#define SBL_BQSORT_H

template<typename Item>
class BQSort {
private:
    static bool less(Item v, Item w) {
        return v < w;
    }

    static void exch(Item *a, int i, int j) {
        Item t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

public:
    static void sort(Item *a, int n) {
        sort(a, 0, n - 1);
    }

    static void sort(Item *a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = partition(a, lo, hi);
        sort(a, lo, mid - 1);
        sort(a, mid + 1, hi);
    }

    static int partition(Item *a, int lo, int hi) {
        int i = lo, j = hi + 1;
        Item v = a[lo];
        while (true) {
            while (less(a[++i], v))
                if (i == hi) break;
            while (less(v, a[--j]))
                if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
};

#endif //SBL_BQSORT_H

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    auto a = new int[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    BQSort<int>::sort(a, n);
    for (int i = 0; i < n; ++i) {
        cout << a[i] << ' ';
    }
    cout << endl;
    delete[] a;
    return 0;
}

yyong119's solution

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[100000];
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n - 1; ++i) cout << a[i] << " ";
    cout << a[n - 1];
    return 0;
}

Zsi-r's solution

#include <iostream>

using namespace std;

int divide(int array[],int low,int high)
{
    int temp = array[low];
    do{
        while(low<high&&array[high]>=temp)high--;
        if (low<high) array[low++] = array[high];
        while(low<high&&array[low]<=temp)low++;
        if(low<high) array[high--]=array[low];
    }while(low!=high);
    array[low] = temp;
    return low;
}

void quicksort(int array[],int low,int high)
{
    int mid;
    if (low>=high) return ; 
    mid = divide(array,low,high);
    quicksort(array,low,mid-1);
    quicksort(array,mid+1,high);
}

void quicksort(int array[],int size)
{
    quicksort(array,0,size-1);
}

int main()
{
    int num,i;
    cin>> num;
    int *array = new int [num];
    for (i=0;i<num;i++)
    {
        cin >> array[i];
    }
    quicksort(array,num);
    for (i=0;i<num;i++)
    {   
        cout <<array[i] << ' ';
    }
    return 0;
}