# Java综合整理堆排序 快速排序 归并排序

## 堆排序

• 时间复杂度：0（N*log(N)）
• 空间复杂度：0（1）
• 稳定性：不稳定
```private static void heapSort(int[] arr) {
//建堆
crearHeap(arr);
for (int i = 0; i < arr.length-1; i++) {
int heapSize=arr.length-i;
swap(arr,heapSize-1,0);
heapSize--;
shiftDown(arr,heapSize,0);
}
System.out.println(Arrays.toString(arr));
}

private static void crearHeap(int[] arr) {
// 从后往前遍历(右边非叶子节点开始), 依次进行向下调整
for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
shiftDown(arr,arr.length,i);
}

}
//向下调整，形成大堆
private static void shiftDown(int[] arr, int size, int i) {
int parent = i;
int child = parent*2+1;
while (child arr[child]){
child=child+1;
}
if (arr[child]>arr[parent]){
swap(arr,child,parent);
}else {
break;
}
parent=child;
child=parent*2+1;
}
}
//交换
private static void swap(int[] arr, int child, int parent) {
int tmp =arr[child];
arr[child] =arr[parent];
arr[parent]=tmp;
}
```

## 快速排序

• 时间复杂度:O(N^ logN) 最坏的时候O(N^2) 和基准值密切相关
• 空间复杂度:0(logN) 最坏的时候O(N)
• 稳定性:不稳定

### 递归

```private static void quick(int[] arr) {
quickSortHelper(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}

private static void quickSortHelper(int[] arr, int left, int right) {
if (left>=right){
//区间只有一个元素，或者零个元素
return;
}
int index = partition(arr,left,right);
quickSortHelper(arr,left,index-1);
quickSortHelper(arr,index+1,right);
}

private static int partition(int[] arr, int left, int right) {
int i=left;
int j=right;
int baseValue=arr[right];
while (i=baseValue){
j--;
}
if (i
```

### 非递归

```public static void quickSortByLoop(int[] arr) {
Stack stack =new Stack<>();
stack.push(0);
stack.push(arr.length-1);
while (!stack.isEmpty()){
int right = stack.pop();
int left = stack.pop();
if (left>=right){
continue;
}
int index = partition(arr,left,right);
//右子树
stack.push(index+1);
stack.push(right);
//左子树
stack.push(left);
stack.push(index-1);
}
System.out.println(Arrays.toString(arr));
}

private static int partition(int[] arr, int left, int right) {
int baseValue =arr[right];
int i =left;
int j =right;
while (i=baseValue){
j--;
}
if (i
```

## 归并排序

• 时间复杂度:O(NlogN)
• 空间复杂度:O(N） 如果是链表，可以为O(1)
• 稳定性:稳定

### 递归

```public static void mergeSort(int[] arr){
mergeSortHelper(arr,0,arr.length);
System.out.println(Arrays.toString(arr));
}

private static void mergeSortHelper(int[] arr, int left, int right) {
if (right-left<=1){
return;
}
int mid = (right+left)/2;

mergeSortHelper(arr,left,mid);
mergeSortHelper(arr,mid,right);
merge(arr,left,mid,right);
}

private static void merge(int[] arr, int left, int mid, int right) {
int cur1 =left;
int cur2 =mid;
//两个数组合并后的结果
int[] output=new int[right-left];
int outputIndex=0;

while (cur1
```

### 非递归

```public static void mergeSortByLoop(int[] arr){
// gap 当前每个组中的元素个数.
for (int gap =1;gap arr.length){
mid =arr.length;
}
if (right>arr.length){
right=arr.length;
}
merge(arr,left,mid,right);
}
}
System.out.println(Arrays.toString(arr));
}
```