package com.cy.demo;
import org.junit.Test;
import org.junit.platform.commons.util.StringUtils;
import java.util.Arrays;
public class 十大排序 {
//选择排序法
@Test
public void selectSort() {
int[] arr = new int[]{5, 2, 7, 8, 3, 9, 1, 4, 6, 0};
int temp;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
//冒泡排序法
@Test
public void MaoPao() {
int[] numbers = new int[]{5, 2, 7, 8, 3, 9, 1, 4, 6, 0};
int temp;
for (int j = 0; j < numbers.length - 1; j++) {
for (int i = 0; i < numbers.length - 1; i++) {
if (numbers[i] > numbers[i + 1]) {
temp = numbers[i];
numbers[i] = numbers[i + 1];
numbers[i + 1] = temp;
}
}
}
System.out.println(Arrays.toString(numbers));
}
@Test
public void quickSortmain() {
int[] numbers = new int[]{5, 2, 7, 8, 3, 9, 1, 4, 6, 0};
quickSort(numbers, 0, numbers.length - 1);
System.out.println(Arrays.toString(numbers));
}
//快速排序法
public void quickSort(int[] arr, int start, int end) {
if (start < end) {
int stard = arr[start];
int low = start;
int high = end;
while (low < high) {
while (low < high && arr[high] >= stard) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= stard) {
low++;
}
arr[high] = arr[low];
}
arr[low] = stard;
quickSort(arr, start, low);
quickSort(arr, low + 1, end);
}
}
//直接插入排序法
@Test
public void insertSort() {
int[] arr = new int[]{5, 2, 7, 8, 3, 9, 1, 4, 6, 0};
int temp;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] < arr[j]) {
temp = arr[i];
for (int k = i; k > j; k--) {
arr[k] = arr[k - 1];
}
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
//直接插入排序法
@Test
public void inserSort2() {
int[] arr = new int[]{5, 2, 7, 8, 3, 9, 1, 4, 6, 0};
int temp;
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
for (int k = 0; k < i; k++) {
if (arr[k] > arr[i]) {
temp = arr[i];
for (int j = i; j > k; j--) {
arr[j] = arr[j - 1];
}
arr[k] = temp;
}
}
}
}
System.out.println(Arrays.toString(arr));
}
//希尔排序(按步长分组进行直接插入排序)
@Test
public void shellSortMain() {
int[] arr = new int[]{5, 2, 7, 8, 3, 9, 1, 4, 6, 0};
int grap = arr.length / 2;
int temp;
int status = 0;
int first = 0;
int code = 0;
while (grap >= 1) {
for (int i = grap; i < arr.length; i++) {
if (i - grap >= 0) {
if (arr[i] < arr[i - grap]) {
if (i - 2 * grap >= 0) {
for (int k = i - 2 * grap; k >= 0; k = k - grap) {
if (arr[k] < arr[i]) {
status = 1;
temp = arr[i];
for (int n = i; n > k + grap; n = n - grap) {
arr[n] = arr[n - grap];
}
arr[k + grap] = temp;
break;
}
}
if (status == 0) {
temp = arr[i];
for (int h = i; h - grap >= 0; h = h - grap) {
arr[h] = arr[h - grap];
first = h - grap;
}
arr[first] = temp;
}
status = 0;
} else {
temp = arr[i];
arr[i] = arr[i - grap];
arr[i - grap] = temp;
}
}
}
}
grap = grap / 2;
}
System.out.println(Arrays.toString(arr));
}
//希尔排序(内部非插入排序)
@Test
public void shell2() {
int arr[] = new int[]{2, 5, 6, 8, 9, 7, 4, 3, 1, 0};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void shellSort(int arr[]) {
//遍历所有步长
for (int d = arr.length / 2; d > 0; d /= 2) {
//遍历所有的元素
for (int i = d; i < arr.length; i++) {
//如果当前数字比前d个数字小
if (arr[i] < arr[i - d]) {
//把当前数字存起来
int temp = arr[i];
int j;
for (j = i - d; j >= 0; j -= d) {
if (arr[j] > temp) {
arr[j + d] = arr[j];
} else {
break;
}
}
arr[j + d] = temp;
}
}
}
}
//归并排序（分治法）
@Test
public void mergSortMain() {
int[] arr = new int[]{1, 5, 2, 7, 4, 6, 3, 9};
mergSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public void mergSort(int[] arr, int start, int end) {
int middle = (start + end) / 2;
if (start < end) {
mergSort(arr, start, middle);
mergSort(arr, middle + 1, end);
merg1(arr, start, middle, end);
}
// merg(arr, start, middle, end);
}
public void merg1(int[] arr, int start, int middle, int end) {
int[] linshi = new int[end - start + 1];
int linshimark = 0;
int mark1 = start;
int mark2 = middle + 1;
for (int k = 0; k < linshi.length; k++) {
if (mark1 <= middle && mark2 <= end) {
if (arr[mark1] <= arr[mark2]) {
linshi[linshimark] = arr[mark1];
linshimark++;
mark1++;
} else {
linshi[linshimark] = arr[mark2];
mark2++;
linshimark++;
}
} else if (mark1 > middle) {
for (int i = mark2; i <= end; i++) {
linshi[linshimark] = arr[i];
linshimark++;
}
break;
} else {
for (int i = mark1; i <= middle; i++) {
linshi[linshimark] = arr[i];
linshimark++;
}
break;
}
}
for (int d = 0; d < linshi.length; d++) {
arr[d + start] = linshi[d];
}
}
public void merg2(int[] arr, int start, int middle, int end) {
int[] temp = new int[end - start + 1];
int i = start;
int j = middle + 1;
int index = 0;
while (i <= middle && j <= end) {
if (arr[i] <= arr[j]) {
temp[index] = arr[i];
index++;
i++;
} else {
temp[index] = arr[j];
index++;
j++;
}
}
if (i <= middle) {
for (int k = i; k <= middle; k++) {
temp[index] = arr[i];
i++;
index++;
}
}
if (j <= end) {
for (int k = j; k <= end; k++) {
temp[index] = arr[j];
j++;
index++;
}
}
for (int k = 0; k < temp.length; k++) {
arr[start + k] = temp[k];
}
}
//基数排序
@Test
public void radisSort(){
int[] arr = new int[]{1, 5, 2, 7, 4, 6, 3, 9,12,34,23,234,56,94,33,54,111,345};
int max = arr[0];
int[][] numbers = new int[10][arr.length];
int[] indexs = new int[]{0,0,0,0,0,0,0,0,0,0};
int temp=0;
int index2;
for(int q = 0;q<10;q++){
numbers[q]=new int[arr.length];
}
for (int i=1;i
