public class sort {
public static void main(String[] args) {
int[] arr = {2, 5, 3, 4, 8, 5, 1};
//sort_insert(arr);
//sort_bin(arr);
//sort_bubble(arr);
sort_quick(arr,0,6);
//sort_select(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
} //直接插入排序
public static void sort_insert(int[] arr) {
int n = arr.length;
int temp;
for (int i = 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {//如果后面的小于前面的
int j = i - 1;
temp = arr[i];//因为往后会淹没要插入的
//下面的while是只要大于就后移一位,直到可以插入
while (j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
} //折半插入排序
public static void sort_bin(int[] arr) {
int i, j, low, high, mid, temp;
int n = arr.length;
for (i = 1; i < n; i++) {
temp = arr[i];
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (temp > arr[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
for (j = i; j > low; j--) {
arr[j] = arr[j - 1];
}
arr[low] = temp; } } //冒泡排序
public static void sort_bubble(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
} //快速排序
public static void sort_quick(int[] arr, int left, int right) {
int temp;
int i = left, j = right;
if (left < right) {
temp = arr[left];
//完成一趟循环,将数组小于temp的放在左边,大于temp的放在右边
while (i != j) {//相等时候说明相遇了,此时i的位置就是插入的位置
//从右往左找到一个小于temp的元素
while (j > i && arr[j] > temp) {
--j;
}
if (i < j) {
arr[i] = arr[j];
++i;//指针右移动一位
}
//从左往右找,找到一个大于temp的元素
while (i < j && arr[i] < temp) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;//指针向前一位,刚移动的
} }
arr[i] = temp;
sort_quick(arr, left, i - 1);
sort_quick(arr, i + 1, right);
} } //简单选择排序,在无序序列选最小的放到有序的上面
public static void sort_select(int[] arr) {
for (int i = 0; i < arr.length; i++) {
//记住最小的序号,默认第一个
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
//交换当前i序号与得到最小的
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}