關於設計演算法,把一個數組4等分,第一個數組的所有元素都小於第二個數組第二個數組所有的信息

本文目錄一覽：

• 1、排序演算法概述
• 2、給一個數組A，只能按數組順序組合，和必須低於限值limit，求組合數量最小情況下的所有組合情況，演算法思路
• 3、設計演算法並實現，將數組A[0……n-1]中的元素循環右移k位，要求只使用 一個元素大小的附加存儲空間。
• 4、設計一個演算法，將數組A[0….n]中的所有元素循環右移K位，要求只有一個數組元素大小的附加空間
• 5、求一個JS的演算法！！

排序演算法概述

十大排序演算法：冒泡排序，選擇排序，插入排序，歸併排序，堆排序，快速排序、希爾排序、計數排序，基數排序，桶排序

穩定 ：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；

不穩定 ：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；

排序演算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，前一個鍵排序的結果可以為後一個鍵排序所用。

演算法的複雜度往往取決於數據的規模大小和數據本身分布性質。

時間複雜度 ： 一個演算法執行所耗費的時間。

空間複雜度 ：對一個演算法在運行過程中臨時佔用存儲空間大小的量度。

常見複雜度由小到大 ：O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n)

在各種不同演算法中，若演算法中語句執行次數(佔用空間)為一個常數，則複雜度為O(1)；

當一個演算法的複雜度與以2為底的n的對數成正比時，可表示為O(log n)；

當一個演算法的複雜度與n成線性比例關係時，可表示為O (n)，依次類推。

冒泡、選擇、插入排序需要兩個for循環，每次只關注一個元素，平均時間複雜度為

（一遍找元素O(n)，一遍找位置O(n)）

快速、歸併、堆基於分治思想，log以2為底，平均時間複雜度往往和O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）相關

而希爾排序依賴於所取增量序列的性質，但是到目前為止還沒有一個最好的增量序列 。例如希爾增量序列時間複雜度為O(n²)，而Hibbard增量序列的希爾排序的時間複雜度為 ， 有人在大量的實驗後得出結論;當n在某個特定的範圍後希爾排序的最小時間複雜度大約為n^1.3。

從平均時間來看，快速排序是效率最高的：

快速排序中平均時間複雜度O(nlog n)，這個公式中隱含的常數因子很小，比歸併排序的O(nlog n)中的要小很多，所以大多數情況下，快速排序總是優於合併排序的。

而堆排序的平均時間複雜度也是O(nlog n)，但是堆排序存在著重建堆的過程，它把根節點移除後，把最後的葉子結點拿上來後需要重建堆，但是，拿上的值是要比它的兩個葉子結點要差很多的，一般要比較很多次，才能回到合適的位置。堆排序就會有很多的時間耗在堆調整上。

雖然快速排序的最壞情況為排序規模（n）的平方關係，但是這種最壞情況取決於每次選擇的基準， 對於這種情況，已經提出了很多優化的方法，比如三取樣劃分和Dual-Pivot快排。

同時，當排序規模較小時，劃分的平衡性容易被打破，而且頻繁的方法調用超過了O(nlog n)為

省出的時間，所以一般排序規模較小時，會改用插入排序或者其他排序演算法。

一種簡單的排序演算法。它反覆地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。這個工作重複地進行直到沒有元素再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為元素會經由交換慢慢「浮」到數列的頂端。

1.從數組頭開始，比較相鄰的元素。如果第一個比第二個大(小)，就交換它們兩個；

2.對每一對相鄰元素作同樣的工作，從開始第一對到尾部的最後一對，這樣在最後的元素應該會是最大(小)的數；

3.重複步驟1~2，重複次數等於數組的長度，直到排序完成。

首先，找到數組中最大（小）的那個元素；

其次，將它和數組的第一個元素交換位置（如果第一個元素就是最大（小）元素那麼它就和自己交換）；

再次，在剩下的元素中找到最大（小）的元素，將它與數組的第二個元素交換位置。如此往複，直到將整個數組排序。

這種方法叫做選擇排序，因為它在不斷地選擇剩餘元素之中的最大（小）者。

對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

為了給要插入的元素騰出空間，我們需要將插入位置之後的已排序元素在都向後移動一位。

插入排序所需的時間取決於輸入中元素的初始順序。例如，對一個很大且其中的元素已經有序（或接近有序）的數組進行排序將會比對隨機順序的數組或是逆序數組進行排序要快得多。

總的來說，插入排序對於部分有序的數組十分高效，也很適合小規模數組。

一種基於插入排序的快速的排序演算法。簡單插入排序對於大規模亂序數組很慢，因為元素只能一點一點地從數組的一端移動到另一端。例如，如果主鍵最小的元素正好在數組的盡頭，要將它挪到正確的位置就需要N-1 次移動。

希爾排序為了加快速度簡單地改進了插入排序，也稱為縮小增量排序，同時該演算法是突破O(n^2）的第一批演算法之一。

希爾排序是把待排序數組按一定數量的分組，對每組使用直接插入排序演算法排序；然後縮小數量繼續分組排序，隨著數量逐漸減少，每組包含的元素越來越多，當數量減至 1 時，整個數組恰被分成一組，排序便完成了。這個不斷縮小的數量，就構成了一個增量序列。

在先前較大的增量下每個子序列的規模都不大,用直接插入排序效率都較高，儘管在隨後的增量遞減分組中子序列越來越大,由於整個序列的有序性也越來越明顯,則排序效率依然較高。

從理論上說，只要一個數組是遞減的，並且最後一個值是1，都可以作為增量序列使用。有沒有一個步長序列,使得排序過程中所需的比較和移動次數相對較少,並且無論待排序列記錄數有多少,演算法的時間複雜度都能漸近最佳呢？但是目前從數學上來說，無法證明某個序列是「最好的」。

常用的增量序列

希爾增量序列 ：{N/2, (N / 2)/2, …, 1}，其中N為原始數組的長度，這是最常用的序列，但卻不是最好的

Hibbard序列：{2^k-1, …, 3,1}

Sedgewick序列：{… , 109 , 41 , 19 , 5，1} 表達式為

歸併排序是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法的一個非常典型的應用。

對於給定的一組數據，利用遞歸與分治技術將數據序列劃分成為越來越小的半子表，在對半子表排序後，再用遞歸方法將排好序的半子表合併成為越來越大的有序序列。

為了提升性能，有時我們在半子表的個數小於某個數（比如15）的情況下，對半子表的排序採用其他排序演算法，比如插入排序。

若將兩個有序表合併成一個有序表，稱為2-路歸併，與之對應的還有多路歸併。

快速排序（Quicksort）是對冒泡排序的一種改進，也是採用分治法的一個典型的應用。

首先任意選取一個數據（比如數組的第一個數）作為關鍵數據，我們稱為基準數(Pivot)，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序，也稱為分區（partition）操作。

通過一趟快速排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數組變成有序序列。

為了提升性能，有時我們在分割後獨立的兩部分的個數小於某個數（比如15）的情況下，會採用其他排序演算法，比如插入排序。

基準的選取：最優的情況是基準值剛好取在無序區數值的中位數，這樣能夠最大效率地讓兩邊排序，同時最大地減少遞歸劃分的次數，但是一般很難做到最優。基準的選取一般有三種方式，選取數組的第一個元素，選取數組的最後一個元素，以及選取第一個、最後一個以及中間的元素的中位數（如4 5 6 7, 第一個4, 最後一個7, 中間的為5, 這三個數的中位數為5, 所以選擇5作為基準）。

Dual-Pivot快排：雙基準快速排序演算法，其實就是用兩個基準數, 把整個數組分成三份來進行快速排序，在這種新的演算法下面，比經典快排從實驗來看節省了10%的時間。

許多應用程序都需要處理有序的元素，但不一定要求他們全部有序，或者不一定要一次就將他們排序，很多時候，我們每次只需要操作數據中的最大元素（最小元素），那麼有一種基於二叉堆的數據結構可以提供支持。

所謂二叉堆，是一個完全二叉樹的結構，同時滿足堆的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。在一個二叉堆中，根節點總是最大（或者最小）節點。

堆排序演算法就是抓住了這一特點，每次都取堆頂的元素，然後將剩餘的元素重新調整為最大（最小）堆，依次類推，最終得到排序的序列。

推論1：對於位置為K的結點 左子結點=2 k+1 右子結點=2 (k+1)

驗證：C:2 2 2+1=5 2 (2+1)=6

推論2：最後一個非葉節點的位置為 (N/2)-1，N為數組長度。

驗證：數組長度為6，(6/2)-1=2

計數排序對一定範圍內的整數排序時候的速度非常快，一般快於其他排序演算法。但計數排序局限性比較大，只限於對整數進行排序，而且待排序元素值分布較連續、跨度小的情況。

計數排序是一個排序時不比較元素大小的排序演算法。

如果一個數組裡所有元素都是整數，而且都在0-K以內。對於數組裡每個元素來說，如果能知道數組裡有多少項小於或等於該元素，就能準確地給出該元素在排序後的數組的位置。

桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，利用某種函數的映射關係將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序）。

桶排序利用函數的映射關係，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當於快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然後只需要對桶中的少量數據做排序即可。

常見的數據元素一般是由若干位組成的，比如字元串由若干字元組成，整數由若干位0~9數字組成。基數排序按照從右往左的順序，依次將每一位都當做一次關鍵字，然後按照該關鍵字對數組排序，同時每一輪排序都基於上輪排序後的結果；當我們將所有的位排序後，整個數組就達到有序狀態。基數排序不是基於比較的演算法。

基數是什麼意思？對於十進位整數，每一位都只可能是0~9中的某一個，總共10種可能。那10就是它的基，同理二進位數字的基為2；對於字元串，如果它使用的是8位的擴展ASCII字符集，那麼它的基就是256。

基數排序 vs 計數排序 vs 桶排序

基數排序有兩種方法：

MSD 從高位開始進行排序

LSD 從低位開始進行排序

這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：

基數排序：根據鍵值的每位數字來分配桶

計數排序：每個桶只存儲單一鍵值

桶排序：每個桶存儲一定範圍的數值

有時，待排序的文件很大，計算機內存不能容納整個文件，這時候對文件就不能使用內部排序了（我們一般的排序都是在內存中做的，所以稱之為內部排序，而外部排序是指待排序的內容不能在內存中一下子完成，它需要做內外存的內容交換），外部排序常採用的排序方法也是歸併排序，這種歸併方法由兩個不同的階段組成：

採用適當的內部排序方法對輸入文件的每個片段進行排序，將排好序的片段（成為歸併段）寫到外部存儲器中（通常由一個可用的磁碟作為臨時緩衝區），這樣臨時緩衝區中的每個歸併段的內容是有序的。

利用歸併演算法，歸併第一階段生成的歸併段，直到只剩下一個歸併段為止。

例如要對外存中4500個記錄進行歸併，而內存大小只能容納750個記錄，在第一階段，我們可以每次讀取750個記錄進行排序，這樣可以分六次讀取，進行排序，可以得到六個有序的歸併段

每個歸併段的大小是750個記錄，並將這些歸併段全部寫到臨時緩衝區（由一個可用的磁碟充當）內了，這是第一步的排序結果。

完成第二步該怎麼做呢？這時候歸併演算法就有用處了。

給一個數組A，只能按數組順序組合，和必須低於限值limit，求組合數量最小情況下的所有組合情況，演算法思路

不知道你是oracle還是sql server？這個是個自連接問題，先要排序，標行號，再同表的上下行相比，所以是自連接

orcale:

select a.vseq,a.declaredate as declaredate1,b.declaredate as declaredate2

from

(select vseq,declaredate,rownum as row from mac505 order by vseq,declaredate)a,

(select vseq,declaredate,rownum as row from mac505 order by vseq,declaredate)b

where a.vseq=b.vseq and a.row+1=b.row and a.declaredate+1000b.declaredate

sql server由於只有2005以上版本才有row_number()函數，所以如下腳本只能用在2005以上版本中

select a.vseq,a.declaredate as declaredate1,b.declaredate as declaredate2

from

(select vseq,declaredate,row_number() orver (order by vseq,declaredate) as row from mac505 )a,

(select vseq,declaredate,row_number() orver (order by vseq,declaredate) as row from mac505 )b

where a.vseq=b.vseq and a.row+1=b.row and a.declaredate+1000b.declaredate

設計演算法並實現，將數組A[0……n-1]中的元素循環右移k位，要求只使用 一個元素大小的附加存儲空間。

#includestdio.h

#define M 101

void change(int a[],int size,int k)

{

int i,j;

int t;

for(i=0;ik;i++)

{

t=a[size-1];

for(j=size-1;j0;j–)

{

a[j]=a[j-1];

}

a[0]=t;

}

}

void main()

{

int i,j,n;

int a[M],k;

scanf(“%d%d”,n,k);

for(i=0;in;i++)

{

scanf(“%d”,a[i]);

}

for(i=0;in;i++)

{

printf(“%d “,a[i]);

}

printf(“\n”);

change(a,n,k);

for(i=0;in;i++)

{

printf(“%d “,a[i]);

}

printf(“\n”);

}

main函數：輸入以後，進行調用函數前後的對比

change函數各參數按題目要求所示。。。

設計一個演算法，將數組A[0….n]中的所有元素循環右移K位，要求只有一個數組元素大小的附加空間

1．首先交換兩個變數的值，通常使用一個附加的中間變數進行過度．我通俗的舉例，就是有1杯牛奶和1杯咖啡，要交換這兩個杯子里的東西，就得有1個空杯子．

2．那麼數組元素的移動，無非也是變數值的交換，你是右移動K位，那麼假設用變數T過度．

設現在要將　i　移到　i＋K　的位置，（假設 i 和 i+k 在0–N之間）應該：

T = A(I+K)

A(I+K) = A(I)

A(I) = T

接下來，要考慮，當 i + K 大於n的處理,留給你自己解決吧!

求一個JS的演算法！！

這題建議你用java做

1:

先定義一個變數String holder=第一個的值，然後給第一個加「100」；

然後執行數組長度減一次循環，每次循環中用compare（）方法來比較大小，如果返回值大於等於0，就加（100+n-1）+「」，如果返回值小於0，就加（100+n）+「」，並更新holder的值；遍歷一次即可。

2：

定義變數count=0 ，boolean judge=false，然後挨個判斷，看是否有後面的小於前面的情況，並在每次循環中計算當前值和第一個值的差（可以使用BigInteger），如果大於等於10000或是count》=2，就令juge=true，並跳出循環，最後利用judge做判斷即可。