# 11226: 【原1226】qsort

### 题目描述

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

P322.8

## Sample Input

``````5
5 4 3 2 1
``````

## Sample Output

``````1 2 3 4 5
``````

## 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;
}
``````