排序模板

from 算法4

void m_s(int lo, int hi)
{
    if (lo >= hi) return;
    int mid = (lo + hi) >> 1;
    m_s(lo, mid), m_s(mid + 1, hi);
    for (int k = lo; k <= hi; k++)
            aux[k] = arr[k];
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++)
    {
        if (i > mid)
            arr[k] = aux[j++];
        else if (j > hi)
            arr[k] = aux[i++];
        else if (aux[j] < aux[i])
            arr[k] = aux[j++];
        else
            arr[k] = aux[i++];
    }
}

from yxc

void q_s(vector<int>& arr, int lo, int hi)
{
    if (lo >= hi) return;
    int i = lo - 1, j = hi + 1, x = arr[(lo + hi) >> 1];
    while(i < j)
    {
        do i++; while (arr[i] < x);
        do j--; while (arr[j] > x);

        if (i < j) std::swap(arr[i], arr[j]);
    }

    q_s(arr, lo, j), q_s(arr, j + 1, hi);
}

#include <algorithm>
#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;

vector<int> arr;
vector<int> aux;

bool isSorted(vector<int>& arr, int lo, int hi)
{
    for(int i = lo + 1; i <= hi; i++)
    {
        if(arr[i] < arr[i-1])  return false;
    }

    return true;
}

void m_s(int lo, int hi)
{
    if (lo >= hi) return;

    int mid = lo + hi >> 1;
    m_s(lo, mid), m_s(mid + 1, hi);


    if(isSorted(arr, lo, mid) == false || isSorted(arr, mid + 1, hi) == false)
    {
        cout << "IS SORTED ERROR\n";
    }
    
    for (int k = lo; k <= hi; k++)
        aux[k] = arr[k];

    int i = lo, j = mid + 1;

    for (int k = lo; k <= hi; k++)
    {
        if (j > hi) arr[k] = aux[i++];
        else if (i > mid) arr[k] = aux[j++];
        else if (aux[j] < aux[i]) arr[k] = aux[j++];
        else arr[k] = aux[i++];
    }

    if (isSorted(arr, lo, hi) == false)
    {
        cout << "IS SORTED ERROR\n";
    }
}

void q_s(vector<int>& arr, int lo, int hi)
{
    if (lo >= hi) return;

    int i = lo - 1, j = hi + 1, x = arr[lo + hi >> 1];

    while (i < j)
    {
        do i++;
        while (arr[i] < x);
        do j--;
        while (arr[j] > x);

        if (i < j) swap(arr[i], arr[j]);
    }

    q_s(arr, lo, j), q_s(arr, j + 1, hi);
}

int main()
{
    for (int j = 0; j < 2000; j++)
    {
        arr.clear();
        for (int i = 0; i < 400 + rand() % 3000; i++)
        {
            arr.push_back(rand() % 735);
        }

        aux.resize(arr.size());
        m_s(0, arr.size() - 1);

        vector<int> arr2 = arr;

        std::sort(arr2.begin(), arr2.end());
        for (int i = 0; i < arr.size(); i++)
        {
            if (arr2[i] != arr[i])
            {
                cout << "m_s  error  " << endl;
            }
        }

        if (j % 100 == 0)
            cout << j << "  ms  J" << endl;
    }

    for (int j = 0; j < 2000; j++)
    {
        arr.clear();
        for (int i = 0; i < 400 + rand() % 3000; i++)
        {
            arr.push_back(rand() % 735);
        }

        q_s(arr, 0, arr.size() - 1);

        vector<int> arr2 = arr;

        std::sort(arr2.begin(), arr2.end());

        for (int i = 0; i < arr.size(); i++)
        {
            if (arr2[i] != arr[i])
            {
                cout << "q_s  error  " << endl;
            }
        }

        if (j % 100 == 0)
            cout << j << "  qs  J" << endl;
    }
    cout << "  end " << endl;
    getchar();
    return 0;
}

from 正月点灯笼

void q_s2(vector<int>& arr, int lo, int hi)
{
    if (lo >= hi) return;

    int i = lo, j = lo;
    int x = arr[hi];

    for (int j = lo; j <= hi - 1; j++)
    {
        if (arr[j] < x)
        {
            swap(arr[i], arr[j]);
            i++;
        }
    }

    swap(arr[hi], arr[i]);

    q_s2(arr, lo, i-1), q_s2(arr, i+1, hi);
}