#include <iostream>

using namespace std;

void DataInput(int * p, int c);       // 輸入函數
void DataCopy(int * dest1, int * dest2, int * dest3, int * source, int c); // 復制函數
void DataShow(int * p, int c);    // 顯示函數
void BubbleSort(int * p, int c);                // 冒泡排序
void SelectSort(int * p, int c);                // 選擇排序
void QuickSort(int * p, int left, int right);   // 快速排序  

int B_loop = 0;         // 冒泡排序法循環次數
int B_exchange = 0;     // 冒泡排序法交換次數
int S_loop = 0;         // 選擇排序法循環次數
int S_exchange = 0;     // 選擇排序法交換次數
int Q_loop = 0;         // 快速排序法循環次數
int Q_exchange = 0;     // 快速排序法交換次數
int main()
{
    int n;
    while (1)
    {
        B_loop = 0;         
        B_exchange = 0;     
        S_loop = 0;         
        S_exchange = 0;     
        Q_loop = 0;         
        Q_exchange = 0;     
        cout << "請輸入要存儲數據的總個數：";
        cin >> n;
        while (cin.get() != '\n')
            continue;
        int * data = new int[n];
        DataInput(data, n);
        cout << "\n當前輸入數據如下：\n\n";
        DataShow(data, n);
        int * datacopy1 = new int[n];
        int * datacopy2 = new int[n];
        int * datacopy3 = new int[n];
        DataCopy(datacopy1, datacopy2, datacopy3, data, n);
        BubbleSort(datacopy1, n);
        cout << "\n冒泡法排序完成！循環" << B_loop << " 次，交換" << B_exchange << " 次.\n";
        SelectSort(datacopy2, n);
        cout << "\n選擇法排序完成！循環" << S_loop << " 次，交換" << S_exchange << " 次.\n";
        QuickSort(datacopy3, 0, n - 1);
        cout << "\n快速法排序完成！循環" << Q_loop << " 次，交換" << Q_exchange << " 次.\n";
        cout << "\n排序后，數據如下：\n\n";
        DataShow(datacopy3, n);
        cout << "\n輸入回車，繼續測試，輸入其它退出程序  ";
        if (cin.get() != '\n')
            break;
        cout << endl << endl;
    }
    cout << "\n程序結束，謝謝使用！^O^\n\n";
    return 0;

}

void DataInput(int * p, int c)
{
    cout << "\n逐個輸入數據：\n";
    for (int i = 0; i < c; ++i)
    {
        cout << "#" << i + 1 <<": ";
        cin >> p[i];
        while (cin.get() != '\n')
            continue;
    }
    cout << "\n數據輸入完畢!\n";
}

 

void DataCopy(int * dest1, int * dest2, int * dest3, int * source, int c)
{
    for (int i = 0; i < c; ++i)
    {
        dest1[i] = source[i];
        dest2[i] = source[i];
        dest3[i] = source[i];
    }
}


void DataShow(int * p, int c)
{
    for (int i = 0; i < c; ++i)
    {
        cout.width(6);
        cout << p[i];
        if (i!=0 && i % 10 == 0)
            cout << endl;
    }
    cout << endl;
}

void BubbleSort(int * p, int c)
{
    int temp;
    for (int i = 0; i < c; ++i)
    {
        for (int j = c - 1; j >=i; j--)
        {
            if (p[j] < p[j - 1])
            {
                temp = p[j - 1];    // 將較大放到后面
                p[j - 1] = p[j];
                p[j] = temp;
                B_exchange++;           // 交換次數加
            }
        }
        B_loop++;       // 循環次數加
    }
}
 

void SelectSort(int * p, int c)
{
    int temp;
    int pos;
    for (int i = 0; i < c - 1; ++i)
    {
        temp = p[i];
        pos = i;
        for (int j = i + 1; j < c; ++j)
        {
            if (p[j] < temp)
            {
                temp = p[j];
                pos = j;
                S_exchange++;
            }
        }
        p[pos] = p[i];
        p[i] = temp;
        S_loop++;
    }
}


void QuickSort(int * p, int left, int right)
{
    int temp;
    int i = left;
    int j = right;
    int middle = p[(left + right) / 2];
    do
    {
        while ((p[i] < middle) && (i < right))
            i++;
        while ((p[j] > middle) && (j > left))
            j--;
        if (i <= j)
        {
            temp = p[i];
            p[i] = p[j];
            p[j] = temp;
            i++;
            j--;
            Q_exchange++;
        }
        Q_loop++;
    }while (i <= j);
    if (left < j)
        QuickSort(p, left, j);
    if (right > i)
        QuickSort(p, i, right);
}