package DataStrcuture;
import java.util.Arrays;
/**
* @Author: JackYe
* @CreateDate: 2019/5/22 15:53
* @Description: java中的排序方法
* @Version: 1.0
*/
public class JavaSort {
public static void main(String[] args) {
int[] a = new int[]{5, 11, 8, 4, 5, 6, 7, 8, 9, 0};
myMinHeapSort(a);
System.out.println(Arrays.toString(a));
}
//选择排序
public static void selectSort(int[] a) {
/*
* @params [a]
* @return void
* @author jackye
* @date 2019/5/22 16:22
* @description: 选择排序 记录最小的位置即可
*/
if (a == null || a.length == 0) {
return;
}
int length = a.length;
for (int i = 0; i < length; i++) {
int minIndex = i;
for (int j = i + 1; j < length; j++) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
//插入排序
public static void insertSort(int[] a) {
if (a == null || a.length == 0) {
return;
}
int length = a.length;
for (int i = 1; i < length; i++) {
int j = i;
while (j >= 1 && a[j] < a[j - 1]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
j--;
}
}
}
//冒泡排序
public static void bubbleSort(int[] a) {
if (a == null || a.length == 0) {
return;
}
int length = a.length;
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
//希尔排序 插入排序升级版 间隔k个的插入排序，最后K=1;
public static void shellSort(int[] a) {
if (a == null || a.length == 0) {
return;
}
int length = a.length;
for (int h = length / 2; h > 0; h = h / 2) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h; j = j - h) {
if (a[j] < a[j - h]) {
int temp = a[j];
a[j] = a[j - h];
a[j - h] = temp;
}
}
}
}
}
//快速排序 前后两队，前小后大()
public static void quickSort(int[] a) {
if (a == null || a.length == 0) {
return;
}
sortSoultion(a, 0, a.length - 1);
}
private static void sortSoultion(int[] a, int low, int high) {
if (low >= high) {
return;
}
int i = low;
int j = high;
int index = a[low];
while (i < j) {
while (i < j && a[j] >= index) {
j--;
}
if (i < j && a[j] < index) {
a[i] = a[j];
i++;
}
while (i < j && a[i] <= index) {
i++;
}
if (i < j && a[i] > index) {
a[j] = a[i];
j--;
}
}
a[i] = index;
sortSoultion(a, low, i - 1);
sortSoultion(a, i + 1, high);
}
//归并排序 先打散，再重排
public static void mergeSort(int a[], int start, int end) {
if (a == null || a.length == 0) {
return;
}
if (start >= end) {
return;
}
int mid = (start + end) >> 1;
mergeSort(a, start, mid);
mergeSort(a, mid + 1, end);
mergeCore(a, start, mid, end);//开始合并
}
private static void mergeCore(int[] a, int start, int mid, int end) {
if (start >= end) {
return;
}
int[] tempArrays = new int[end - start + 1];
int i = start;
int j = mid + 1;
int pos = 0;
while (i <= mid && j <= end) {
if (a[i] < a[j]) {
tempArrays[pos++] = a[i++];
} else {
tempArrays[pos++] = a[j++];
}
}
while (i <= mid) {
tempArrays[pos++] = a[i++];
}
while (j <= end) {
tempArrays[pos++] = a[j++];
}
for (int g = 0; g < pos; g++) {
a[start + g] = tempArrays[g];
}
}
//堆排序 通过构建最大顶堆 得到最大的值(堆顶)，然后堆顶不断的和堆底的元素交换位置，刷新，产生新的堆顶(次小值)
public static void myMinHeapSort(int[] a) {
int len = a.length;
for (int i = len / 2 - 1; i >= 0; i--) {
adjustMinHeap(a, i, len - 1);
}
for (int i = len - 1; i >= 0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
//得到i-1个节点的顶堆
adjustMinHeap(a, 0, i - 1);
}
}
private static void adjustMinHeap(int[] a, int parent, int len) {
//左孩子
int child = 2 * parent + 1;
while (child <= len) {
//比较左右孩子，取出最大
if (child + 1 < len && a[child] < a[child + 1]) {
child++;
}
// 与父亲交换彼此的值
if (a[child] > a[parent]) {
int temp = a[parent];
a[parent] = a[child];
a[child] = temp;
//child成为parent，继续迭代
parent = child;
child = 2 * child + 1;
} else {
break;
}
}
}
}
