Nice！第一次见这么全面的Java实现八大排序算法，爱了( 三 ) 它们都属于内部排序

父节点i的左子节点在位置：(2*i+1);
父节点i的右子节点在位置：(2*i+2);
子节点i的父节点在位置：floor((i-1)/2);

/** * @param a */public static void sort(int[] a) {for (int i = a.length - 1; i > 0; i--) {max_heapify(a, i);//堆顶元素(第一个元素)与Kn交换int temp = a[0];a[0] = a[i];a[i] = temp;}}/*** * *将数组堆化 *i = 第一个非叶子节点 。*从第一个非叶子节点开始即可 。 无需从最后一个叶子节点开始 。*叶子节点可以看作已符合堆要求的节点 ， 根节点就是它自己且自己以下值为最大 。* * @param a * @param n */public static void max_heapify(int[] a, int n) {int child;for (int i = (n - 1) / 2; i >= 0; i--) {//左子节点位置child = 2 * i + 1;//右子节点存在且大于左子节点 ， child变成右子节点if (child != n}//交换父节点与左右子节点中的最大值if (a[i] < a[child]) {int temp = a[i];a[i] = a[child];a[child] = temp;}}}

复杂度分析

建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);
调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);
堆排序的过程由n次第2步完成, 时间复杂度为O(nlgn).

文章插图
总结与思考由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列。同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序。
冒泡排序我想对于它每个学过C语言的都会了解，这可能是很多人接触的第一个排序算法。
基本思想冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法描述冒泡排序算法的运作如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

文章插图
代码实现

public static void sort(int[] a) {//外层循环控制比较的次数for (int i = 0; i < a.length - 1; i++) {//内层循环控制到达位置for (int j = 0; j < a.length - i - 1; j++) {//前面的元素比后面大就交换if (a[j] > a[j + 1]) {int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}}

复杂度分析以下是冒泡排序算法复杂度:

文章插图
冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n2/2次, 时间复杂度为O(n2). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n2). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).
总结与思考由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。
快速排序快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
基本思想快速排序的基本思想：挖坑填数+分治法。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n2) ，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。