C语言强化（五）输出一串数中最小的 k 个

有时候题目看似很简单，似乎非常容易实现，但是，你考虑过效率了吗？

通过这道题，你可以掌握

• 简单的插入排序
• 算法最优化的技巧

题目：输入 n 个整数，输出其中最小的 k 个。
例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，则最小的 4 个数字为 1，2，3 和 4。

看到此题，第一反应就是对这串数字进行排序，然后遍历角标0~3的数字打印出来，很简单嘛~~

怎么可以这么简单，仔细一看，题目只是要求最小的N个数字啊，这样子对整个数组进行排序有必要吗？

只需要4个最小的，也就意味着只要一个数比现有的4个最小数大，那么我们就可以将它永远永远遗忘掉，而不是还把他插入到数组中，把他插入到数组中，等一下有新的值插进来，还要和他多比较一次，无形中增加了比较次数！

思路

写一个函数sorting()，能插入值并对数组进行排序，注意原数组已经排好顺序
新建vector，遍历所给数组，
对于之前的4个元素，只是执行sorting函数
对于之后的元素，执行sorting函数，将最上面值pop出去

源代码

#include <stdio.h>
#include<stdlib.h>
#include <iostream>
#include<sstream>
#include <vector>

using namespace std;

/**
查找最小的 k 个元素（数组）
题目：输入 n 个整数，输出其中最小的 k 个。
例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，
则最小的 4 个数字为 1，2，3 和 4。

思路
写一个函数sorting()，能插入值并对数组进行排序，注意原数组已经排好顺序
新建vector，遍历所给数组，
	对于之前的4个元素，只是执行sorting函数
	对于之后的元素，执行sorting函数，将最上面值pop出去
*/

/**
sorting
vt：所给数组
value：要插入的值
从顶到底遍历vector
如果value比遍历到的结点值小，则交换位置
否则，因为原数组已经排好顺序，后面的数都比当前的数小，所以停止，跳出循环
*/
void sorting(vector<int> &vt,int value){
	vt.push_back(value);
	for(int i = vt.size()-2;i>=0;i--){
		if(value<vt[i]){
			if(i<vt.size()-1)
				vt[i+1]=vt[i];
			vt[i]=value;
		}else{
			break;
		}
	}
}
/**
findLastN
寻找最小N个数
*/
void findLastN(vector<int> oriVt,vector<int> &finalVt,int n){
	//把第一个数直接放进去
	finalVt.push_back(oriVt[0]);
	//从第二个数开始遍历
	for(int i =1;i<oriVt.size();i++){
		//对于之前的4个元素，只是执行sorting函数
		sorting(finalVt,oriVt[i]);
		if(i>n-1){
			//对于之后的元素，执行sorting函数，将最上面值pop出去
			finalVt.pop_back();
		}
	}
}
void main()
{
	vector<int> finalVt;
	vector<int> oriVt;
	//创建原数组
	oriVt.push_back(2);
	oriVt.push_back(-1);
	oriVt.push_back(4);
	oriVt.push_back(0);
	oriVt.push_back(1);
	oriVt.push_back(12);
	oriVt.push_back(3);
	//显示原数组
	cout<<"原数组："<<endl;
	for(int i = 0;i<oriVt.size();i++){
		cout<<oriVt[i]<<endl;
	}
	//找出最小n个
	int n = 4;
	findLastN(oriVt,finalVt,n);
	cout<<"最小N个数组："<<endl;
	for(int i = 0;i<finalVt.size();i++){
		cout<<finalVt[i]<<endl;
	}
	system("pause");
}

算法的优化，可以理解为一个词：吝啬

多一步浪费，多一分钱都不给！可以比较10次计算出来的，绝对不比较11次！

原文：http://blog.csdn.net/hzy38324/article/details/45242475