packagebaseJava;/*** @title SortMethods.java
*@authorDonsenChen
* @Date 5月2日 上午10:16:03
* @Description*/
public classSortMethods {public static voidmain(String[] args) {int[] arr = { 3, 7, 9, 1, 4, 8, 2, 6, 5};
binarySort(arr);
bubbleSort(arr);
quickSort(arr,0, 0);
selectSort(arr);
insertSort(arr);
shellSort(arr);
mergeSort(arr,0, 0);
}//1. 二分法排序
public static void binarySort(int[] numbers) {inti, j, temp;intlow, hight, mid;for (i = 1; i < numbers.length; i++) {
temp=numbers[i];
low= 0;
hight= i - 1;while (low <=hight) {
mid= (low + hight) / 2;if (numbers[mid] >temp)
hight= mid - 1;elselow= mid + 1;
}for (j = i - 1; j > hight; j--)
numbers[j+ 1] =numbers[j];
numbers[hight+ 1] =temp;
}
System.out.print("二分法排序：");
printArr(numbers);
System.out.println();
}//2. 冒泡排序
public static void bubbleSort(int[] numbers) {int temp; //记录临时中间值
int size = numbers.length; //数组大小
for (int i = 0; i < size - 1; i++) {for (int j = i + 1; j < size; j++) {if (numbers[i] > numbers[j]) { //交换两数的位置(ps:这里的大于号小于号决定数组排序的升序或降序)
temp =numbers[i];
numbers[i]=numbers[j];
numbers[j]=temp;
}
}
}
System.out.print("冒泡排序：");
printArr(numbers);
System.out.println();
}//3. 快速排序
public static void quickSort(int[] numbers, int start, intend) {if (start
int temp; //记录临时中间值
int i = start, j =end;do{while ((numbers[i] < base) && (i
i++;while ((numbers[j] > base) && (j >start))
j--;if (i <=j) {
temp=numbers[i];
numbers[i]=numbers[j];
numbers[j]=temp;
i++;
j--;
}
}while (i <=j);if (start
quickSort(numbers, start, j);if (end >i)
quickSort(numbers, i, end);
}
System.out.print("快速排序：");
printArr(numbers);
System.out.println();
}//4. 选择排序
public static void selectSort(int[] numbers) {int size =numbers.length, temp;for (int i = 0; i < size; i++) {int k =i;for (int j = size - 1; j > i; j--) {if (numbers[j]
k=j;
}
temp=numbers[i];
numbers[i]=numbers[k];
numbers[k]=temp;
}
System.out.print("选择排序：");
printArr(numbers);
System.out.println();
}//5. 插入排序
public static void insertSort(int[] numbers) {int size =numbers.length, temp, j;for (int i = 1; i < size; i++) {
temp=numbers[i];for (j = i; j > 0 && temp < numbers[j - 1]; j--)
numbers[j]= numbers[j - 1];
numbers[j]=temp;
}
System.out.print("插入排序：");
printArr(numbers);
System.out.println();
}//6. 希尔排序
public static void shellSort(int[] numbers) {int n =numbers.length;//进行分组，最开始的增量(gap)为数组长度的一半
for (int gap = n / 2; gap > 0; gap /= 2) {//对各个分组进行插入排序
for (int i = gap; i < n; i++) {//将art[i]插入到所在分组的正确位置上
insertI(numbers, gap, i);
}
}
System.out.print("希尔排序：");
printArr(numbers);
System.out.println();
}//希尔排序插入方法//将art[i]插入到所在分组的正确位置上
private static void insertI(int[] arr, int gap, inti) {int inserted =arr[i];intj;for (j = i - gap; j >= 0 && inserted < arr[j]; j -=gap) {
arr[j+ gap] =arr[j];
}
arr[j+ gap] =inserted;
}//7. 归并排序
public static void mergeSort(int[] numbers, int left, intright) {int t = 1;//每组元素个数
int size = right - left + 1;while (t
t = 2 *s;int i =left;while (i + (t - 1)
merge(numbers, i, i+ (s - 1), i + (t - 1));
i+=t;
}if (i + (s - 1)
merge(numbers, i, i+ (s - 1), right);
}
System.out.print("归并排序：");
printArr(numbers);
System.out.println();
}//归并算法实现
private static void merge(int[] data, int p, int q, intr) {int[] B = new int[data.length];int s =p;int t = q + 1;int k =p;while (s <= q && t <=r) {if (data[s] <=data[t]) {
B[k]=data[s];
s++;
}else{
B[k]=data[t];
t++;
}
k++;
}if (s == q + 1)
B[k++] = data[t++];elseB[k++] = data[s++];for (int i = p; i <= r; i++)
data[i]=B[i];
}//打印数组
private static void printArr(int[] arr) {
System.out.print("[");for (int i = 0; i < arr.length; i++) {if (i == arr.length - 1) {
System.out.print(arr[i]+ "]");
}else{
System.out.print(arr[i]+ ", ");
}
}
}
}
