package com.binggle.learn.learn.sort;
import com.alibaba.fastjson.JSONObject;
public class SortTest {
private static Integer[] arr = new Integer[]{1, 7, 3, 10, 20, 9, 8, 0, 13};
private static int findPartition(Integer[] arr, int low, int high) {
Integer sentry = arr[low];
while(low < high) {
while (low < high && arr[high] >= sentry) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= sentry) {
low++;
}
arr[high] = arr[low];
}
arr[low] = sentry;
return low;
}
private static void fastSort(Integer[] arr, int low, int high) {
if (low >= high) {
return;
}
int partition = findPartition(arr, low, high);
fastSort(arr, low, partition - 1);
fastSort(arr, partition + 1, high);
}
private static void simpleInsertSort(Integer[] arr) {
int i, j;
for(i = 1; i < arr.length; i++) {
int current = arr[i];
for(j = i - 1; j >= 0; j--) {
if (current < arr[j]) {
arr[j+1] = arr[j];
} else {
break;
}
}
arr[j + 1] = current;
}
}
private static void simpleSelectedSort(Integer[] arr) {
for(int i = 0 ; i < arr.length - 1; i++) {
int index = i;
for(int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[index]) {
index = j;
}
}
int tmp = arr[i];
arr[i] = arr[index];
arr[index] = tmp;
}
}
private static void bubbleSort(Integer[] arr) {
int i, j;
boolean flag = true;
for(i = 0; i < arr.length - 1; i++) {
for(j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
flag = false;
}
}
if (flag) {
break;
}
}
}
private static void shellSort(Integer[] arr) {
int i,j;
for(int gap = arr.length / 2; gap > 0; gap = gap / 2) {
for(i = gap; i < arr.length; i++) {
int current = arr[i];
for(j = i - gap; j >= 0 && current < arr[j]; j = j - gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = current;
}
}
}
private static void merge(Integer[] arr, int start1, int end1, int start2, int end2) {
int i = 0;
int j = 0;
int k = 0;
int arr1Length = end1 - start1 + 1;
int arr2Length = end2 - start2 + 1;
Integer[] target = new Integer[arr1Length + arr2Length];
while(i < arr1Length && j < arr2Length) {
if (arr[start1 + i] < arr[start2 + j]) {
target[k++] = arr[start1 + i] ;
i++;
} else {
target[k++] = arr[start2 + j] ;
j++;
}
}
while(i < arr1Length) {
target[k++] = arr[start1 + i++];
}
while(j < arr2Length) {
target[k++] = arr[start2 + j++];
}
for(i = 0; i < k; i++) {
arr[start1 + i] = target[i];
}
}
private static void mergeSort(Integer[] arr, int start, int end) {
if (start < end) {
int middle = (start + end) / 2;
mergeSort(arr, start, middle);
mergeSort(arr, middle + 1, end);
merge(arr, start, middle, middle + 1, end);
}
}
private static void adjustHead(Integer[] arr, int start, int length) {
for(int i = 0; i < length / 2; i++) {
int maxChildIndex = 2 * i;
if (maxChildIndex + 1 < length) {
maxChildIndex = arr[maxChildIndex] > arr[maxChildIndex + 1] ? maxChildIndex : maxChildIndex + 1;
}
if (arr[i] < arr[maxChildIndex]) {
int temp = arr[maxChildIndex];
arr[maxChildIndex] = arr[i];
arr[i] = temp;
}
}
}
private static void heapSort(Integer[] arr) {
for(int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHead(arr, i, arr.length);
}
for(int i = arr.length - 1; i > 0; i--) {
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
adjustHead(arr, 0, i);
}
}
public static void main(String[] args) {
fastSort(arr, 0 , arr.length - 1);
simpleInsertSort(arr);
simpleSelectedSort(arr);
bubbleSort(arr);
shellSort(arr);
mergeSort(arr, 0, arr.length - 1);
heapSort(arr);
System.out.println("sort result : " + JSONObject.toJSONString(arr));
}
}