[Java] 纯文本查看 复制代码
import java.util.Arrays;
public class SortTest {
public static void main(String[] args){
int[] a = {2,4,3,7,5,8,1,6};
System.out.println("使用插入排序："+ Arrays.toString(insertSort(a)));
System.out.println("使用二分插入排序："+ Arrays.toString(binaryInsertSort(a)));
System.out.println("使用冒泡排序："+ Arrays.toString(bubble(a)));
System.out.println("使用快速排序：" + Arrays.toString(quickSort(a, 0, a.length-1)));
}
/**
* 插入排序
* 步骤：将无序数列中的数与有序数列依次比较，插入合适的位置，直至整个数列有序
* @param numbers
* @return
*/
public static int[] insertSort(int[] numbers){
for (int i = 0; i < numbers.length; i++){
for (int j = i; j > 0; j--){
if (numbers[j] < numbers[j-1]){
int temp = numbers[j];
numbers[j] = numbers[j-1];
numbers[j-1] = temp;
}
}
}
return numbers;
}
/**
* 二分插入排序
* @param numbers
* @return
*/
public static int[] binaryInsertSort(int[] numbers){
for (int i = 1; i < numbers.length; i++){
if (numbers < numbers[i-1]){
int temp = numbers;
int left = 0;
int right = numbers.length - 1;
while (left <= right){
int mid = (left + right) / 2;
if (numbers[mid] < temp){
left += 1;
} else {
right -= 1;
}
}
for (int j = i; j > left; j--){
numbers[j] = numbers[j-1];
}
numbers[left] = temp;
}
}
return numbers;
}
/**
* 冒泡排序
* 步骤：1.依次比较相邻两个数的大小，将大数放在小数后面
* 2.重复步骤1至排序结束
* @param numbers
*/
public static int[] bubble(int[] numbers){
int temp = 0;
int len = numbers.length - 1;
for (int i = 0; i < len; i++){
for (int j = 0; j < len - i; j++){
if (numbers[j] > numbers[j+1]){
temp = numbers[j];
numbers[j] = numbers[j+1];
numbers[j+1] = temp;
}
}
}
return numbers;
}
/**
* 快速排序
* @param numbers
* @param low
* @param high
* @return
*/
public static int[] quickSort(int[] numbers, int low, int high){
if (low < high){
int mid = getMid(numbers, low, high);
quickSort(numbers, low, mid - 1);
quickSort(numbers, mid + 1, high);
}
return numbers;
}
public static int getMid(int[] numbers, int low, int high){
int temp = numbers[low];
while (low < high){
while (numbers[high] > temp){
high--;
}
numbers[low] = numbers[high];
while (numbers[low] < temp){
low++;
}
numbers[high] = numbers[low];
}
numbers[low] = temp;
return low;
}
}