import com.sun.deploy.security.SelectableSecurityManager;
import java.util.Arrays;
public class Orders {
/**
* 冒泡排序
* 冒泡排序的思路以从小往大排序来看，从头往后，如果相邻的元素后面的比前面的大
* 那么交换位置，这样一轮下来最后一个元素就是最大的，归位成功。最大的前面的最大的也是这样来的
*/
static void bubbleSort(int[] arr) {
for(int i=0; i<arr.length-1; i++) {
for(int j=1; j<arr.length-i; j++) {
if(arr[j-1]>arr[j]) {
int tmp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = tmp;
}
}
}
}
/**
* 直接选择排序
* 直接选择排序可能最好理解，就是找到第i小，将第i小与i位置处的元素交换位置
*/
static void selectSort(int[] arr) {
for(int i=0; i<arr.length; i++) {
int min = arr[i];
int flag = i;
for(int j=i+1; j<arr.length; j++) {
if(min>arr[j]) {
min = arr[j];
flag = j;
}
}
// 将第i小和找到的第i小交换位置
int tmp = arr[flag];
arr[flag] = arr[i];
arr[i] = tmp;
}
}
/**
* 插入排序
* 插入排序的基本思路是让前i个元素有序，之后将后面的元素与前面的元素比较，
* 遇到第一个比该元素大的，那么后面的都比他大，需要将该元素插在第一个比他大的
* 前面
*/
static void insertSort(int[] arr) {
for(int i=1; i<arr.length; i++) {
for(int j=0; j<i; j++) {
if(arr[i]<arr[j]) {
int tmp = arr[i];
for(int k=i; k>j; k--) {
arr[k] = arr[k-1];
}
arr[j] = tmp;
}
}
}
}
/**
* 希尔排序
* 希尔排序是对插入排序的优化,通过设置步长，先让数组基本有序，每次遍历完后步长减半，再来一次
* 最后步长为1，就是插入排序了。
*
* !!!attention 希尔排序设置哨兵位，大家的输入用例需要将arr[0]空下来
* 例 [0,19,11,15,3,87,11,99,21,35]
* 当然希尔排序也可以不设置哨兵位
*/
static void shellSort(int[] arr) {
int itl = (arr.length-1)/2; // 步长
while(itl>=1) {
for(int i=itl+1; i<arr.length; i+=1) {
int j=i-itl;
arr[0] = arr[i]; // 设置哨兵
while(j>0 && arr[0]<arr[j]) {
arr[j+itl] = arr[j];
j-=itl;
}
arr[j+itl] = arr[0];
}
itl/=2;
}
}
/**
* 快速排序
* 快速排序的思路就是每一次找到一个元素的位置，该元素前面的元素都比它小，后面的元素都比它大，
* 从而将一个数组拆成两部分，之后的两部分和刚刚被拆的数组的求解方式一致但无关联。
*
* 关于参数front为要排数组的第一个元素位置
* rear为最后元素一个位置
*/
static void quickSort(int[] arr, int front, int rear) {
if(front>=rear) {
return;
}
int i = front;
int j = rear+1;
int sentinel = arr[front];
while(true) {
while(sentinel>arr[++i] && i<rear);
while(sentinel<arr[--j]);
if(i<j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
} else {
break;
}
}
arr[front] = arr[j];
arr[j] = sentinel;
quickSort(arr, front, j-1);
quickSort(arr, j+1, rear);
}
/**
* 合并排序
* 合并排序的思想就是将数组先不断地划分，最后划分为长度为2的数组后再进行合并排序
*/
static void mergeSort(int[] arr, int front, int rear) {
if(front<rear) {
int mid = (front+rear)/2;
mergeSort(arr, front, mid);
mergeSort(arr, mid+1, rear);
merge(arr, front, mid, rear);
for(int i=front; i<=rear; i++) {
arr[i] = sup[i];
}
}
}
static int[] sup = new int[100]; //为辅助数组，长度可以根据自己要排数组长度改变。
static void merge(int[] arr, int front, int mid, int rear) {
int i = front;
int j = mid + 1;
int k = front;
while (i <= mid && j <= rear) {
if (arr[i] < arr[j]) {
sup[k++] = arr[i++];
} else {
sup[k++] = arr[j++];
}
}
if (j>rear)
for (int m = i; m <= mid; m++) {
sup[k++] = arr[m];
}
else
for (int m = j; m <= rear; m++) {
sup[k++] = arr[m];
}
}
/**
* 最后讲一下堆排序
* 要说堆排序其实才是效率最高的，但是堆这个数据结构比较复杂，我暂时不想实现，简单讲一下思路吧
* 堆有最大堆和最小堆，我们以最大堆为例讲一下从小到大的排序好了
* 最大堆的最上面的根节点就是该结构的最大值，取出来放到数组末尾，之后变换堆，变换后的堆的顶部又是最大值
* 至于怎么变换堆，这儿一两句话讲不清
* 下面给大家一本书《我的第一本算法书》，该书的的第一章第七小结有详细解释，我怕我讲的不好，
* 推荐大家去看那本书吧，图文并茂很详细，极力推荐。
*/
public static void main(String[] args) {
int[] arr = { 19,11,15,3,87,11,99,21,35 };
mergeSort(arr,0, 8);
Arrays.stream(arr).forEach(t-> System.out.print(t+" "));
System.out.println();
}
}
