19、数据结构与算法C++：排序(2)-程序员快看-教程，程序员编程资料站

排序(2)

这一章中我们继续来介绍排序算法。

1.希尔排序

先来看下希尔排序代码如下：

#include<iostream>
#include<vector>
using namespace std;
void SellSort(vector<int>& vec);//希尔排序
int main()
{
    int n,e;
    vector<int> vec;
    cout << "输入数据元素个数：" << endl;
    cin >> n;
    cout << "输入数据元素：" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> e;
        vec.push_back(e);
    }
    SellSort(vec);
    cout << "从小到大排序结果:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
void SellSort(vector<int>& vec)//希尔排序
{
    int increment = vec.size();
    int e,j;
    do
    {
        increment = increment / 3 +1;
        for (int i = increment; i < vec.size(); i++)
        {
            if (vec[i] < vec[i - increment])
            {
                e = vec[i];
                for (j = i - increment; j >= 0 && vec[j] > e; j -= increment)
                {
                    vec[j + increment] = vec[j];
                }
                vec[j + increment] = e;

            }
        }
    } while (increment>1);

}

在VS下运行结果如下：

2.堆排序

要了解堆排序，就先要了解下堆。

堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆 ; 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如果按照层序遍历的方式给结点从1 开始编号，则结点之间满足如下关系:

{ki⩾k2iki⩾k2i+1或{ ki⩽k2iki⩽k2i+11⩽i⩽*n2* { k i ⩾ k 2 i k i ⩾ k 2 i + 1 或 { k i ⩽ k 2 i k i ⩽ k 2 i + 1 1 ⩽ i ⩽ * n 2 *

**堆排序(Heap Sort)**思想是将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值) 。然后将剩余的n−1 n − 1 个序列重新构造成一个堆，这样就会得到n n 个元素中的次小值。如此反复执行，便能得到一个有序序列了。相关代码如下：

#include<iostream>
#include<vector>
using namespace std;
void HeapSort(vector<int>& vec);//堆排序
void HeapAdjust(vector<int>& vec, int s, int m);//堆构建
int main()
{
    int n,e;
    vector<int> vec;
    cout << "输入数据元素个数：" << endl;
    cin >> n;
    cout << "输入数据元素：" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> e;
        vec.push_back(e);
    }
    HeapSort(vec);
    cout << "从小到大排序结果:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
void HeapSort(vector<int>& vec)//堆排序
{
    int n = vec.size();
    vec.insert(vec.begin(), 0);
    int i;
    for (i = n / 2; i > 0; i--)
        HeapAdjust(vec, i,n);
    for (i = n; i > 1; i--)
    {
        swap(vec[1],vec[i]);
        HeapAdjust(vec, 1, i-1);
    }
    vec.erase(vec.begin());
}
void HeapAdjust(vector<int>& vec,int s,int m)//堆构建
{
    int temp, j;
    for (j = 2 * s; j <= m; j *= 2)
    {
        if ((j < m)&&(vec[j]<vec[j + 1]))
            j++;
        if (vec[s] >= vec[j])
            break;
        swap(vec[s], vec[j]);
        s = j;
    }
}

在VS下运行结果如下：

3.归并排序

归并排序( Merging Sort) 就的原理是假设初始序列含有n n 个记录，则可以看成是n n 个有序的子序列，每个子序列的长度为1，然后两两归并，得到*n/2* *n/2*个长度为2或1的有序子序列;再两两归并，……，如此重复，直至得到一个长度为n n 的有序序列为止，这种排序方法称为2路归并排序。

递归方法实现

#include<iostream>
#include<vector>
using namespace std;
void MergeSort(vector<int>& vec);//递归方法实现归并排序
void MSort(vector<int>& SR, vector<int>& TR1, int s, int t);
void Merge(vector<int>&SR, vector<int>&TR, int i, int m, int n);
int main()
{
    int n,e;
    vector<int> vec;
    cout << "输入数据元素个数：" << endl;
    cin >> n;
    cout << "输入数据元素：" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> e;
        vec.push_back(e);
    }
    MergeSort(vec);
    cout << "从小到大排序结果:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
void MergeSort(vector<int>& vec)//递归方法实现归并排序
{
    MSort(vec, vec, 0, vec.size() - 1);
}
void MSort(vector<int>& SR, vector<int>& TR1, int s, int t)
{
    int m;
    vector<int> TR2;
    TR2.resize(SR.size());
    if (s == t)
        TR1[s] = SR[s];
    else
    {
        m = (s + t) / 2;
        MSort(SR, TR2, s, m);
        MSort(SR, TR2, m+1, t);
        Merge(TR2, TR1, s, m, t);

    }
}
void Merge(vector<int>&SR, vector<int>&TR, int i, int m, int n)
{
    int k, j, l;
    for (j = m + 1, k = i; i <= m&&j <= n; k++)
    {
        if (SR[i] < SR[j])
            TR[k] = SR[i++];
        else
            TR[k] = SR[j++];
    }
    if (i <= m)
    {
        for (l = 0; l <= m - i; l++)
            TR[k + l] = SR[i + l];
    }
    if (j <= n)
    {
        for (l = 0; l <= n - j; l++)
            TR[k + l] = SR[j + l];
    }
}

在VS下运行结果如下：

非递归实现

递归方法容易理解，但却牺牲空间和时间的性能。

#include<iostream>
#include<vector>
using namespace std;
void MergeSort2(vector<int>& vec);//递归方法实现归并排序
void MergePass(vector<int>& SR, vector<int>&TR, int s, int n);
void Merge(vector<int>&SR, vector<int>&TR, int i, int m, int n);
int main()
{
    int n,e;
    vector<int> vec;
    cout << "输入数据元素个数：" << endl;
    cin >> n;
    cout << "输入数据元素：" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> e;
        vec.push_back(e);
    }
    MergeSort2(vec);
    cout << "从小到大排序结果:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
void MergeSort2(vector<int>& vec)//递归方法实现归并排序
{
    vector<int> TR(vec.size());
    int k = 1;
    while (k < vec.size())
    {
        MergePass(vec, TR, k, vec.size()-1);
        k*=2 ;
        MergePass(TR, vec,k, vec.size()-1);
        k *= 2;
    }

}
void MergePass(vector<int>& SR, vector<int>&TR, int s, int n)
{
    int i = 0, j;
    while (i <= n - 2 * s+1)
    {
        Merge(SR, TR, i, i + s - 1, i + 2*s - 1);
        i = i + 2 * s;
    }
    if (i < n - s + 1)
        Merge(SR, TR, i, i + s - 1, n);
    else
        for (j = i; j <= n; j++)
            TR[j] = SR[j];
}

void Merge(vector<int>&SR, vector<int>&TR, int i, int m, int n)
{
    int k, j, l;
    for (j = m + 1, k = i; i <= m&&j <= n; k++)
    {
        if (SR[i] < SR[j])
            TR[k] = SR[i++];
        else
            TR[k] = SR[j++];
    }
    if (i <= m)
    {
        for (l = 0; l <= m - i; l++)
            TR[k + l] = SR[i + l];
    }
    if (j <= n)
    {
        for (l = 0; l <= n - j; l++)
            TR[k + l] = SR[j + l];
    }
}

在VS下运行结果如下：