归并排序，快速排序，堆排序实现及时间、空间复杂度分析
1. 算法实现
排序中比较复杂的有归并排序，快速排序，堆排序三大算法了，三个算法的时间复杂度都是O(N * logN)，三个算法的思想我就简单的展开详述以下。
1.1 归并排序
归并排序的核心思想是链表中的经典题目：合并两个有序链表。
Leetcode P21: Merge Two Sorted Lists
采用分治的思想，将整个数组分为两个部分，先对左边的数组进行归并排序，再对右边的数组进行归并排序，最后两者进行merge。
下面的函数就是归并排序的归并部分，将两个已经有序的数组归并。
public class MergeSort implements Sort{
@Override
public void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
mergeSort(arr, 0, arr.length - 1);
}
public void mergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + ((r - l) >> 1);
//注意递归是i
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public void merge(int[] arr, int l, int mid, int r) {
int[] newArr = new int[r - l + 1];
int left = l;
int right = mid + 1;
int index = 0;
while (left <= mid && right <= r) {
if (arr[left] > arr[right]) {
newArr[index++] = arr[right++];
} else {
newArr[index++] = arr[left++];
}
}
while (left <= mid) {
newArr[index++] = arr[left++];
}
while (right <= r) {
newArr[index++] = arr[right++];
}
for (int i = 0; i < newArr.length; i++) {
arr[i + l] = newArr[i];
}
}
}
1.2 堆排序
堆排序首先就要利用堆这个数据结构。首先先将整个数组结构调整成堆。
heapInset函数插入某个数字，并且将插入的部分进行调整。对于一个数组，从位置0开始插入，并且边插入边进行调整。
public class HeapSort implements Sort{
@Override
public void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0) {
heapify(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
public void heapInsert(int[] arr, int index) {
//index > 0 的条件可以省略，因为如果index是1的话，两个值必定相等，无法进入循环
while (arr[(index - 1) / 2] < arr[index]) {
int fa = (index - 1) / 2;
swap(arr, index, fa);
index = fa;
}
}
public void heapify(int[]arr, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) {
int right = left + 1;
int maxLeftRightIndex = right < heapSize && arr[left] < arr[right] ? right : left;
int maxIndex = arr[maxLeftRightIndex] > arr[index] ? maxLeftRightIndex : index;
if (maxIndex == index) {
break;
}
swap(arr, index, maxIndex);
index = maxIndex;
left = maxIndex * 2 + 1;
}
}
public void swap(int []arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
这样处理完之后，数组就成为了一个最大堆。要将数组调整为有序的，要经历以下几步：
- 数组的第一个数是最大堆的顶，是最大的数，每次将第一个数和最大堆的最后一个数交换。这样后面部分就排好序了
- 交换完之后，最大堆的结构就会被破坏了，所以需要调整最大堆。
//交换到最后一个位置
swap(arr, 0, --heapSize);
while (heapSize > 0) {
//调整位置成最大堆
heapify(arr, 0, heapSize);
//之后再次进行交换
swap(arr, 0, --heapSize);
}
调整位置
public void heapify(int[]arr, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) {
int right = left + 1;
int maxLeftRightIndex = right < heapSize && arr[left] < arr[right] ? right : left;
int maxIndex = arr[maxLeftRightIndex] > arr[index] ? maxLeftRightIndex : index;
if (maxIndex == index) {
break;
}
swap(arr, index, maxIndex);
index = maxIndex;
left = maxIndex * 2 + 1;
}
}
1.3 快速排序
快速排序的核心思想思想是选一个数，不管是随机的还是固定的，每一步将大于这个数的数字放在数组的右边，小于的所有数字放在左边，听起来是不是很熟悉，这就是经典题目荷兰国旗的思想啦。
public class QuickSort implements Sort{
@Override
public void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int length = arr.length;
quickSort(arr, 0, length - 1);
}
public void quickSort(int[] arr, int l, int r) {
if (l >= r || l < 0) return;
int[] mids = partition(arr, l, r);
quickSort(arr, l, mids[0]);
quickSort(arr, mids[1], r);
}
public int[] partition(int arr[], int l, int r) {
int[] mids = new int[]{l ,r};
int num = arr[r];
int left = l - 1;
int right = r;
int cur = l;
while (cur < right) {
if (arr[cur] < num) {
swap(arr, ++left, cur++);
} else if (arr[cur] > num) {
swap(arr, --right, cur);
} else {
cur++;
}
}
swap(arr, right++, r);
mids[0] = left;
mids[1] = right;
return mids;
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = new int[]{4,1,2,3,4,3,1,4,1,1,23,4,5,4,2,2,3,5,3,1,1,2,3,4,5,6,7};
QuickSort q = new QuickSort();
q.sort(arr);
}
}
2. 时间复杂度分析
2.1 Master theorem
Master公式是为了评估递归函数的复杂度而诞生的。
T(N) = a* T(N / 2) + O(N^d)
-
log(b,a) > d时，时间复杂度是O(N ^ log(b,a)) - log(b,a) = d时，时间复杂度是
O(N ^ d + logN) - log(b,a) < d时，时间复杂度是
O(N^d)
2.2 算法复杂度分析
使用master公式计算三个排序的时间复杂度
2.2.1 归并排序
Merge-Sort的核心代码如下：
public void mergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + ((r - l) >> 1);
(1)part 1
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
(2)part 2
merge(arr, l, mid, r);
}
时间复杂度估算：
- part 1部分将问题分为两个部分，所以master中a=2,b=2。
- part 2部分是有序链表的合并，时间复杂度是：O(N)，所以d=1。
所以套用master公式中的第二条，时间复杂度是O(N*logN)
2.2.2 堆排序
Merge-Sort的核心代码如下：
public void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
(1)part1
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int heapSize = arr.length;
(2)part2
swap(arr, 0, --heapSize);
while (heapSize > 0) {
heapify(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
时间复杂度估算：
- 最大堆的插入后调整的时间复杂度是
O(logN)，part 1部分是插入N个元素，时间复杂度是log1+log2+log3+log4+...+logN = N，所以part 1的时间复杂度是O(N)。 - part 2部分中heapify的时间复杂度是logN，heapify就是堆的调整，所以part 2部分的时间复杂度是O(N * logN)
- 加起来就是O(N)+O(N*logN)，取最大项即为O(N*logN)
2.2.3 快速排序
Quick-Sort的核心代码如下：
public void quickSort(int[] arr, int l, int r) {
if (l >= r || l < 0) return;
(1)part 1
int[] mids = partition(arr, l, r);
(2)part 2
quickSort(arr, l, mids[0]);
quickSort(arr, mids[1], r);
}
时间复杂度估算：
- part 1中的partition思想是荷兰国旗问题，时间复杂度是O(N)。
- part 2和归并排序一样，也是将问题分为了两个部分，所以a=2，b=2。
所以快速排序的时间复杂度是O(N*logN)
2.2.4 空间复杂度
除了归并排序中，需要提前分配O(N)的空间，作为Merge过程中的缓存。堆排序和快速排序全部都是in-place修改的，所以不需要分配额外空间。
其实在在归并排序和堆排序过程中，因为函数递归，函数占用的栈地址也算空间复杂度，但是为什么没有算进去呢？个人认为是因为在一些高手的眼中，递归函数是可以改成循环，所以这就不用考虑这些额外空间了。
本文由博客一文多发平台 OpenWrite 发布！
版权声明：本文为strongchenyu原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。