一个无序数组取前5项大的值,不能排序应该怎么写
求告知!!!!!!!!!!!!!!! --------------------编程问答-------------------- google topN 问题一个简单的做法就是构造一个5个元素的有序列表,把数组的前5项放进去。
然后扫描数组的其余元素,发现当前元素比这个列表上最小的元素大,就把这个元素添加进去,去掉有序表上最小的那个元素。重复这个过程,最后就是5个最大的了。 --------------------编程问答-------------------- 你有没有在数据结构或者算法课程上学过“快速排序”算法呢?快速排序的前提是你要有一个“划分”方法,也就是以数组里的某个数为界,将数组划分为“不大于此数、不小于次数”的左右两部分。
求一个数组的第n大数,不需要为数组排序。调用这个“划分”方法就可以了。
我给你写个demo,随即产生1万个数,然后求出排在第3456大的数字。我随便搜索了一下“快速排序”,找到第一个文章:
http://www.cnblogs.com/huankfy/articles/1446588.html
那么我就抄它的partition方法好了。最终就是这样:
using System;--------------------编程问答-------------------- 我是随便搜了一个“快速排序”的文章,引用第一个文章。实际上这个文章中的 Sort 方法有点小毛病。可能更好的 Sort 方法是这样写的:
using System.Linq;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
var rnd = new Random();
var a = Enumerable.Range(0, 10000).Select(x => rnd.Next()).ToArray();
求第n大数(a, 3456);
Console.WriteLine("a[3456]= {0}", a[3456]);
Console.ReadKey();
}
private static void 求第n大数(int[] a, int index)
{
求第n大数(a, 0, a.Length - 1, index);
}
private static void 求第n大数(int[] a, int left, int right, int index)
{
begin:
var middle = Partition(a, left, right);
if (middle == index)
return;
if (index < middle )
right = middle - 1;
else
left = middle + 1;
goto begin;
}
private static int Partition(int[] a, int left, int right)
{
int tmp = a[left];
while (left < right)
{
while (left < right && a[right] >= tmp)
right--;
// 换位后不能将left+1,防止跳位
if (left < right)
a[left] = a[right];
while (left < right && a[left] <= tmp)
left++;
if (left < right)
{
a[right] = a[left];
// 有left < right,可将right向前推一位
right--;
}
}
a[left] = tmp;
return left;
}
}
}
if(i - left < right - i)
{
Sort(a, left, i - 1);
Sort(a, i + 1, right);
}
else
{
Sort(a, i + 1, right);
Sort(a, left, i - 1);
}
快速排序在递归时总是先执行规模最小的那一半(可能左边也可能右边),以避免滥用堆栈。
回到这个问题,判断第n大数,例如从1万个数里找到第3456大数跟找到第5大数所花的时间是几乎一样的,只需要调用partition方法11次左右,飞快地得到了。找到了第3456大数之后,数组中这个数以及其左边的那些数字,就是你要的数字。 --------------------编程问答-------------------- 嗯,呵呵,第3456大的数可能是
Console.WriteLine("a[3456]= {0}", a[3455]);
我或许把下标写错了哦! --------------------编程问答-------------------- --------------------编程问答-------------------- 唉,第3456大数可能是这个意思
求第n大数(a, 3455);
Console.WriteLine("a[3456]= {0}", a[3455]);
不过这不重要了哇。主要是算法使用问题。
补充:.NET技术 , C#