Java的集中基本常用算法

1、1. 常用算法1.1. 冒泡排序算法冒泡排序是排序算法的一種，思路清晰，代碼簡潔，常被用在大學(xué)生計(jì)算機(jī)課程中。“冒泡”這個(gè)名字的由來是因?yàn)樵酱蟮脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。這里以從小到大排序?yàn)槔M(jìn)行講解1.1.1. 基本思想及舉例說明冒泡排序的基本思想就是不斷比較相鄰的兩個(gè)數(shù)，讓較大的元素不斷地往后移。經(jīng)過一輪比較，就選出最大的數(shù)；經(jīng)過第2輪比較，就選出次大的數(shù)，以此類推。下面以對 3 2 4 1 進(jìn)行冒泡排序說明。第一輪排序過程3 2 4 1 （最初）2 3 4 2 （比較3和2，交換）2 3 4 1 （比較3和4，不交換）2 3 1 4 （比較4和1，交換）第一輪結(jié)束，最大

2、的數(shù)4已經(jīng)在最后面，因此第二輪排序只需要對前面三個(gè)數(shù)進(jìn)行再比較。第二輪排序過程2 3 1 4 （第一輪排序結(jié)果）2 3 1 4 （比較2和3，不交換）2 1 3 4 （比較3和1，交換第二輪結(jié)束，第二大的數(shù)已經(jīng)排在倒數(shù)第二個(gè)位置，所以第三輪只需要比較前兩個(gè)元素。第三輪排序過程2 1 3 4 （第二輪排序結(jié)果）1 2 3 4 （比較2和1，交換）至此，排序結(jié)束。1.1.2. 算法總結(jié)及實(shí)現(xiàn)對于具有N個(gè)元素的數(shù)組Rn，進(jìn)行最多N-1輪比較；第一輪，逐個(gè)比較（R1, R2）, （R2, R3）, （R3, R4）, . （RN-1, RN） ; 最大的元素會被移動到RN上。第二輪，逐個(gè)比較（R1,

3、R2）, （R2, R3）, （R3, R4）, . （RN-2, RN-1）；第二大元素會被移動到RN-1上。以此類推，直到整個(gè)數(shù)組從小到大排序。下面給出了冒泡排序的一般實(shí)現(xiàn)和優(yōu)化實(shí)現(xiàn)。一般實(shí)現(xiàn)是教科書里常見的實(shí)現(xiàn)方法，無論數(shù)組是否排序好了，都會進(jìn)行N-1輪比較；而優(yōu)化實(shí)現(xiàn)，在數(shù)組已經(jīng)排序好的情況下，會提前退出比較，減小了算法的時(shí)間復(fù)雜度。/* * Created on: 2015年4月25日 * Author: xia */#include#include#define N 8voidbubble_sort(int a, int n);/一般實(shí)現(xiàn)Void bubble_sort(int a

4、, int n) /n為數(shù)組a的元素個(gè)數(shù)/一定進(jìn)行N-1輪比較for (inti = 0; i n - 1; i+) /每一輪比較前n-1-i個(gè)，即已排序好的最后i個(gè)不用比較for (int j = 0; j aj + 1) int temp = aj;aj = aj + 1;aj + 1 = temp;/優(yōu)化實(shí)現(xiàn)void bubble_sort_better(int a, int n) /n為數(shù)組a的元素個(gè)數(shù)/最多進(jìn)行N-1輪比較for (inti = 0; i n - 1; i+) int isSorted = 1;/每一輪比較前n-1-i個(gè)，即已排序好的最后i個(gè)不用比較for (int

5、j = 0; j aj + 1) isSorted = 0;int temp = aj;aj = aj + 1;aj + 1 = temp;if (isSorted)break; /如果沒有發(fā)生交換，說明數(shù)組已經(jīng)排序好了intmain() intnumN = 89, 38, 11, 78, 96, 44, 19, 25 ;bubble_sort(num, N); /或者使用bubble_sort_better(num, N);for (inti = 0; i 2，所以min_index=2）3 2 4 1（2 1，所以min_index=4，這時(shí)候確定了第1小的數(shù)在位置4）1 2 4 3 （第

6、1輪結(jié)果，將3和1交換，也就是位置1和位置4交換）第2輪排序過程（尋找第2小的數(shù)所在的位置）1 2 4 3（第1輪結(jié)果，min_index=2，只需要從位置2開始尋找）1 2 4 3（4 2，所以min_index=2）1 2 4 3（3 2，所以min_index=2）1 2 4 3（第2輪結(jié)果，因?yàn)閙in_index位置剛好在第2個(gè)位置，無需交換）第3輪排序過程（尋找第3小的數(shù)所在的位置）1 2 4 3（第2輪結(jié)果，min_index=3，只需要從位置2開始尋找）1 2 4 3（4 3，所以min_index=4）1 2 3 4（第3輪結(jié)果，將3和4交換，也就是位置4和位置3交換）至此，排

7、序完畢。1.2.2. 總結(jié)及實(shí)現(xiàn)選擇排序?qū)Υ笮镹的無序數(shù)組RN進(jìn)行排序，進(jìn)行N-1輪選擇過程。第i輪選取第i小的數(shù)，并將其放在第i個(gè)位置上。當(dāng)?shù)贜-1次完成時(shí)，第N?。ㄒ簿褪亲畲螅┑臄?shù)自然在最后的位置上。下面給出選擇排序的C語言實(shí)現(xiàn)。/* * Created on: 2015年4月25日 * Author: xia */#include#include#define N 8Void select_sort(int a, int n);/選擇排序?qū)崿F(xiàn)Void select_sort(int a, int n) /n為數(shù)組a的元素個(gè)數(shù)/進(jìn)行N-1輪選擇for (inti = 0; i n - 1

8、; i+) int min_index = i;/找出第i小的數(shù)所在的位置for (int j = i + 1; j n; j+) if (aj amin_index) min_index = j;/將第i小的數(shù)，放在第i個(gè)位置；如果剛好，就不用交換if (i != min_index) int temp = ai;ai = amin_index;amin_index = temp;intmain() intnumN = 89, 38, 11, 78, 96, 44, 19, 25 ;select_sort(num, N);for (inti = 0; i2，所以待插入位置j=1） 2 3 4

9、 1 （將2插入到位置j）第2輪 2 3 4 1 （第1輪排序結(jié)果） 2 3 4 1 （由于24，所以先假定j=2） 2 3 4 1 （由于34，所以j=3） 2 3 4 1 （由于4剛好在位置3，無需插入）第3輪 2 3 4 1 （第2輪排序結(jié)果） 2 3 4 1 （由于12，所以j=1）1 2 3 4 （將1插入位置j，待排序元素為空，排序結(jié)束）1.3.2. 算法總結(jié)及實(shí)現(xiàn)選擇排序?qū)Υ笮镹的無序數(shù)組RN進(jìn)行排序，進(jìn)行N-1輪選擇過程。首先將第1個(gè)元素作為已經(jīng)排序好的子數(shù)組，然后將剩余的N-1個(gè)元素，逐個(gè)插入到已經(jīng)排序好子數(shù)組；。因此，在第i輪排序時(shí)，前i個(gè)元素總是有序的，將第i+1個(gè)元素

10、插入到正確的位置。/* * Created on: 2015年4月25日 * Author: xia */#include#include#define N 8void insert_sort(int a, int n);/插入排序?qū)崿F(xiàn),這里按從小到大排序voidinsert_sort(int a, int n) /n為數(shù)組a的元素個(gè)數(shù)/進(jìn)行N-1輪插入過程for (int i = 1; i n; i+) /首先找到元素ai需要插入的位置int j = 0;while (aj ai) & (j j; k-) ak = ak - 1;aj = temp;intmain() intnumN = 8

11、9, 38, 11, 78, 96, 44, 19, 25 ;insert_sort(num, N);for (inti = 0; i N; i+)printf(%d , numi);printf(n);system(pause);return 0;注意：插入排序是一種穩(wěn)定的排序算法，不會改變原有序列中相同數(shù)字的順序。插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。當(dāng)然，剛開始這個(gè)有序的小序列只有1個(gè)元素，就是第一個(gè)元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個(gè)和插入

12、元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。1.4. 快速排序算法快速排序是對冒泡法排序的一種改進(jìn)。1.4.1. 基本思想及舉例說明快速排序算法的基本思想是：將所要進(jìn)行排序的數(shù)分為左右兩個(gè)部分，其中一部分的所有數(shù)據(jù)都比另外一部分的數(shù)據(jù)小，然后將所分得的兩部分?jǐn)?shù)據(jù)進(jìn)行同樣的劃分，重復(fù)執(zhí)行以上的劃分操作，直到所有要進(jìn)行排序的數(shù)據(jù)變?yōu)橛行驗(yàn)橹埂？赡軆H根據(jù)基本思想對快速排序的認(rèn)識并不深，接下來以對n個(gè)無序數(shù)列A0, A1, An-1采用快速排序方法進(jìn)行升序排列為例進(jìn)行講解。1) 定義兩個(gè)變量

13、low和high，將low、high分別設(shè)置為要進(jìn)行排序的序列的起始元素和最后一個(gè)元素的下標(biāo)。第一次，low和high的取值分別為0和n-1，接下來的每次取值由劃分得到的序列起始元素和最后一個(gè)元素的下標(biāo)來決定。2) 定義一個(gè)變量key，接下來以key的取值為基準(zhǔn)將數(shù)組A劃分為左右兩個(gè)部分，通常，key值為要進(jìn)行排序序列的第一個(gè)元素值。第一次的取值為A0，以后毎次取值由要劃分序列的起始元素決定。3) 從high所指向的數(shù)組元素開始向左掃描，掃描的同時(shí)將下標(biāo)為high的數(shù)組元素依次與劃分基準(zhǔn)值key進(jìn)行比較操作，直到high不大于low或找到第一個(gè)小于基準(zhǔn)值key的數(shù)組元素，然后將該值賦值給low

14、所指向的數(shù)組元素，同時(shí)將low右移一個(gè)位置。4) 如果low依然小于high，那么由low所指向的數(shù)組元素開始向右掃描，掃描的同時(shí)將下標(biāo)為low的數(shù)組元素值依次與劃分的基準(zhǔn)值key進(jìn)行比較操作，直到low不小于high或找到第一個(gè)大于基準(zhǔn)值key的數(shù)組元素，然后將該值賦給high所指向的數(shù)組元素，同時(shí)將high左移一個(gè)位置。5) 重復(fù)步驟(3) (4)，直到low的植不小于high為止，這時(shí)成功劃分后得到的左右兩部分分別為Alowpos-1和Apos+1high，其中，pos下標(biāo)所對應(yīng)的數(shù)組元素的值就是進(jìn)行劃分的基準(zhǔn)值key，所以在劃分結(jié)束時(shí)還要將下標(biāo)為pos的數(shù)組元素賦值為 key。6) 將

15、劃分得到的左右兩部分Alowpos-1和Apos+1high繼續(xù)采用以上操作步驟進(jìn)行劃分，直到得到有序序列為止。1.4.2. 代碼實(shí)現(xiàn)為了能夠加深理解，接下來通過一段代碼來了解快速排序的具體實(shí)現(xiàn)方法。/* * Created on: 2015年4月25日 * Author: xia */#include#include#define N 6intpartition(intarr, int low, int high) int key;key = arrlow;while (low high) while (low = key)high-;if (low high)arrlow+ = arrhi

16、gh;while (low high &arrlow = key)low+;if (low high)arrhigh- = arrlow;arrlow = key;return low;voidquick_sort(intarr, int start, int end) intpos;if (start end) pos = partition(arr, start, end);quick_sort(arr, start, pos - 1);quick_sort(arr, pos + 1, end);return;intmain(void) inti;intarrN = 32, 12, 7,

17、78, 23, 45 ;printf(排序前 n);for (i = 0; i N; i+)printf(%dt, arri);quick_sort(arr, 0, N - 1);printf(n 排序后 n);for (i = 0; i N; i+)printf(%dt, arri);printf(n);system(pause);return 0;運(yùn)行結(jié)果：排序前32 12 7 78 23 45排序后7 12 23 32 45 78在上面的代碼中，根據(jù)前面介紹的步驟一步步實(shí)現(xiàn)了快速排序算法。接下來通過示意圖來演示第一次劃分操作。在第一次劃分操作中，先進(jìn)行初始設(shè)置，key的值是進(jìn)行劃分的基準(zhǔn)

18、，其值為要劃分?jǐn)?shù)組的第一個(gè)元素值，在上面的排序序列中為第一個(gè)元素值32，同時(shí)將low設(shè)置為要排序數(shù)組中第一個(gè)元素的下標(biāo)，第一次排序操作時(shí)其值為0，將high設(shè)置為要排序序列最后一個(gè)元素的下標(biāo)，在上面的排序序列中其第一次取值為5。先將下標(biāo)為high的數(shù)組元素與key進(jìn)行比較，由于該元素值大于key，因此high向左移動一個(gè)位置繼續(xù)掃描。由于接下來的值為 23，小于key的值，因此將23賦值給下標(biāo)為low所指向的數(shù)組元素。接下來將low右移一個(gè)位置，將low所指向的數(shù)組元素的值與key進(jìn)行比較，由干接下來的12、7都小于key，因此low繼續(xù)右移掃描，直至下標(biāo)low所指向的數(shù)組元素的值為78即大于

19、key為止，將78賦值給下標(biāo)為high所指向的數(shù)組元素，同時(shí)將high左移一個(gè)位置。接下來由于low不再小于high，劃分結(jié)束。需要注意的是，在進(jìn)行劃分的過程中，都是將掃描的值與key的值進(jìn)行對比，如果小于key，那么將該值賦值給數(shù)組中的另外一個(gè)元素，而該元素的值并沒有改變。從圖中可以看出這一點(diǎn)，所以需要在劃分的最后將作為劃分基準(zhǔn)的key值賦值給下標(biāo)為pos的數(shù)組元素，這個(gè)元素不再參與接下來的劃分操作。第一輪劃分結(jié)束后，得到了左右兩部分序列A0、A1、A2和A4、A5，繼續(xù)進(jìn)行劃分，即對毎輪劃分后得到的兩部分序列繼續(xù)劃分，直至得到有序序列為止。Java實(shí)現(xiàn)public class QuickS

20、ort static void quicksort(intn, int left, intright) intdp;if (leftright) dp = partition(n, left, right);quicksort(n, left, dp - 1);quicksort(n, dp + 1, right); static int partition(intn, int left, int right) int pivot = nleft;while (leftright) while (left= pivot)right-;if (leftright)nleft+ = nright;

21、while (leftright&nleft = pivot)left+;if (leftright)nright- = nleft; nleft = pivot;return left; publicstaticvoid main(String args) int array = newint 11, 213, 134, 44, 77, 78, 23, 43 ;quicksort(array, 0, array.length - 1);for (inti = 0; iarray.length; i+) System.out.println(i + 1) + th: + arrayi);1.5

22、. 歸并排序算法1.5.1. 算法思想歸并排序也稱合并排序，其算法思想是將待排序序列分為兩部分，依次對分得的兩個(gè)部分再次使用歸并排序，之后再對其進(jìn)行合并。僅從算法思想上了解歸并排序會覺得很抽象，接下來就以對序列A0, Al, An-1進(jìn)行升序排列來進(jìn)行講解，在此采用自頂向下的實(shí)現(xiàn)方法，操作步驟如下。1) 將所要進(jìn)行的排序序列分為左右兩個(gè)部分，如果要進(jìn)行排序的序列的起始元素下標(biāo)為first，最后一個(gè)元素的下標(biāo)為last，那么左右兩部分之間的臨界點(diǎn)下標(biāo)mid=(first+last)/2，這兩部分分別是Afirst mid和Amid+1 last。2) 將上面所分得的兩部分序列繼續(xù)按照步驟(1)繼

23、續(xù)進(jìn)行劃分，直到劃分的區(qū)間長度為1。3) 將劃分結(jié)束后的序列進(jìn)行歸并排序，排序方法為對所分的n個(gè)子序列進(jìn)行兩兩合并，得到n/2或n/2+l個(gè)含有兩個(gè)元素的子序列，再對得到的子序列進(jìn)行合并，直至得到一個(gè)長度為n的有序序列為止。下面通過一段代碼來看如何實(shí)現(xiàn)歸并排序。1.5.2. 實(shí)現(xiàn)代碼/* * Created on: 2015年4月25日 * Author: xia */#include#include#define N 7voidmerge(intarr, int low, int mid, int high) inti, k;int *tmp = (int *) malloc(high -

24、low + 1) * sizeof(int);/申請空間，使其大小為兩個(gè)intleft_low = low;intleft_high = mid;intright_low = mid + 1;intright_high = high;for (k = 0; left_low= left_high&right_low= right_high; k+) / 比較兩個(gè)指針?biāo)赶虻脑豬f (arrleft_low = arrright_low) tmpk = arrleft_low+; else tmpk = arrright_low+;if (left_low= left_high) /若第一個(gè)序

25、列有剩余，直接復(fù)制出來粘到合并序列尾/memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int);for (i = left_low; i= left_high; i+)tmpk+ = arri;if (right_low= right_high) /若第二個(gè)序列有剩余，直接復(fù)制出來粘到合并序列尾/memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int);for (i = right_low; i= right_high; i+)tmpk+ = arri;

26、for (i = 0; i high - low + 1; i+)arrlow + i = tmpi;free(tmp);return;voidmerge_sort(intarr, unsignedint first, unsignedint last) int mid = 0;if (first 1);merge_sort(arr, first, mid);merge_sort(arr, mid + 1, last);merge(arr, first, mid, last);return;intmain() inti;int aN = 32, 12, 56, 78, 76, 45, 36 ;

27、printf(排序前 n);for (i = 0; i N; i+)printf(%dt, ai);merge_sort(a, 0, N - 1); / 排序printf(n 排序后 n);for (i = 0; i N; i+)printf(%dt, ai);printf(n);system(pause);return 0;運(yùn)行結(jié)果：排序前32 12 56 78 76 45 36排序后12 32 36 45 56 76 78分析上面的運(yùn)行結(jié)果，通過歸并排序成功地實(shí)現(xiàn)了對給定序列的排序操作。接下來通過下圖來了解歸并排序的具體操作流程。在下圖中，先對所要進(jìn)行排序的序列進(jìn)行分解，直到分為單個(gè)元素為

28、止，然后將其進(jìn)行兩兩合并。由于最終分解成單個(gè)元素，因此在合并的時(shí)候.將小數(shù)放在前面，大數(shù)放在后面，得到一個(gè)有序序列。接下來對兩個(gè)相連的有序序列進(jìn)行排序，先比較有序序列中的第一個(gè)元素，將較小的元素放入臨時(shí)數(shù)組中，接著將較小元素所在數(shù)組的下一個(gè)元素與另一個(gè)數(shù)組中的較小元素比較，同樣將較小元素放入臨時(shí)數(shù)組中，依次進(jìn)行，直到兩個(gè)數(shù)組的所有元素都放入臨時(shí)數(shù)組中，最后再將臨時(shí)數(shù)組的元素放入原始數(shù)組中的對應(yīng)位置。1.6. 順序查找算法、1.6.1. 算法思想順序査找是一種簡單的査找算法，其實(shí)現(xiàn)方法是從序列的起始元素開始，逐個(gè)將序列中的元素與所要查找的元素進(jìn)行比較，如果序列中有元素與所要查找的元素相等，那么査

29、找成功，如果査找到序列的最后一個(gè)元素都不存在一個(gè)元素與所要査找的元素值相等，那么表明査找失敗。接下來通過一段代碼來了解順序査找的具體使用。1.6.2. 代碼實(shí)現(xiàn)/* * Created on: 2015年4月25日 * Author: xia */#include#include#includeintordersearch(int a, int n, int des)inti;for(i=0; in; i+)if(des=ai)return 1;return 0;intmain()inti, val;int a8 = 32,12,56,78,76,45,43,98;int ret;for(i=

30、0; i8; i+)printf(%dt, ai);printf(n請輸入所要查找的元素：);while(1)scanf(%d, &val);fflush(stdin); ret = ordersearch(a, 8, val);if(1 = ret)printf (查找成功！);elseprintf (查找失??！);printf(n請輸入所要查找的元素：); return 0;運(yùn)行結(jié)果：32 12 56 78 76 45 43 98請輸出所要查找的元素：78查找成功！請輸出所要查找的元素：5查找失??！分析上面的運(yùn)行結(jié)果，首先輸入所要查找的元素為78，該數(shù)在所要查找的序列中是存在的，所以打印輸出“查找成功！ ”。接下來輸入的數(shù)值5在所要查