八大排序算法(下篇)

1、1.快速排序通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個(gè)排序過(guò)程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。/* Created by adrian on 2015/1/25.* 快速排序:通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小* ,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個(gè)排序過(guò)程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。*/public class QuickSort / 初始化數(shù)組public static void

2、init(int array Random random = new Random(;for (int i = 0; i array.length; i+arrayi = random.nextInt(1000;/ 打印數(shù)組public static void display(int array for (int i = 0; i = hightreturn;/ 比較值int key = arraylow;/ 原始下標(biāo)int low_index = low, hight_index = hight;while (low hight / 如果低位下標(biāo)小于高位下標(biāo)并且高位值不小于比較值while

3、(low = keyhight-;/ 符合條件的值(小于比較值被移到key的左邊arraylow = arrayhight;/ 如果低位下標(biāo)小于高位下標(biāo)并且低位值不大于比較值while (low hight & arraylow = keylow+;/ 符合條件的值(大于比較值被移到key的右邊arrayhight = arraylow;/ key值位置(此時(shí)的結(jié)果是low=hightarraylow = key;/ 遞歸左邊部分quick(array, low_index, low - 1;/ 遞歸右邊部分quick(array, low + 1, hight_index;/ 測(cè)試publi

4、c static void main(String args int array = new int100;init(array;display(array;quick(array, 0, array.length - 1;display(array;2.希爾排序希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序,當(dāng)剛開(kāi)始元素很無(wú)序的時(shí)候,步長(zhǎng)最大,所以插入排序的元素個(gè)數(shù)很少,速度很快;當(dāng)元素基本有序了,步長(zhǎng)很小,插入排序?qū)τ谟行虻男蛄行屎芨摺?* Created by adrian on 2015/1/25.* 希爾排序:按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序,當(dāng)剛開(kāi)始元素很無(wú)序的時(shí)候,步長(zhǎng)最大,所以插入排

5、序的元素個(gè)數(shù)很少* ,速度很快;當(dāng)元素基本有序了,步長(zhǎng)很小,插入排序?qū)τ谟行虻男蛄行屎芨摺?/public class ShellSort / 初始化數(shù)組public static void init(int array Random random = new Random(;for (int i = 0; i array.length; i+arrayi = random.nextInt(1000;/ 打印數(shù)組public static void display(int array for (int i = 0; i array.length; i+ / 換行if (i + 1 % 10

6、= 0/* 對(duì)每個(gè)步長(zhǎng)增量序列排序* param array* 數(shù)組* param d* 步長(zhǎng)* param begainIndex* 第一個(gè)排序下標(biāo)*/private static void insert(int array, int d, int begainIndex for (int i = begainIndex + d; i array.length; i += d for (int j = begainIndex; j i; j += d if (arrayi j; k -= d arrayk = arrayk - d;arrayj = tempValue;/* param ar

7、ray* 數(shù)組*/public static void shell(int array / 步長(zhǎng)int d = array.length 1;while (d = 1 / 對(duì)每個(gè)步長(zhǎng)增量序列排序for (int i = 0; i = 1;/ 測(cè)試public static void main(String args int array = new int100;init(array;display(array;shell(array;display(array;3.歸并排序合并排序法是將兩個(gè)(或兩個(gè)以上有序表合并成一個(gè)新的有序表,即把待排序序列分為若干個(gè)子序列,每個(gè)子序列是有序的。然后再把有序

8、子序列合并為整體有序序列。/* Created by adrian on 2015/1/26.* 歸并排序:首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點(diǎn)取出(一般是與最好一個(gè)節(jié)點(diǎn)進(jìn)行交換,將前面len* -1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過(guò)程,然后再將根節(jié)點(diǎn)取出,這樣一直到所有節(jié)點(diǎn)都取出*/public class MergeSort / 初始化數(shù)組public static void init(int array Random random = new Random(;for (int i = 0; i array.length; i+arrayi = random.nextInt(1000;/ 打印數(shù)組

9、public static void display(int array for (int i = 0; i 1; if (len 1 int leftArray = Arrays.copyOfRange(array, 0, middle; int rightArray = Arrays.copyOfRange(array, middle, len; mergeSort(leftArray; mergeSort(rightArray; merge(array, leftArray, rightArray; / 合并數(shù)組，升序 private static void merge(int result, int left, int right int i = 0, l = 0, r = 0; while (l left.length & r right.length if (leftl rightr resulti = leftl; i+; l+; else re