sort.cpp

数据结构 数据结构 数据结构 数据结构 数据结构 数据结构

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