一、课程设计题目与要求

排序算法应用及对比
【基本要求】

• 1、生成三组1000万个数，分别为随机数、基本正序(所有元素在正序的基础上整体左移2位)、逆序（用什么数据结构？如果数据量达到1亿，10亿怎么办？）；
• 2、实现快速排序（改进版），归并排序和堆排序的递归和非递归版本；
• 3、要求从三组1000万数据中查找前d个最大的数（d是输入参数） ，请用快排，堆排序，归并排序以及插入/冒泡排序算法对所有数据排序后再查找最大的d个数，比较不同排序算法以及递归和非递归算法的区别(运行时间)；
• 4、不需要对1000万数据整体排序，从三组1000万数据中查找前d个最大和最小的数，用什么数据结构？

二、需求分析

对于不同数据序列，我们都有多种方法来排序，合适的算法可以节约大量时间和空间的开销，如何判断最高效的方法尤为重要。

程序通过对不同的随机和有序序列用快速排序（改进版），归并排序和堆排序的递归和非递归版本进行搜索。分析不同算法的运行时间，得到不同大小，不同顺序下最优的搜索方法。

对于题目中的不对1000万数据整体排序，从三组1000万数据中查找前d个最大和最小的数，**解决方法：**建一个大小为d的最小堆，先取出前d个数并构建小顶堆，然后遍历数据与小顶堆的堆顶相比，比堆顶小直接丢弃，比堆顶大则替换堆顶，并重新构建这个堆，遍历完所有1000万个数之后得到的最小堆里面便是最大的d个数。

三、设计

3.1 设计思想

（1）数据结构设计

三个动态数组ABC大小为用户输入的大小，分别用来存储随机数、基本正序(所有元素在正序的基础上整体左移2位)、逆序序列。
六个T_x (x = a->f) 复制ABC中的一个后用来给几种算法做排序。

（2）算法设计

程序涉及到的搜索函数如上图所示。

3.2 详细设计

快速排序（改进版）（交换排序的一种）
递归快排：
改进方案：改进选取枢轴的方法，即每次选取数据集中的中位数做枢轴，（选取中位数的可以在 O(n)时间内完成）。

//返回中位数位置
int GetMiddleValue(int A[], int low, int high)
{
    //  int mid = low + (high - low) >> 1;
    int mid = (high + low) / 2;

    int y1 = A[low] > A[mid] ? low : mid;
    int y2 = A[low] > A[high] ? low : high;
    int y3 = A[mid] > A[high] ? mid : high;

    if (y1 == y2) return y3;

    else return A[y1] > A[y2] ? y2 : y1;
}

快排的分割策略：第一步是通过将枢轴元与最后一个元素交换使得枢轴元离开要被分割的数据段；i 从第一个元素开始而 j 从倒数第二个元素开始。当 i 在 j 左边时，我们将 i 右移，移过那些小于枢轴元的元素，并将 j 左移，移过那些大于枢轴元的元素。当 i 和 j 停止时，i 指向的是大元素，j指向的是小元素。如果 i 在 j 左边，那么将这两个元素互换。 如果此时 i 和 j 已经交错即 i>j所以不交换。此时把枢轴元与 i 所指的元素交换。

基于栈的非递归快排：

void FD_QuickSort(int AA[], int low, int high)
{
    stack<int>x;
    stack<int>y;
    x.push(low);
    y.push(high);
    int Beg, End, k;

    while (x.size() != 0) {
        Beg = x.top();
        x.pop();
        End = y.top();
        y.pop();

        k = partition(AA, Beg, End);

        //      PrintA(AA, N);

        if (Beg < k - 1)
        {
            x.push(Beg);
            y.push(k - 1);
        }
        if (End > k + 1)
        {
            x.push(k + 1);
            y.push(End);
        }
    }
}

第一步、申请一个栈，存放排序数组的起始位置和终点位置。
第二步、将整个数组的起始位置s和终点位置e进栈
第三步、出栈数据，对出栈的数据进行排序，查找基准数据所在最终的位置 p。
第四步、判断起始位置s 是否小于基准位置p-1，如果小于则将起始位置和p-1为终点位置进栈
第五步、判断基准位置p+1 是否小于终点位置e，如果小于则将 p+1作为起始位置，e作为终点位置进栈
第六步、判断栈是否为空，如果不为空则重复第三步，否则退出操作。

归并排序：
基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid, n = last;
    int k = 0;

    while (i <= m && j <= n)
    {
        if (a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}

堆排序：（选择排序的一种）
存储：
一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。

堆化数组：
根据堆的性质, 只要保证部分有序即可, 即根节点大于左右节点的值. 将数组抽象为一个完全二叉树, 所以只要从最后一个非叶子节点向前遍历每一个节点即可. 如果当前节点比左右子树节点都大, 则已经是一个最大堆, 否则将当前节点与左右节点较大的一个交换, 并且交换过之后依然要递归的查看子节点是否满足堆的性质, 不满足再往下调整. 如此即可完成数组的堆化.
以下为非递归堆的调整代码

//  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
void FD_AdjustHeap(int a[], int ii, int n)
{
    int  temp = a[ii];
    int L = 2 * ii + 1;
    int R = 2 * ii + 2;

    while (L < n)
    {
        if (R < n && a[R] > a[L]) //在左右孩子中找最大的
            L++;

        if (a[L] <= temp)
            break;

        a[ii] = a[L];     //把较大的子结点往上移动,替换它的父结点
        ii = L;
        L = 2 * ii + 1;
    }
    a[ii] = temp;
}

排序（删除）：
为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。
//非递归堆排序

void FD_HeapSort(int a[], int n)
{
    FD_BuildHeap(a, n);
    for (int i = n - 1; i >= 0; i--)
    {
        Swap(a[i], a[0]);
        FD_BuildHeap(a, i);
    }
}

四、测试数据及测试结果：

长度10000，查找个数10

长度100000，查找个数10