1、基本思想：
在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。
2、實(shí)例
3、算法實(shí)現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
/** * 選擇排序算法 * 在未排序序列中找到最小元素，存放到排序序列的起始位置 * 再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，然后放到排序序列末尾。 * 以此類推，直到所有元素均排序完畢。 * @param numbers */ public static void selectsort(int[] numbers) { int size = numbers.length; //數(shù)組長(zhǎng)度 int temp = 0 ; //中間變量 for(int i = 0 ; i < size ; i++) { int k = i; //待確定的位置 //選擇出應(yīng)該在第i個(gè)位置的數(shù) for(int j = size -1 ; j > i ; j--) { if(numbers[j] < numbers[k]) { k = j; } } //交換兩個(gè)數(shù) temp = numbers[i]; numbers[i] = numbers[k]; numbers[k] = temp; } } |
二、插入排序
1、基本思想：每步將一個(gè)待排序的記錄，按其順序碼大小插入到前面已經(jīng)排序的字序列的合適位置（從后向前找到合適位置后），直到全部插入排序完為止。
2、實(shí)例
3、算法實(shí)現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
/** * 插入排序 * * 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序 * 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描 * 如果該元素（已排序）大于新元素，將該元素移到下一位置 * 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置 * 將新元素插入到該位置中 * 重復(fù)步驟2 * @param numbers 待排序數(shù)組 */ public static void insertsort(int[] numbers) { int size = numbers.length; int temp = 0 ; int j = 0; for(int i = 0 ; i < size ; i++) { temp = numbers[i]; //假如temp比前面的值小，則將前面的值后移 for(j = i ; j > 0 && temp < numbers[j-1] ; j --) { numbers[j] = numbers[j-1]; } numbers[j] = temp; } } |
4、效率：
時(shí)間復(fù)雜度：o（n^2）.
三、希爾算法
1、基本思想：
先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。
2、操作方法：
選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
希爾排序的示例：
3、算法實(shí)現(xiàn)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
/**希爾排序的原理:根據(jù)需求，如果你想要結(jié)果從大到小排列，它會(huì)首先將數(shù)組進(jìn)行分組，然后將較大值移到前面，較小值 * 移到后面，最后將整個(gè)數(shù)組進(jìn)行插入排序，這樣比起一開(kāi)始就用插入排序減少了數(shù)據(jù)交換和移動(dòng)的次數(shù)，可以說(shuō)希爾排序是加強(qiáng) * 版的插入排序 * 拿數(shù)組5, 2, 8, 9, 1, 3，4來(lái)說(shuō)，數(shù)組長(zhǎng)度為7，當(dāng)increment為3時(shí)，數(shù)組分為兩個(gè)序列 * 5，2，8和9，1，3，4，第一次排序，9和5比較，1和2比較，3和8比較，4和比其下標(biāo)值小increment的數(shù)組值相比較 * 此例子是按照從大到小排列，所以大的會(huì)排在前面，第一次排序后數(shù)組為9, 2, 8, 5, 1, 3，4 * 第一次后increment的值變?yōu)?/2=1,此時(shí)對(duì)數(shù)組進(jìn)行插入排序， *實(shí)現(xiàn)數(shù)組從大到小排 */ public static void shellsort(int[] data) { int j = 0; int temp = 0; //每次將步長(zhǎng)縮短為原來(lái)的一半 for (int increment = data.length / 2; increment > 0; increment /= 2) { for (int i = increment; i < data.length; i++) { temp = data[i]; for (j = i; j >= increment; j -= increment) { if(temp > data[j - increment])//如想從小到大排只需修改這里 { data[j] = data[j - increment]; } else { break; } } data[j] = temp; } } } |
4、效率
時(shí)間復(fù)雜度：o（n^2）.
4、各種算法的時(shí)間復(fù)雜度
以上所述是小編給大家介紹的java 選擇排序、插入排序、希爾算法實(shí)例詳解，希望對(duì)大家有所幫助
