堆排序:
对于堆排序来说,整个步骤还是比较繁琐,首先我们需要先进行建堆操作,从小到大就建大堆,从大到小就建小堆,建堆操作涉及到向下调整的过程,然后我们需要堆顶元素和数组最后一个元素进行交换,然后再进行从索引为0的位置向下调整,从而达到排序的效果。
1)建堆:
这里我们建大堆
public void createHeap(int[] array) {
for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
adjust(i, array.length - 1, array);
}
}
private void adjust(int parent, int useSize, int[] array) {
int child = parent * 2 + 1;
while (child < useSize) {
if (child + 1 < useSize && array[child + 1] > array[child]) {
child = child + 1;
}
if (array[child] > array[parent]) {
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
2)进行原地堆排序:
public void heapSort(int[] array) {
createHeap(array);
int end = array.length - 1;
while (end > 0) {
int tmp = array[0];
array[0] = array[end];
array[end] = tmp;
adjust(0, end, array);
end--;
}
}
为什么堆排序的时间复杂度是nlogN呢?
因为堆的底层是一棵完全二叉树,logN就代表树的深度,n代表进行排序的有n个元素。
归并排序:
归并排序是一个时间复杂度NlogN且是一个稳定的排序算法。归并的核心是在于并这个过程,给你两个数组,让你合并成一个有序数组,这就是归并的核心。归并排序算法也是分治法的经典应用之一。
public int[] mergeArray(int[] array1, int[] array2) {
int[] arr = new int[array1.length + array2.length];
int bs = 0;
int be = array1.length - 1;
int as = 0;
int ae = array2.length - 1;
int i = 0;
while (bs <= be && as <= ae) {
if (array1[bs] < array2[as]) {
arr[i] = array1[bs];
bs++;
i++;
} else {
arr[i] = array2[as];
as++;
i++;
}
}
while (bs <= be) {
arr[i] = array1[bs];
bs++;
i++;
}
while (as <= ae) {
arr[i] = array2[as];
as++;
i++;
}
return arr;
}
当我们懂得了归并的核心并之后,我们需要对整个数组进行一次一次的拆分
进行拆分之后,我们可以就可以进行两个数组合并成一个有序数组的操作。
我们这里使用递归对整个数组进行区域划分。
public void mergeSort(int[] array, int begin, int end) {
if (begin >= end) {
return;
}
int mid = begin + ((end - begin) >>> 1);
mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, end, mid);
}
private void merge(int[] array, int begin, int end, int mid) {
int[] tmp = new int[end - begin + 1];
int bs = begin;
int be = mid;
int as = mid + 1;
int ae = end;
int i = 0;
while (bs <= be && as <= ae) {
if (array[bs] < array[as]) {
tmp[i++] = array[bs++];
} else {
tmp[i++] = array[as++];
}
}
while (bs <= be) {
tmp[i++] = array[bs++];
}
while (as <= ae) {
tmp[i++] = array[as++];
}
for (int j = 0; j < i; j++) {
array[j + begin] = tmp[j];
}
}
快速排序:
快速排序是一个效率非常高的排序算法,平均的时间复杂度为NlogN,但是在最差情况下的时间复杂度为O(n^2)。最差的情况我们等等再进行讨论。
快速排序也是利用了分治思想,把一个数组分成一个个区间进行处理,不同与归并,快排使用了基准这个概念,我们以第一个元素为基准,把小于等于这个基准的值放在左区间,把大于等于这个基准的值放在右区间。然后进行分治,最后达到排序的效果。
1)找基准:
private int partition(int[] array, int begin, int end) {
int tmp = array[begin];
while (begin < end) {
while (begin < end && array[end] >= tmp) {
end--;
}
array[begin] = array[end];
while (begin < end && array[begin] <= tmp) {
begin++;
}
array[end] = array[begin];
}
array[begin] = tmp;
return begin;
}
2)进行快速排序:
public void quickSort(int[] array, int begin, int end) {
if (begin >= end) {
return;
}
int mid = findMid(array, begin, end);
int pivot = partition(array, begin, end);
quickSort(array, begin, pivot - 1);
quickSort(array, pivot + 1, end);
}
刚刚我们提过的最差情况,那就是分治区间只有左区间或者只有右区间,这时候时间复杂度就高了,这时候我们有三数取中法和随机选择法进行优化。三数取中法,就是让第一个元素和最后一个元素和中间元素进行大小比较,然后让数值在中间的数和第一个元素进行交换,达到不会有单区间的情况发生
public int findMid(int[] array, int begin, int end) {
int mid = begin + ((end - begin) / 2);
if (array[begin] > array[end]) {
if (array[mid] > array[begin]) {
return begin;
} else if (array[mid] < array[end]) {
return end;
} else {
return mid;
}
} else {
if (array[mid] < array[begin]) {
return begin;
} else if (array[mid] > array[end]) {
return end;
} else {
return mid;
}
}
}
然后我们在快速排序的过程中可以进行优化处理:
public void quickSort(int[] array, int begin, int end) {
if (begin >= end) {
return;
}
int mid = findMid(array, begin, end);
int tmp = array[begin];
array[begin] = array[mid];
array[mid] = tmp;
int pivot = partition(array, begin, end);
quickSort(array, begin, pivot - 1);
quickSort(array, pivot + 1, end);
}


