假设待排序数据是整型。编写C++程序，使用类和数组实现以下功能： (1)实现选择排序（直接选择排序）、插入排序（直接插入排序）和交换排序（快速排序、冒泡排序）、*归并排序等各种排序方法 (2)对于(1)实现的插入排序（直接插入排序）和交换排序（快速排序、冒泡排序），分别输出每一趟（遍）的结果和最终结果，并应用它对上面的数据序列进行排序。 (3) 输入或给定若干个已经有序或逆序的线性表，分别利用选择排序（直接选择排序）、插入排序（直接插入排序）和交换排序（快速排序、冒泡排序）、*归并排序等各种排序方法对他们进行排序，并输出他们各自的比较和移动记录次数。检验实际结果（运行时间和比较、移动记录次数）和理论结果的差异，并进行讨论各种方法的优劣。

下面是一个简单的代码实现，包括选择排序、插入排序、快速排序、冒泡排序和归并排序。

#include <iostream>
using namespace std;

class Sort {
public:
    virtual void sort(int arr[], int n) = 0;
    int getComparisonCount() const { return comparisonCount; }
    int getMoveCount() const { return moveCount; }
protected:
    int comparisonCount, moveCount;
    void swap(int& a, int& b) {
        int temp = a;
        a = b;
        b = temp;
        moveCount += 3;
    }
};

class SelectionSort : public Sort {
public:
    void sort(int arr[], int n) override {
        comparisonCount = moveCount = 0;
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                comparisonCount++;
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr[i], arr[minIndex]);
        }
    }
};

class InsertionSort : public Sort {
public:
    void sort(int arr[], int n) override {
        comparisonCount = moveCount = 0;
        for (int i = 1; i < n; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                comparisonCount++;
                arr[j + 1] = arr[j];
                moveCount++;
                j--;
            }
            arr[j + 1] = temp;
            moveCount++;
        }
    }
};

class QuickSort : public Sort {
public:
    void sort(int arr[], int n) override {
        comparisonCount = moveCount = 0;
        quickSort(arr, 0, n - 1);
    }
private:
    void quickSort(int arr[], int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
    int partition(int arr[], int left, int right) {
        int pivot = arr[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            comparisonCount++;
            if (arr[j] < pivot) {
                i++;
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i + 1], arr[right]);
        return i + 1;
    }
};

class BubbleSort : public Sort {
public:
    void sort(int arr[], int n) override {
        comparisonCount = moveCount = 0;
        for (int i = 0; i < n; i++) {
            bool swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                comparisonCount++;
                if (arr[j] > arr[j + 1]) {
                    swap(arr[j], arr[j + 1]);
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
    }
};

class MergeSort : public Sort {
public:
    void sort(int arr[], int n) override {
        comparisonCount = moveCount = 0;
        mergeSort(arr, 0, n - 1);
    }
private:
    void mergeSort(int arr[], int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    void merge(int arr[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int* L = new int[n1];
        int* R = new int[n2];
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
            moveCount++;
        }
        for (int i = 0; i < n2; i++) {
            R[i] = arr[mid + 1 + i];
            moveCount++;
        }
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            comparisonCount++;
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
                moveCount++;
            } else {
                arr[k++] = R[j++];
                moveCount++;
            }
        }
        while (i < n1) {
            arr[k++] = L[i++];
            moveCount++;
        }
        while (j < n2) {
            arr[k++] = R[j++];
            moveCount++;
        }
        delete[] L;
        delete[] R;
    }
};

int main() {
    int arr[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    // Selection sort
    SelectionSort ss;
    ss.sort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "Selection sort comparison count: " << ss.getComparisonCount() << endl;
    cout << "Selection sort move count: " << ss.getMoveCount() << endl;

    // Insertion sort
    InsertionSort is;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    is.sort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "Insertion sort comparison count: " << is.getComparisonCount() << endl;
    cout << "Insertion sort move count: " << is.getMoveCount() << endl;

    // Quick sort
    QuickSort qs;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    qs.sort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "Quick sort comparison count: " << qs.getComparisonCount() << endl;
    cout << "Quick sort move count: " << qs.getMoveCount() << endl;

    // Bubble sort
    BubbleSort bs;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    bs.sort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "Bubble sort comparison count: " << bs.getComparisonCount() << endl;
    cout << "Bubble sort move count: " << bs.getMoveCount() << endl;

    // Merge sort
    MergeSort ms;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    ms.sort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "Merge sort comparison count: " << ms.getComparisonCount() << endl;
    cout << "Merge sort move count: " << ms.getMoveCount() << endl;

    return 0;
}

其中，`Sort` 是一个抽象类，包含一个纯虚函数 `sort`，表示排序算法。子类 `SelectionSort`、`InsertionSort`、`QuickSort`、`BubbleSort` 和 `MergeSort` 分别实现了选择排序、插入排序、快速排序、冒泡排序和归并排序，重写了 `sort` 方法。

除此之外，`Sort` 还包含了计数器，用于记录比较次数和移动记录次数。

在 `main` 函数中，我们首先创建一个整型数组 `arr`，并定义其长度为 `n`。

然后我们依次使用不同的排序算法对 `arr` 进行排序，输出排序结果以及比较次数和移动记录次数。