❶ 一百萬個結構數組，根據其中一項值排序，用雙鏈表還是數組排序效率更好，請給出最快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);//迭代調用
}
}
}
這樣感覺效率還是不高！