package sort;
import java.util.Random;
public class Main {
static final int NUMS_SIZE = 10;
static final int RANDOM_MAX = 100;
static ISort sorter;
public static void main(String[] args) {
int[] nums = initNums();
show(nums);
// 交换排序
// sorter = new MaoPaoImpl();
// sorter = new KuaiPaiImpl();
// 插入排序
// sorter = new ZhiJieInsertImpl();
// sorter = new XiErImpl();
// 选择排序
// sorter = new SimpleChooseImpl();
// sorter = new HeapSortImpl();
// 归并排序
sorter = new GuibingImpl();
sorter.sort(nums);
show(nums);
}
private static int[] initNums() {
Random random = new Random();
int[] nums = new int[NUMS_SIZE];
for (int i = 0; i < NUMS_SIZE; i++) {
nums[i] = random.nextInt(RANDOM_MAX);
}
return nums;
}
public static void show(int[] nums) {
System.out.print("[");
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]);
if (i == nums.length - 1) {
System.out.print("]");
} else {
System.out.print(",");
}
}
System.out.println();
}
public static void changePosition(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
public static void insert(int[] nums, int from, int to, int step) {
int num = nums[from];
for (int i = from; i > to; i -= step) {
nums[i] = nums[i - step];
}
nums[to] = num;
}
}
package sort;
public class MaoPaoImpl implements ISort {
@Override
public void sort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
Main.changePosition(nums, j, j + 1);
}
}
}
}
}
package sort;
public class KuaiPaiImpl implements ISort {
@Override
public void sort(int[] nums) {
split(nums, 0, nums.length - 1);
}
void split(int[] nums, int left, int right) {
if (right - left <=0) {
return;
}
int index = left;
int i = left;
int j = right;
while (left < right) {
while (left < right && nums[index] <= nums[right]) {
right--;
}
Main.changePosition(nums, index, right);
index = right;
while (left < right && nums[index] >= nums[left]) {
left++;
}
Main.changePosition(nums, left, index);
index = left;
}
Main.show(nums);
split(nums, i, index-1);
split(nums, index+1, j);
}
}
package sort;
public class ZhiJieInsertImpl implements ISort {
@Override
public void sort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] < nums[j]) {
Main.insert(nums, i, j, 1);
break;
}
}
Main.show(nums);
}
}
}
package sort;
public class XiErImpl implements ISort {
@Override
public void sort(int[] nums) {
int step = nums.length / 2;
while (step != 0) {
System.out.println(step);
sort(nums, step);
step /= 2;
}
}
void sort(int[] nums, int step) {
for (int i = 0; i < step; i++) {
sort(nums, step, i);
Main.show(nums);
}
}
void sort(int[] nums, int step, int begin) {
for (int i = begin + step; i < nums.length; i += step) {
for (int j = begin; j < i; j += step) {
if (nums[i] < nums[j]) {
Main.insert(nums, i, j, step);
}
}
}
}
}
package sort;
public class SimpleChooseImpl implements ISort {
@Override
public void sort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int minIndex = findMin(nums, i);
Main.changePosition(nums, i, minIndex);
}
}
private int findMin(int[] nums, int begin) {
int min = begin;
for (int i = begin + 1; i < nums.length; i++) {
if (nums[i] < nums[min]) {
min = i;
}
}
return min;
}
}
package sort;
public class HeapSortImpl implements ISort {
@Override
public void sort(int[] nums) {
int index = nums.length - 1;
while (index != 0) {
buildHeap(nums, index);
Main.changePosition(nums, 0, index);
index--;
}
}
void buildHeap(int[] nums, int last) {
for (int i = last; i > 0; i--) {
if (i % 2 == 0) {
if (nums[i] > nums[(i - 1) / 2]) {
Main.changePosition(nums, i, (i - 1) / 2);
}
} else {
if (nums[i] > nums[i / 2]) {
Main.changePosition(nums, i, i / 2);
}
}
}
}
}
package sort;
public class GuibingImpl implements ISort {
@Override
public void sort(int[] nums) {
sort(nums, 0, nums.length - 1);
}
void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int middle = (left + right) / 2;
sort(nums, left, middle);
sort(nums, middle + 1, right);
merge(nums, left, middle, right);
}
private void merge(int[] nums, int left, int middle, int right) {
int[] tmp = new int[right - left + 1];
int tmp_index = 0;
int array1_left = left;
int array1_right = middle;
int array2_left = middle + 1;
int array2_right = right;
while (array1_left <= array1_right && array2_left <= array2_right) {
while (array1_left <= array1_right && nums[array1_left] < nums[array2_left]) {
tmp[tmp_index] = nums[array1_left];
tmp_index++;
array1_left++;
}
while (array2_left <= array2_right && nums[array2_left] < nums[array1_left]) {
tmp[tmp_index] = nums[array2_left];
tmp_index++;
array2_left++;
}
}
while (array2_left <= array2_right) {
tmp[tmp_index] = nums[array2_left];
tmp_index++;
array2_left++;
}
while (array1_left <= array1_right) {
tmp[tmp_index] = nums[array1_left];
tmp_index++;
array1_left++;
}
for (int i = left, j = 0; i <= right; i++, j++) {
nums[i] = tmp[j];
}
}
}
