import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// quickSort(arr, 0, arr.length-1);
// bubbleSort(arr);
// selectSort(arr);
// insertSort(arr);
shellSort(arr);
return arr;
}

// 希尔
public void shellSort(int[] arr) {
    int step = arr.length / 2;
    while (step >= 1) {
        for (int i=step; i < arr.length; i++) {
            for (int j=i; j >= step; j -= step) {
                if (arr[j] < arr[j-step]) {
                    swap(arr, j, j-step);
                } else {
                    break;
                }
            }
        }
        step /= 2;
    }
}

// 插入
public void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j;
        for (j=i-1;j>=0;j--) {
            if (arr[j] > key) {
                arr[j+1] = arr[j];
            } else {
                break;
            }
        }
        arr[j+1] = key;
    }
}

// 选择
public void selectSort(int[] arr) {
    for (int i = 0; i < arr.length -1; i++) {
        int min = arr[i];
        int minIndex = i;
        for (int j = i+1; j < arr.length; j ++) {
            if (arr[j] < min) {
                min = arr[j];
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

// 冒泡
public void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length-1; i++) {
        for (int j=0; j < arr.length-i-1;j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
            }
        }
    }
}

// 快排
public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int key = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= key) j--;
        while (i < j && arr[i] <= key) i++;
        if (i < j) swap(arr, i, j);
    }
    swap(arr, left, i);
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
}

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

}