18、数据结构与算法C++：排序(1)-程序员江小北

排序(1)

排序是我们经常需要面对的问题。我们先来看下排序的定义：

假设含有n n 个记录的序列为{ r1,r2,...,rn} { r 1 , r 2 , . . . , r n } ,其相应的关键字分别为{ k1,k2,...,kn} { k 1 , k 2 , . . . , k n } ,需确定1,2,...,n 1 , 2 , . . . , n 的一种排序p1,p2,...,pn p 1 , p 2 , . . . , p n ，使其相应的关键字满足kp1⩽kp2⩽......⩽kpn k p 1 ⩽ k p 2 ⩽ . . . . . . ⩽ k p n (非递减或非递增) 关系，即使得序列成为一个按关键字有序的序列{ rp1,rp2,...,rpn} { r p 1 , r p 2 , . . . , r p n } ,这样的操作就称为排序。

稳定性是排序一个重要的性能。其定义如下：

假设ki=kj(1⩽i⩽n,1⩽j⩽n,i≠j) k i = k j ( 1 ⩽ i ⩽ n , 1 ⩽ j ⩽ n , i ≠ j ) ,且在排序前的序列中ri r i 领先于rj r j (即i<j i < j )。如果排序后ri r i 仍然领先于rj r j ，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj r j 领先于ri r i ，则称所用的排序方法是不稳定的。

根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为:内排序和外排序。

1.冒泡排序

冒泡排序( Bubble Sort) 一种交换排序，它的基本思想是:两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

冒泡排序初级版

#include<iostream>
#include<vector>
using namespace std;
void BubbleSort0(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);
    }
    BubbleSort0(vec);
    cout << "从小到大排序结果:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
void BubbleSort0(vector<int>& vec)//冒泡排序初级版
{
    for (int i = 0; i < vec.size(); i++)
    {
        for (int j = i + 1; j < vec.size(); j++)
        {
            if (vec[i]>vec[j])
            {
                swap(vec[i],vec[j]);
            }
        }
    }
}

在VS上运行结果如下：

冒泡排序官方版

官方版是从末尾开始，相邻两个数据元素两两比较。代码如下：

#include<iostream>
#include<vector>
using namespace std;
void BubbleSort(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);
    }
    BubbleSort(vec);
    cout << "从小到大排序结果:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
void BubbleSort(vector<int>& vec)//冒泡排序官方版
{
    for (int i = 0; i < vec.size(); i++)
    {
        for (int j =vec.size()-2; j >= i; j--)
        {
            if (vec[j]>vec[j+1])
            {
                swap(vec[j], vec[j+1]);
            }
        }
    }
}

在VS上运行结果如下：

冒泡排序优化版

冒泡排序官方版和初级版性能和效率相当，优势在于跟利于优化。

#include<iostream>
#include<vector>
using namespace std;

void BubbleSort2(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);
    }
    BubbleSort2(vec);
    cout << "从小到大排序结果:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
void BubbleSort2(vector<int>& vec)//冒泡排序优化版
{

    bool flag = true;
    for (int i = 0; i < vec.size()&&flag; i++)
    {
        flag = false;
        for (int j = vec.size() - 2; j >= i; j--)
        {
            if (vec[j]>vec[j + 1])
            {
                swap(vec[j], vec[j + 1]);
                flag = true;
            }
        }
    }
}

在VS上运行结果如下：

2.简单选择排序

简单选择排序法( Simple Selection Sort) 就是通过n−i n − i 次关键字间的比较，从n−i+1 n − i + 1 个记录中选出关键字最小的记录，并和第i(1⩽i⩽n) i ( 1 ⩽ i ⩽ n ) 个记录交换之。

#include<iostream>
#include<vector>
using namespace std;
void SelectSort(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);
    }
    SelectSort(vec);
    cout << "从小到大排序结果:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
void SelectSort(vector<int>& vec)//简单选择排序
{
    int min;
    for (int i = 0; i < vec.size()-1; i++)
    {
        min = i;
        for (int j = i + 1; j < vec.size(); j++)
        {
            if (vec[min]>vec[j])
                min = j;
        }
        if (min != i)
            swap(vec[i], vec[min]);
    }
}

在VS上运行结果如下：

3.直接插入排序

直接插入排序(Straight Insertion Sort) 的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1 的有序表。

#include<iostream>
#include<vector>
using namespace std;
void InsertSort(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);
    }
    InsertSort(vec);
    cout << "从小到大排序结果:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
void InsertSort(vector<int>& vec)//直接插入排序
{
    for (int i = 1; i < vec.size(); i++)
    {
        int e,j;
        if (vec[i - 1] > vec[i])
        {
            e = vec[i];
            for (j = i - 1; j >= 0 && vec[j] > e; j--)
                vec[j + 1] = vec[j];
            if (j < 0)
                vec[0] = e;
            else
                vec[j + 1] = e;
        }
    }
}

在VS上运行结果如下：