#include<iostream>
using namespace std;

void print(int* arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void swap(int& a, int& b)
{
    int temp = 0;
    temp = a;
    a = b;
    b = temp;
}

void PopSort1(int* arr,int len)
{

    for (int i = 0; i < len - 1; i++)
    {
        bool sorted = 0;//判断循环是否进行元素的交换了
        for (int j = 0; j < len - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])//稳定的排序算法，相同值的数，不会进行交换
            {
                sorted = 1;
                swap(arr[j], arr[j + 1]);
            }
        }
        if (!sorted)//本次循环没进行交换，说明排序已经完成，剩下还没进行的循环就不用进行了。
        {
            break;
        }

    }
    print(arr, len);
}

void PopSort2(int* arr, int len)
{
    int end = len - 1;
    while (end)
    {
        for (int i = 0; i < end; i++)//<end,保证每次都能取到第i+1个
        {
            if (arr[i] > arr[i + 1])
            {
                swap(arr[i], arr[i + 1]);
            }
        }
        end--;
    }
    print(arr, len);
}

int main(void)
{
    int arr[] = { 1,4,5,266,5,1,78,9 };
    int len = sizeof(arr) / sizeof(arr[0]);
    PopSort1(arr, len);
    //PopSort2(arr, len);

    return 0;
}