十大经典排序算法( 三 ) _排序算法

6.1、算法描述
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
6.2、动图演示

文章插图

?6.3、代码实现
/** * 归并排序 * * @param array * @return */public static int[] MergeSort(int[] array) { if (array.length < 2) return array; int mid = array.length / 2; int[] left = Arrays.copyOfRange(array, 0, mid); int[] right = Arrays.copyOfRange(array, mid, array.length); return merge(MergeSort(left), MergeSort(right));}/** * 归并排序——将两段排序好的数组结合成一个排序数组 * * @param left * @param right * @return */public static int[] merge(int[] left, int[] right) { int[] result = new int[left.length + right.length]; for (int index = 0, i = 0, j = 0; index < result.length; index++) {if (i >= left.length)result[index] = right[j++];else if (j >= right.length)result[index] = left[i++];else if (left[i] > right[j])result[index] = right[j++];elseresult[index] = left[i++]; } return result;}6.4、算法分析
最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
七、快速排序（Quick Sort）快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
7.1、算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
7.2、动图演示

文章插图

?7.3、代码实现
/** * 快速排序方法 * @param array * @param start * @param end * @return */public static int[] QuickSort(int[] array, int start, int end) { if (array.length < 1 || start < 0 || end >= array.length || start > end) return null; int smallIndex = partition(array, start, end); if (smallIndex > start)QuickSort(array, start, smallIndex - 1); if (smallIndex < end)QuickSort(array, smallIndex + 1, end); return array;}/** * 快速排序算法——partition * @param array * @param start * @param end * @return */public static int partition(int[] array, int start, int end) { int pivot = (int) (start + Math.random() * (end - start + 1)); int smallIndex = start - 1; swap(array, pivot, end); for (int i = start; i <= end; i++)if (array[i] <= array[end]) {smallIndex++;if (i > smallIndex)swap(array, i, smallIndex);} return smallIndex;} /** * 交换数组内两个元素 * @param array * @param i * @param j */public static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp;}【十大经典排序算法】7.4、算法分析
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
八、堆排序（Heap Sort）堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
8.1、算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn) 。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

8.2、动图演示

文章插图

8.3、代码实现
//声明全局变量，用于记录数组array的长度；static int len;/** * 堆排序算法 * * @param array * @return */public static int[] HeapSort(int[] array) { len = array.length; if (len < 1) return array; //1.构建一个最大堆 buildMaxHeap(array); //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆 while (len > 0) {swap(array, 0, len - 1);len--;adjustHeap(array, 0); } return array;}/** * 建立最大堆 * * @param array */public static void buildMaxHeap(int[] array) { //从最后一个非叶子节点开始向上构造最大堆 for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆网友的提醒，此处应该为 i = (len/2 - 1)adjustHeap(array, i); }}/** * 调整使之成为最大堆 * * @param array * @param i */public static void adjustHeap(int[] array, int i) { int maxIndex = i; //如果有左子树，且左子树大于父节点，则将最大指针指向左子树 if (i * 2 < len && array[i * 2] > array[maxIndex])maxIndex = i * 2; //如果有右子树，且右子树大于父节点，则将最大指针指向右子树 if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])maxIndex = i * 2 + 1; //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。if (maxIndex != i) {swap(array, maxIndex, i);adjustHeap(array, maxIndex); }}