八大排序算法(下篇)

1、1.快速排序通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。/* Created by adrian on 2015/1/25.* 快速排序:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小* ,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。*/public class QuickSort / 初始化数组public static void

2、init(int array Random random = new Random(;for (int i = 0; i array.length; i+arrayi = random.nextInt(1000;/ 打印数组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.希尔排序希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。/* Created by adrian on 2015/1/25.* 希尔排序:按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排

5、序的元素个数很少* ,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。*/public class ShellSort / 初始化数组public static void init(int array Random random = new Random(;for (int i = 0; i array.length; i+arrayi = random.nextInt(1000;/ 打印数组public static void display(int array for (int i = 0; i array.length; i+ / 换行if (i + 1 % 10

6、= 0/* 对每个步长增量序列排序* param array* 数组* 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* 数组*/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.* 归并排序:首先是根据元素构建堆。然后将堆的根节点取出(一般是与最好一个节点进行交换,将前面len* -1个节点继续进行堆调整的过程,然后再将根节点取出,这样一直到所有节点都取出*/public class MergeSort / 初始化数组public static void init(int array Random random = new Random(;for (int i = 0; i array.length; i+arrayi = random.nextInt(1000;/ 打印数组

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; / 合并数组，升序 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