排序
一、题目：（感谢 /v_JULY_v 提供的题目）
查找最小的k 个元素
输入n 个整数，输出其中最小的k 个。
例如输入1，2，3，4，5，6，7 和8 这8 个数字，则最小的4 个数字为1，2，3 和4。
二、分析：
看到题目的第一个想法，先把输入的n个整数排序，再输出最小的k个元素。
下面比较每种排序方案，选择最优方案解决这个问题！
三、排序：
排序算法中时间开销是衡量其好坏的重要标志！
基本操作：比较、移动
提高效率：尽可能少的比较次数和移动次数
1.插入排序：
（1）插入排序（insertion sort）
把元素分为待排序序列和已排序序列（初始时把第一位元素默认为已排序序列），依次将待排序序列的每一个元素插入到已排序序列中，直到全部元素都插入到已排序序列。
算法描述
从第一个元素开始，该元素可以认为已经被排序取出下一个元素，在已经排序的元素序列中从后向前扫描如果该元素（已排序）大于新元素，将该元素移到下一位置重复步骤3，直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作，称为二分查找排序。
（2）希尔排序（shell sort）
将所有元素分割成若干个子序列，在子序列中进行排序，重复以上操作，待所有元素基本有序时，进行一次插入排序。
过程实例
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：
13 14 94 33 8225 59 94 65 2345 27 73 25 3910
然后我们对每列进行排序：
10 14 73 25 2313 27 94 33 3925 59 94 65 8245
当我们以单行来读取数据时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 7325 23 1327 94 3339 25 5994 65 8245
排序之后变为：
10 14 1325 23 3327 25 5939 65 7345 94 8294
最后以1步长进行排序（此时就是简单的插入排序了）。
图解
2.交换排序：
（1）冒泡排序（bubble sort）
两两比较相邻的元素，大的往后移，小的往前移，直到排序完成。
算法描述
比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
图解
（2）快速排序（quick sort）
选一个轴值（基准），把比轴值小的值移到其左侧，把比轴值大的值移到其右侧，然后对左侧和右侧的元素重复上述的过程，直到整个序列有序。快速排序是一个递归的过程。
算法描述
从数列中挑出一个元素，称为 "基准"（pivot），重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
图解
3.选择排序：
（1）选择排序（selection sort）
首先在未排序序列中找到最小元素，存放到已排序序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列末尾。以此类推，直到所有元素均排序完毕。
图解
（2）堆排序（heap sort）
先把待排序序列构造成堆，选出堆中最大（小）的元素从堆中移走，再把剩余元素调整为堆，以此类推，直到堆中只剩一个元素。
（堆——具有以下特性的完全二叉树：每个结点的值都大（小）于或等于其左右孩子结点的值，大（小）根堆。
父节点i的左子节点在位置 (2*i);父节点i的右子节点在位置 (2*i+1);子节点i的父节点在位置 floor(i/2); ）
（完全二叉树——具有以下特点：
叶子结点只会出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子
）
图解
4.归并排序：
（1）归并排序（merge sort）
将若干个有序序列逐步归并，最终归并为一个有序序列。（归并——将两个或两个以上的有序序列合并为一个有序序列的过程。）
算法描述
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列设定两个指针，最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针达到序列尾将另一序列剩下的所有元素直接复制到合并序列尾图解
各种排序方法的比较：
针对本题我认为选择排序比较适合~
四、代码：
#include<iostream>using namespace std;const int n = 10;const int k = 4;void main(){int intArray[n] = {10,20,5,2,36,4,9,8,58,40};int index = 0;int min = 0;int temp = 0;for(int i=0;i<k;i++){index = i;min = intArray[i];for(int j=i+1;j<n;j++){if(intArray[j] < min){min = intArray[j];index = j;}}temp = intArray[i];intArray[i] = intArray[index];intArray[index] = temp;}for(int i=0;i<k;i++){cout<<intArray[i]<<" ";}}结果截图：
