归并排序、快速排序、桶排序---Java实现(带注释)
程序员文章站
2022-05-13 20:02:57
...
归并排序:
package sort;
/**
* Created by Hollake on 2019\5\26 0026.
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
MergeSort.mergeSort(arr);
printArr(arr);
}
// 归并时间复杂度O(N*logN),额外空间复杂度O(N),稳定
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <2) return;
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int l, int r) {
// 如果左边界小于右边界执行,否则返回
if (l < r) {
int mid = (l + r) / 2;
// 采用分治
mergeSort(arr, 0, mid);
mergeSort(arr, mid + 1, r);
// 将左右排好序的数组重新排好序
merge(arr, l, mid, r);
}
}
private static void merge(int[] arr, int l, int mid, int r) {
// 创建一个新数组
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = mid + 1;
// 只有arr数组的l到mid以及mid到r都没越界的时候执行
while ( p1 <= mid && p2 <= r ) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
// 执行到这里说明arr数组的mid到r已经拷贝完了,接着直接拷贝l到mid的所有数
while ( p1 <= mid ) {
help[i++] = arr[p1++];
}
// 执行到这里说明arr数组的l到mid已经拷贝完了,接着直接拷贝mid到r的所有数
while ( p2 <= r ) {
help[i++] = arr[p2++];
}
// 将所有数重新拷贝回arr[l---r]
for (int j = 0; j < help.length; j++) {
arr[l + j] = help[j];
}
}
private static void printArr(int[] arr) {
for (int i: arr){
System.out.print(i+",");
}
}
}
快速排序:
package sort;
/**
* Created by Hollake on 2019\5\29 0029.
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
QuickSort.quickSort(arr);
printArr(arr);
}
// 快排时间复杂度O(N*logN),额外空间复杂度O(logN),不稳定
private static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length-1);
}
private static void quickSort(int[] arr, int l, int r) {
// 快排递归执行条件
if (l < r) {
// 将数组最后一个数arr[r]作为判断对象,小于它的放左边,大于它的放右边,
// 返回数组中等于arr[r]的起始位置,p数组只包含起始这两个值。例如数组为[12,3,4,6,8,6]
// ,partation 后的数组为[3,4,6,6,12,8],返回的p = [2,3]
int[] p = partation(arr, l, r);
// 递归,按照中间数的起始位置将数组分治
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
private static int[] partation(int[] arr, int l, int r) {
// less表示数组小于arr[r]的下标,第一次从-1开始,只要小于arr[r],
// 那么就less++,
int less = l - 1;
// less表示数组大于arr[r]的下标,第一次从r开始,只要大于arr[r],
// 那么就more--,注意,其实需要判断的是从l---r-1的数,因为r的数是作为被比较的数的
int more = r;
// 当左下标小于右下标的时候循环
while ( l < more ) {
// 判断l位置元素是否小于arr[i],如果小于那么将l位置和左下标也就是less加1后交换,
// 其实大部分时间,也就是没有碰到和arr[i]相等的元素,并没有进行交换,因为less+1就是l
if (arr[l] < arr[r]) {
swap(arr, l++, ++less);
// 如果大于,那么将--more位置的元素交换到l位置,但是l不会++,这是因为换过来的数还得重新进行判断
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
// 如果碰到等于arr[i]的数,l++
l++;
}
}
// 最后将r位置的数交换到more位置,因为用的是arr[r]的数进行比较,所以最终需要将这个和more位置交换
swap(arr, r, more);
return new int[]{less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static void printArr(int[] arr) {
for (int i: arr){
System.out.print(i+",");
}
}
}
桶排序:
package sort;
/**
* Created by Hollake on 2019\5\30 0030.
*/
public class HeapSort {
public static void main(String[] args) {
// int[] arr = {2, 4, 6, 9, 3, 6, 4, 86, 3, 2, 4};
int[] arr = {4,3,4};
HeapSort.heapSort(arr);
printArr(arr);
}
// 堆排时间复杂度O(N*logN),额外空间复杂度O(1),不稳定
private static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 从第一个数开始遍历,让数组变为大根堆(大根堆是完全二叉树)
for (int i = 0; i < arr.length; i++) {
// 每次堆的容量扩大1,进行大根堆转变
heapInsert(arr, i);
}
int heapSize = arr.length;
while ( heapSize > 0 ) {
// 将大根堆第一个数也就是数组第一个数(大根堆中最大的数)和大根堆最后一个数交换位置,然后大根堆大小减一
swap(arr, 0, --heapSize);
// 让交互到0位置喜爱那个对较小的数下沉,继续形成大根堆。
heapify(arr, 0, heapSize);
}
}
private static void heapify(int[] arr, int index, int heapSize) {
// 大根堆父节点的左叶子结点
int left = index * 2 + 1;
// 判断左儿子是否越界
while ( left < heapSize ) {
// 判断父节点的左儿子在没有越界的情况下谁最大,拿到数组下标,
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
// 判断左右儿子中最大值和父节点谁最大,拿到最大值下标
largest = arr[index] > arr[largest] ? index : largest;
if (largest == index) {
break;
}
// 交换父节点和左右儿子中的最大值
swap(arr, largest, index);
// 将左右儿子最大值下标赋给父节点
index = largest;
// 赋值后父节点的左儿子
left = index * 2 + 1;
}
}
private static void heapInsert(int[] arr, int index) {
// 当index位置的这个值大于它的父节点的时候需要上浮,最终形成大根堆
while ( arr[index] > arr[(index - 1) / 2] ) {
// 如果大于交换位置
swap(arr, index, (index - 1) / 2);
// 更新节点,把父节点更新为当前节点,继续循环
index = (index - 1) / 2;
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static void printArr(int[] arr) {
for (int i: arr){
System.out.print(i+",");
}
}
}