//  此版本为调整优化好的快速排序算法实现。
# include <iostream>
# include <vector>
using namespace std;
int Partition(vector<int> &arr, int low, int high)
{
    int pivot;                // 划分后基准记录的位置
    int pivotkey = arr[low]; // 用区间的第一个值作为基准，也可以采用其他方式,比如三数取中
    while (low < high)
    {
        while (low < high && arr[high] >= pivotkey) // 先从右向左扫描
            high--;
        if (low < high)      // 每次必须有判断，因为有可能在此时出现low>high的情况
            arr[low++] = arr[high];
        while (low < high && arr[low] <= pivotkey) // 再从左向右扫描
            low++;
        if(low < high)
            arr[high--] = arr[low];
    }
    pivot = low;           // 找出基准位置
    arr[pivot] = pivotkey; // 基准位置定位
    return pivot;
}
// 典型的分治法的思想
void quicksort(vector<int> &arr, int low, int high)
{
    if (low < high)  // 仅当区间长度大于 1 时才排序
    {
        int pivot = Partition(arr, low, high);  // 分解，找出基准
        quicksort(arr, low, pivot-1);           // 递归求解左子区间
        quicksort(arr, pivot + 1, high);        // 递归求解右子区间
    }
}
int main ()
{
    vector<int> arr;
    int temp;
    while (cin >> temp)
    {
        arr.push_back(temp); // 将数存入数组
    }
    quicksort(arr, 0, arr.size() - 1);
    for(auto i : arr)
        cout << i << endl;
    return 0;
}

// 优化的冒泡算法实现
# include <iostream>
# include <vector>
using namespace std;
void BubbleSort(vector<int> &arr)
{
    int i , j, temp,len;
    len =  arr.size();
    for (i = 0; i < len - 1; i++)  // 外层循环控制无序区的终点位置
    {
        bool flag = true;
        for (j = len - 1; j > i; j--) //内层控制每次比较的位置
        {
            if (arr[j] < arr[j - 1])
            {
                temp = arr[j];
                arr[j] = arr[j -1];
                arr[j - 1] = temp;
                flag = false;
            }
        }
        if (flag)
            break;
    }
}
int main()
{
    vector<int> arr;
    int temp;
    while (cin >> temp)
    {
        arr.push_back(temp); // 将数存入数组
    }
    BubbleSort(arr);
    cout <<"after sort: "<< endl;
    for(auto i : arr)
        cout << i << endl;
    return 0;
}