❶ 一百万个结构数组，根据其中一项值排序，用双链表还是数组排序效率更好，请给出最快C或C++算法代码。
采用数组排序，使用快速排序，例如说采用a 关键字排序的话:
void Swap(Type &NodeA,Type &NodeB)
{
Type Temp=NodeA;
NodeA=NodeB;
NodeB=Temp;
}
void Qsort(int LeftRange,int RightRange,Type Array[])
{
int LPoint,RPoint;
unsigned int Mid;
if (LeftRange==RightRange) return ;
Mid=Array[(LeftRange+RightRange)/2].a;
LPoint=LeftRange;RPoint=RightRange;
do
{
LPoint++;RPoint--;
while (Array[LPoint].a<Mid) LPoint++;
while (Array[RPoint].a>Mid) RPoint--;
if (LPoint<RPoint)
{
Swap(Array[LPoint],Array[RPoint]);
}
}while (LPoint<RPoint);
Qsort(LeftRange,RPoint);
Qsort(RPoint+1,RightRange);
}
从大到小排序：
采用数组排序，使用快速排序，例如说采用a 关键字排序的话:
void Swap(Type &NodeA,Type &NodeB)
{
Type Temp=NodeA;
NodeA=NodeB;
NodeB=Temp;
}
void Qsort(int LeftRange,int RightRange,Type Array[])
{
int LPoint,RPoint;
unsigned int Mid;
if (LeftRange==RightRange) return ;
Mid=Array[(LeftRange+RightRange)/2].a;
LPoint=LeftRange;RPoint=RightRange;
do
{
LPoint++;RPoint--;
while (Array[LPoint].a>Mid) LPoint++;
while (Array[RPoint].a<Mid) RPoint--;
if (LPoint<RPoint)
{
Swap(Array[LPoint],Array[RPoint]);
}
}while (LPoint<RPoint);
Qsort(LeftRange,RPoint);
Qsort(RPoint+1,RightRange);
}
插入排序的时间复杂度是O(N^2)的时间复杂度，而快速排序的平均复杂度为O(N*Log(N))，且快速排序的时间常数小，虽然其最坏理论时间复杂度为O(N^2)，但在实际运行中快速排序的速度较其他排序快很多，而且利用段长度小于3时用选择排序的话，验证速度提高10%~20%左右，但对于百万级的数据来说，普通的快速排序已然足够。
❷ 100w个数,用最快的方法,求从小到大排序后的前五个数（cc++程序）
我面试的时候有问到过，因为数据量很大，所以要同时考虑空间问题。标准答案是采用堆排序。
求从小到大排序后的前五个数，就是求最小的5个数。
具体做法是：
构建一个只有5个元素的max－heap，那么根结点就是这5个数中最大的数，然后开始遍历数组，如果遇到的数比max－heap的根结点还大，直接跳过，遇到比max－heap根结点小的数，就替代根结点，然后对这个max－heap进行维护（也就是排序，保证heap的特征）。那么遍历完数组后，这个max－heap的5个元素就是最小的5个数。
关于堆排序的代码应该不难找，或者我今天有空的时候写给你～
❸ 100万个随机数的数组，快速排序比插入排序快多少倍
忽略常数、误差的平均情况中，快速排序执行约10^7次，插入排序执行约10^12次，大约十万倍吧
❹ 如何从100万个数中找出最大的前100个数
三个方法：
1.根据快速排序划分的思想求解。
2.先取出前100个数，维护一个100个数的最小堆，遍历一遍剩余的元素，在此过程中维护堆就可以了。
3.分块查找。
❺ 对1000000万个数据排序，用什么方法快呢
初步的想法是可以通过树来进行排序,类似数据库建立索引的过程,然后遍历这个树就可以了.你可以参考一下B+树的算法.
❻ c语言，如何对大量数据（一百万条）排序
”数组的长度定义是有限的，1万还能运行通过，太大的话编译就不通过。“
如果不能完全读入数组，则就无法进行有效的排序了！
”且将1万条数据排序的效率也很低，要5秒多。。。“
一般排序用系统自带的qsort（）函数，快慢与机器性能有关。
❼ 对大量数据排序，多种排序方法中，哪种最快，效率最高
直接选择排序>快速排序>基数排序>归并排序 >堆排序>Shell排序>冒泡排序=冒泡排序2 =直接插入排序
❽ 对100万个排好序的数，查找某一个数，最快的方法是什么，效率是多少
算法如下：根据快速排序划分的思想
(1) 递归对所有数据分成[a,b）b（b,d]两个区间，(b,d]区间内的数都是大于[a,b)区间内的数
(2) 对(b,d]重复(1)操作，直到最右边的区间个数小于100个。注意[a,b)区间不用划分
(3) 返回上一个区间，并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分，分为[a2,b2）b2（b2,d2]两个区间，取（b2,d2]区间。如果个数不够，继续(3)操作，如果个数超过100的就重复1操作，直到最后右边只有100个数为止。
2.先取出前100个数，维护一个100个数的最小堆，遍历一遍剩余的元素，在此过程中维护堆就可以了。具体步骤如下：
step1：取前m个元素（例如m=100），建立一个小顶堆。保持一个小顶堆得性质的步骤，运行时间为O（lgm);建立一个小顶堆运行时间为m*O（lgm）=O(m lgm);
step2:顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素小，直接丢弃
如果大于堆顶元素，则用该元素替换堆顶元素，然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素，因此需要维护堆的代价为(N-m)*O(lgm);
最后这个堆中的元素就是前最大的10W个。时间复杂度为O(N lgm）。
3.分块查找
先把100w个数分成100份，每份1w个数。先分别找出每1w个数里面的最大的数，然后比较。找出100个最大的数中的最大的数和最小的数，取最大数的这组的第二大的数，与最小的数比较。。。。
❾ 排序算法：有100万数据，用卙用内存最小和排序最忋 void sort(int* array, int n) 其中你n的值为100万左右
int类型最大值为32767，故可以用32767的int数组存贮。
void sort( int *array , int n ){
int *array = new int[32767];
Zero_Memory( array , sizeof(int)*32767 );
for( long i = 0 ; i < n ; ++i ){
int data_i = read( i );//得到第i个数
++array[data_i];
}
}
那么array的下标就是数据，元组的值就是数据的个数，为0就是没有这个数据。
遍历一下这个数组就能得到排序好的序列，
内存 32767*sizeof(int)，时间是n
❿ 100万个32位整数，如何最快找到中位数.能保证每个数是唯一的，如何实现o算法
比如 1-9 这9个数字的中位数是 5
这些数的和是 45
temp = 5*0.618=3.09
比如现在的顺序是 189234675
然后 temp每次修正temp= temp * n/2(n-m) n是 数组 个数 m 是 小于 temp 的 个数
一遍下来 big = {8,9,4,6,7,5}
samll = {1,2,3}
现在 修正 temp = 3.09*9/6 =4.635
一遍下来 big = {8,9,6,7,5}
samll = {1,2,3,4}
temp = 4.635*9/8=5.214375
一遍下来 big = {8,9,6,7}
samll = {1,2,3,4,5}
temp = 5.214375 * 9/8
边界是 count(big) - count(samll) < =1
这样 最后 可以得到 中位数 但是 效率
不高
用的 原来就是 中位数 的 大于他的 和小于他的 个数 一样
对应算法是 search_zhong.php
<?php
$arr = array();//定义数组
for($i=0;$i<=1000;$i++){//假设有 1001个数字 现在随机生成
$arr[] = rand(0,10000);
}
$arr_s = $arr;
$time = time();//排序前开始计时
sort($arr);//对数组 排序
$zhongwei = $arr[501];//中位数
echo '中位数是：'.$zhongwei.'找到中位数用了'.time()-$time.'秒
';
$time2 = time();
echo '中位数是：(用马乙说的方法)'.mayiFunc($arr_s,0,0).'找到中位数用了'.time()-$time2.'秒
';
function mayiFunc($arr,$temp,$m){
$n = count($arr);
if($temp == 0){
$sum = array_sum($arr);
$agv = $sum/count($arr);
$temp = $agv*0.618;
}else{
$temp = $temp * $n/(2*($n-$m));
}
$big = array();
$small = array();
foreach($arr as $a){
if($a>$temp){
$big++;
}
else{
$small++;
}
}
if($big>$small){
if($big-$small<=1){
echo $temp;
exit;
return $temp;
}
else{
mayiFunc($arr,$temp,$small);//迭代调用
}
}else{
if($small-$big<=1){
echo $temp;
exit;
return $temp;
}
else{
mayiFunc($arr,$temp,$big);//迭代调用
}
}
}
这样感觉效率还是不高！