最近算法老师让大家抓紧时间完成算法作业，总共四个题目。这几个题目都很不错，我计划着把这四个作业写成四篇博客，一是可以记录下来供大家分享学习，二是可以提升自己对于这几个算法的理解。

---

任务要求：实现排序类，公共函数包括冒泡排序、快速排序（递归）、堆排序。将递归算法改写为非递归的，进行比较。

---

算法思想：

（1） 冒泡排序：临近数据的关键码进行两两比较，按照顺序（从小到大或者从大到小）进行交换，这样一趟走过去之后，拥有最大或者最小的关键码的数据被交换到了最后一个位置；然后，再从头开始进行两两比较，直到倒数第二位结束；依照上面的步骤，直到确定第一个位置的数据或者这一组的数据经过一趟冒泡之后不再发生变化时，冒泡排序结束。这样得出的结果序列就是我们预期要得到的有序序列。
（2） 快速排序（递归）：任取待排序对象中的某个对象作为基准，按照该对象的关键码大小，将整个对象序列划分为左右两个子序列。其中，左侧子序列中所有的关键码都小于或等于基准对象的关键码；右侧子序列中所有对象的关键码都大于基准对象的关键码。此时基准对象所在的位置也就是该对象在该序列中最终应该安放的位置。然后递归的在左右子序列中重复实施上述的方法，直至所有的对象都放到相应的位置上为止。
（3） 快速排序（非递归）：递归的快排算法是编译器自动用栈来实现的，当递归层次比较深的时候，需要占用比较大的进程栈空间，会造成进程栈溢出的危险。因此我们可以自己用栈模拟递归过程，即每次从栈顶取出一部分做划分之后，都把新的两部分的起始位置分别入栈。
（4） 堆排序：利用大顶堆（或者小顶堆）堆顶记录的是最大关键字（最小关键字）这一特性，实现对序列的排序。以大顶堆为例。首先，将初始待排序关键字序列（R1，R2…Rn）构建成一个大顶堆，此时的堆为初始的无序区。然后，将堆顶的元素R1与最后一个元素Rn交换，此时得到新的无序区（R1，R2…Rn-1）和新的有序区（Rn），且此时满足R1，R2…Rn-1 <= Rn。经过如上的交换之后，新的顶堆可能违反大顶堆的性质，因此需要对新产生的无序区（R1，R2…Rn-1）进行调整使之成为新的大顶堆，然后再将R1与Rn-1（无序区中最后一个元素）进行交换。不断重复以上过程直至有序区中的元素个数达到n-1个为止，完成整个排序过程。

设计思路：

（1） 冒泡排序：冒泡排序需要用到双重循环。首先，实现内层循环，即进行相邻元素之间的比较，该调换顺序的调换顺序，不用调换顺序的进行下一位的比较。其次，再实现外层循环，根据冒泡排序的思想，每次内循环结束后，都会有一个最小值（或者最大值）到达它最终应该到达的位置，因此下一趟内循环的比较次数就减少一次，于是我们应该在外循环中控制内层循环的次数。内层循环结束退出后，外层循环减一再进入内循环。为了防止有序序列已经出现的时候，我们的循环还在运行，不妨设置一个标志位，初始为0，如果在内部循环中发生了交换则将其置为1。如果内层循环结束后，我们的标志位仍为0，则表示我们的序列已经有序，无需再继续执行下去，此时便可以返回当前的有序序列了。
（2） 快速排序（递归）：快排的设计思路基于分治法。首先，选取一个元素作为切分元素pivot，然后基于pivot把数组切分为三部分：左子数组（元素小于或者等于pivot），pivot，右子数组（元素大于pivot）。然后，递归地对左右两个子数组进行快速排序，只要保证左右两个子数组分别有序，整个数组也就有序了。
（3） 快速排序（非递归）：自己构造一个栈，栈中存放待排序数组的起始位置和终止位置，然后将整个数组的起始位置s和终止位置e入栈，然后从s到e依次对出栈数据进行排序，找到基准数据最终的位置p。在基准位置左侧，判断起始位置s是否小于基准位置p-1，如果小于则将起始位置和新的终点(p-1)位置进栈。同理，在基准位置右侧，判断e是否大于基准位置p+1，若大于则将p+1作为起始位置，e作为终点位置进栈。在这两个新的栈中找到各自的基准数据的最终位置。如此往复直至栈空。
（4） 堆排序：堆排序中关键的就是建立大顶堆的过程和调整过程，而调整过程是最为重要的。从最末非叶节点（根据树的结构，不难得出这个位置为Array.length/2向下取整）开始，然后依次往前调整；然后我们再讨论调整过程，首先和当前节点的左子女进行比较，用一个值largest记录比较出来的比较大的那个值的index，然后再让这个largest所代表的值与该节点的右子女进行比较，依旧用largest记录较大值的index，最后比较当前节点与这个largest所代表的值，如果相等说明我们当前节点就是这个三节点两层子树的最大值，如果不相等，我们应该将这个值与我们当前的节点（子树父节点）交换。按照以上步骤建立大顶堆，然后将大顶堆堆顶的值与该树的最后一个节点进行交换，此时便分出来两个区，也就是我们算法思想中提到的无序区和有序区。交换之后的，再对新的Array进行新一轮的调整。为了方便，我同时也实现了一个数组的工具类，它有两个功能，一是打印Array；另一个功能就是实现两个数的交换功能。

程序代码：

（1） 冒泡排序：

public class BubbleSort {public static void main(String[] args) {// TODO Auto-generated method stubint A[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };BubbleSort(A, 10);for (int i = 0; i < 10; i++) {System.out.print(A[i] + " ");}}public static void BubbleSort(int A[], int n) {boolean flag = false;int temp;for (int i = 0; i < n - 1; i++) {flag = false;for (int j = n - 1; j > i; j--)if (A[j - 1] > A[j]) {temp = A[j - 1];A[j - 1] = A[j];A[j] = temp;flag = true;}if (flag == false)return;}}}

（2） 快速排序：

public class QuickSort {public static void main(String[] args) {int A[] = { 1, 5, 8, 2, 4, 6, 3, 7, 9, 0 };int low = 0;int high = A.length - 1;QuickSort(A, low, high);for (int i = 0; i < A.length; i++) {System.out.print(A[i] + " ");}}public static void QuickSort(int A[], int low, int high) {if (low < high) {int pivotpos = Partition(A, low, high);QuickSort(A, low, pivotpos - 1);QuickSort(A, pivotpos + 1, high);}}public static int Partition(int A[], int low, int high) {int pivot = A[low];while (low < high) {while (low < high && A[high] >= pivot)--high;A[low] = A[high];while (low < high && A[low] <= pivot)++low;A[high] = A[low];}A[low] = pivot;return low;}}

（3） 快速排序非递归方式实现：

public class QuickSortNonRecursion {public static void main(String[] args) {int A[] = { 1, 5, 8, 2, 4, 6, 3, 7, 9, 0 };int low = 0;int high = A.length - 1;nonRec_quickSort(A, low, high);for (int i = 0; i < A.length; i++) {System.out.print(A[i] + " ");}}public static void nonRec_quickSort(int[] a, int start, int end) {Stack<Integer> stack = new Stack<>();if (start < end) {stack.push(end);stack.push(start);while (!stack.isEmpty()) {int l = stack.pop();int r = stack.pop();int index = partition(a, l, r);if (l < index - 1) {stack.push(index - 1);stack.push(l);}if (r > index + 1) {stack.push(r);stack.push(index + 1);}}}System.out.println(Arrays.toString(a));}public static int partition(int[] a, int start, int end) {int pivot = a[start];while (start < end) {while (start < end && a[end] >= pivot)end--;a[start] = a[end];while (start < end && a[start] <= pivot)start++;a[end] = a[start];}a[start] = pivot;return start;}}

（4） 堆排序：

核心代码：

public class HeapSort {public static void main(String[] args) {int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };System.out.println("Before heap:");ArrayUtils.printArray(array);heapSort(array);System.out.println("After heap sort:");ArrayUtils.printArray(array);}public static void heapSort(int[] array) {if (array == null || array.length <= 1)return;buildMaxHeap(array);for (int i = array.length - 1; i >= 1; i--) {ArrayUtils.exchangeElements(array, 0, i);maxHeap(array, i, 0);}}private static void buildMaxHeap(int[] array) {if (array == null || array.length <= 1) {return;}int half = array.length / 2;for (int i = half; i >= 0; i--) {maxHeap(array, array.length, i);}}private static void maxHeap(int[] array, int heapSize, int index) {int left = index * 2 + 1;int right = index * 2 + 2;int largest = index;if (left < heapSize && array[left] > array[index]) {largest = left;}if (right < heapSize && array[right] > array[largest]) {largest = right;}if (index != largest) {ArrayUtils.exchangeElements(array, index, largest);maxHeap(array, heapSize, largest);}}}

工具类：

public class ArrayUtils {public static void printArray(int[] array) {System.out.print("{");for (int i = 0; i < array.length; i++) {System.out.print(array[i]);if (i < array.length - 1) {System.out.print(",");}}System.out.println("}");}public static void exchangeElements(int[] array, int index1, int index2) {int temp = array[index1];array[index1] = array[index2];array[index2] = temp;}}

测试例及运行结果：

（1） 冒泡排序：
{10,9,8,7,6,5,4,3,2,1} ==> {1,2,3,4,5,6,7,8,9,10}
{1,5,8,2,4,6,3,7,9,0} ==> {0,1,2,3,4,5,6,7,8,9}
（2） 快速排序（递归与非递归测试例相同）：
{10,9,8,7,6,5,4,3,2,1} ==> {1,2,3,4,5,6,7,8,9,10}
{1,5,8,2,4,6,3,7,9,0} ==> {0,1,2,3,4,5,6,7,8,9}
（3） 堆排序：
Before heap:
{9,8,7,6,5,4,3,2,1,0,-1,-2,-3}
After heap sort:
{-3,-2,-1,0,1,2,3,4,5,6,7,8,9}

分析：

（1） 冒泡排序：
最好情况：对象的初始排列是按关键码从小到大排好序时，此算法只执行一次冒泡排序，做n-1次的关键码比较，不需要移动对象。
最坏情况：算法执行了n-1次冒泡，第i次（1<=i<=n）做了n-i次关键码比较，执行了n-i次对象交换。因此这种情况下，总的关键码比较次数KCN和对象移动次数RMN为：

空间复杂度：需要一个附加对象以实现对象值的对换。
冒泡排序是一个稳定的排序算法。
（2） 快速排序（递归）：
快速排序的趟数取决于递归树的深度。

最理想情况下时间复杂度分析：每次划分后，该对象的左右两侧的子序列长度相同。总的时间复杂度T(n)= o(n log2n )
最坏情况下时间复杂度分析：每次划分后，有一个子序列是空的，此时T(n)=O(n2)
平均情况：T(n)= o(n log2n )

最好情况下空间复杂度分析：由于算法是递归的，需要一个栈存放每层递归调用时的指针和参数。递归的深度就是树的深度，因此此时的存储开销为o(log2n)。
最坏情况下空间复杂度分析：此时递归树为单支树，存储开销为o(n)。

快速排序是不稳定的排序算法。
（3） 快速排序（非递归）：
该算法对比递归算法，它使用的栈是我们自己创建的栈。而递归方法使用的是程序自动产生的栈，栈中包含了函数调用时的参数和函数中的局部变量。如果局部变量很多或者函数内部有调用了其他函数，这样一来，栈就会变得很大，每次递归调用都要操作很大的栈，效率自然会下降。而我们自己创建的栈，不管程序的复杂度如何，都不会影响程序的效率。
该算法的平均情况的时间复杂度仍是o(n log2n )。
（4） 堆排序：
时间复杂度分析：初始化大顶堆过程每个非叶节点都用到了调整过程的算法，因此该层循环所用时间为：

n 其中，i 是层序号，2i 是第 i 层的最大结点数，(k-i-1)是第 i 层结点能够 移动的最大距离。
化简后：

调整循环过程：该循环的计算时间为O(nlog2n)。所以，堆排序的时间复杂度为O(nlog2n)。
空间复杂度分析：附加存储主要在调整过程中占用，执行交换需要使用一个临时存储空间，因此空间复杂度为O(1)。
堆排序是一个不稳定的排序算法。

以上是作业的主要内容，如果有不正确或者有异议的地方，还希望大家不吝指正。