八大排序算法(下篇)

1、1.快速排序通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數(shù)據(jù)變成有序序列。/* Created by adrian on 2015/1/25.* 快速排序:通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小* ,然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數(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;/ 原始下標int low_index = low, hight_index = hight;while (low hight / 如果低位下標小于高位下標并且高位值不小于比較值while

3、(low = keyhight-;/ 符合條件的值(小于比較值被移到key的左邊arraylow = arrayhight;/ 如果低位下標小于高位下標并且低位值不大于比較值while (low hight & arraylow = keylow+;/ 符合條件的值(大于比較值被移到key的右邊arrayhight = arraylow;/ key值位置(此時的結果是low=hightarraylow = key;/ 遞歸左邊部分quick(array, low_index, low - 1;/ 遞歸右邊部分quick(array, low + 1, hight_index;/ 測試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.希爾排序希爾排序是按照不同步長對元素進行插入排序,當剛開始元素很無序的時候,步長最大,所以插入排序的元素個數(shù)很少,速度很快;當元素基本有序了,步長很小,插入排序對于有序的序列效率很高。/* Created by adrian on 2015/1/25.* 希爾排序:按照不同步長對元素進行插入排序,當剛開始元素很無序的時候,步長最大,所以插入排

5、序的元素個數(shù)很少* ,速度很快;當元素基本有序了,步長很小,插入排序對于有序的序列效率很高。*/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/* 對每個步長增量序列排序* param array* 數(shù)組* param d* 步長* param begainIndex* 第一個排序下標*/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 / 步長int d = array.length 1;while (d = 1 / 對每個步長增量序列排序for (int i = 0; i = 1;/ 測試public static void main(String args int array = new int100;init(array;display(array;shell(array;display(array;3.歸并排序合并排序法是將兩個(或兩個以上有序表合并成一個新的有序表,即把待排序序列分為若干個子序列,每個子序列是有序的。然后再把有序

8、子序列合并為整體有序序列。/* Created by adrian on 2015/1/26.* 歸并排序:首先是根據(jù)元素構建堆。然后將堆的根節(jié)點取出(一般是與最好一個節(jié)點進行交換,將前面len* -1個節(jié)點繼續(xù)進行堆調整的過程,然后再將根節(jié)點取出,這樣一直到所有節(jié)點都取出*/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