package Algorithm.sort;

import com.alibaba.fastjson.JSON;

import com.alibaba.fastjson.JSONObject;

import org.json.JSONArray;

import org.jsoup.Connection;

import org.jsoup.Jsoup;

import org.jsoup.nodes.Document;

import org.jsoup.nodes.Element;

import org.jsoup.select.Elements;

import java.io.IOException;

import java.util.ArrayList;

import java.util.List;

import static Algorithm.selection.Selection3.swap;

/**

* Created by lenovo on 2017/3/23.

*/

public class Sort {

public static void main(String[] args) throws IOException {

int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10, 11};

// quicksort(a,0,a.length-1);

int[] temArr = new int[arr.length];

mergesort(arr, temArr, 0, arr.length - 1);

for (int i = 0; i < arr.length; i++) {

System.out.print(arr[i] + ",");

}

}

private static void mergesort(int[] arr, int[] tempArr, int left, int right) {

if (left >= right)

return;

int mid = (left + right) / 2;

mergesort(arr, tempArr, left, mid);

mergesort(arr, tempArr, mid + 1, right);

merge(arr, tempArr, left, right, mid);

}

private static void merge(int[] arr, int[] tempArr, int left, int right, int mid) {

for (int i = left; i <= right; i++) {

tempArr[i] = arr[i];

}

int cursor = left;

int index1 = left;

int index2 = mid + 1;

while (index1 <= mid && index2 <= right) {

if (tempArr[index1] <= tempArr[index2]) {

arr[cursor++] = tempArr[index1++];

} else {

arr[cursor++] = tempArr[index2++];

}

}

while (index1 <= mid) {

arr[cursor++] = tempArr[index1++];

}

while (index2 <= right) {

arr[cursor++] = tempArr[index2++];

}

}

private static void quicksort(int[] arr, int left, int right) {

if (left >= right)

return;

int pivotIndex = (left + right) / 2;

swap(arr, pivotIndex, right);

pivotIndex = partition(arr, left, right);

quicksort(arr, left, pivotIndex - 1);

quicksort(arr, pivotIndex + 1, right);

}

private static int partition(int[] arr, int left, int right) {

int pivot = arr[right];

int l = left;

int r = right-1;

while (l <= r) {

while (l <= r && arr[l] <= pivot) {

++l;

}

while (l <= r && arr[r] >= pivot) {

--r;

}

if (l < r) {

swap(arr, l, r);

}

}

swap(arr, l, right);

return l;

}

}