学校网站意义/线在成都网站推广公司

1、简单选择排序

简单选择排序思想是：从头到尾（从后往前也行）遍历序列，先固定第一个位置的数据，将该位置后面的数据，依次和这个位置的数据进行比较，如果比固定位置的数据大，就交换。这样，进行一趟排序以后，第一个位置就是最小的数了。然后重复进行，第 2 次遍历并且比较后，第二个位置就是第二小的数字了，，依次类推

比较简单，直接上代码吧：

void selectsort(int a[], int n)
{for (int i = 0; i < n-1; i++){int min = i;  // 保留一份开始下标的副本for (int j = i + 1; j < n; j++)  // 从该值后面的数据开始遍历{if (a[j] < a[min])min = j;}if (i != min)swap(a[i],a[min]);  // 第 i 个位置就是这一轮最小的数字了}}

2、堆排序

堆排序的原理不赘述了，不太明白的同学可以参考链接：堆与堆排序

下面，说一下利用 STL 实现堆排序。

STL中与堆相关的4个函数——建立堆make_heap()，在堆中添加数据push_heap()，在堆中删除数据pop_heap()和堆排序sort_heap()：

头文件 #include <algorithm>

下面的_First与_Last为可以随机访问的迭代器（指针），_Comp为比较函数（仿函数），其规则——如果函数的第一个参数小于第二个参数应返回true，否则返回false。

（1）、建立堆
make_heap(_First, _Last, _Comp)

默认是建立最大堆的。对int类型，可以在第三个参数传入greater<int>()得到最小堆。

要先在容器中加入数据，再调用push_heap ()

排序之后就不再是一个合法的heap了

实例如下：

bool comp(int a,int b)   // 建立一个最小堆
{if (a > b)return true;return false;}int main()
{vector<int> v_heap;v_heap.push_back(3);v_heap.push_back(7);v_heap.push_back(31);v_heap.push_back(4);v_heap.push_back(12);v_heap.push_back(7);v_heap.push_back(24);v_heap.push_back(9);make_heap(v_heap.begin(), v_heap.end(),comp); // 这个 comp  是对应的，如果建立堆得时候有，排序的时候也要有 //v_heap.push_back(5);  // 应该先往容器中添加数据，然后再调用 push_heap() 往堆中加入数据//push_heap(v_heap.begin(),v_heap.end(),comp);pop_heap(v_heap.begin(),v_heap.end(),comp);// 需要先调用 pop_heap(),才能在容器中删除数据v_heap.pop_back();  // 删除最后一个数据for (auto v : v_heap)cout << v <<"   ";cout << endl;//sort_heap(v_heap.begin(),v_heap.end(),comp);// 如果建立的是最大堆，排序后的结果就是从小到大。最小堆排序后的结果是从大到小//for (auto v : v_heap)//	cout << v << "   ";//cout << endl;return 0;
}

这里说明一下几个问题：

（1）make_heap() 函数，建立堆得过程实际上也是一种排序的过程，只不过这种排序，不是严格意义上的从大到小排序

（2）sort_heap() 函数以后，排序得到的结果已经不再是一个堆了

（3）如果是对一个数组进行堆操作，pop_head() 函数，是将第一个元素放到最后一个，然后将剩下的元素重新建立堆。

堆排序有很多应用，有一题详见下一篇博客