總結(jié)一下排序嘿;)

有插入排序和拓?fù)渑判颉?/p>

1.插入排序/直接插入排序

假設(shè)對(duì)較小的數(shù)組A[0...n-2]已經(jīng)排好序了，然后把A[n-1]找到一個(gè)合適的位置插進(jìn)去。一般來說是從右向左掃描這個(gè)有序的數(shù)組，直到遇到第一個(gè)小于A[n-1]的元素，然后把A[n-1]插在這個(gè)元素的后面，插入的這個(gè)位置往往不是最終的位置。

for ( int i = 1; i < a.length; i++) {

int v =a[i];

int j=i-1;

while(j>=0&& a[j]>v) {

a[j+1] = a[j];

j--;

}

a[j+1]=v;

}

最壞的情況是輸入一個(gè)嚴(yán)格遞減的數(shù)組,C(worst)=((n-1)*n)/2。在這種情況下和蠻力法中的冒泡排序的鍵值比較次數(shù)是完全相同的。最好的情況是按照升序排列的數(shù)組,C(best)=n-1。對(duì)該算法平均效率的分析主要基于對(duì)無序數(shù)組的研究，平均比較次數(shù)是降序數(shù)組的一半，C(avg)=(n^2)/4;

2.拓?fù)渑判?/p>

為了使拓?fù)渑判虺蔀榭赡?#xff0c;圖必須是一個(gè)無環(huán)有向圖。如果一個(gè)圖沒有回路，拓?fù)渑判蛴薪狻Ｓ袃煞N高效的算法，既可以驗(yàn)證一個(gè)有向圖是否是一個(gè)無環(huán)有向圖，又可以在是情況下，輸入拓?fù)渑判虻囊粋€(gè)頂點(diǎn)序列。

第一種：深度優(yōu)先查找的簡單應(yīng)用。

執(zhí)行一次DFS遍歷，并記住頂點(diǎn)變成死端(即退出遍歷棧)的順序。將該次序反過來就得到拓?fù)渑判騿栴}的一個(gè)解。

第二種：基于減治技術(shù)的直接實(shí)現(xiàn)。

在有向圖中求出一個(gè)源(一個(gè)沒有任何輸入邊的頂點(diǎn))，把它和所有從它出發(fā)的邊都刪除。如果有多個(gè)這樣的源，隨意選擇一個(gè)。源不存在，則無解。頂點(diǎn)被刪除的次序是拓?fù)渑判騿栴}的一個(gè)解。

源刪除算法獲得的解和基于DFS的算法求得的解不同，兩者都正確，所以，拓?fù)渑判騿栴}可能會(huì)有若干個(gè)不同的可選解。

總結(jié)

以上是生活随笔為你收集整理的java减治法深度优先查找_排序|减治法实现排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。