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;
}
}
网友评论