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下运行结果如下:
*

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: