代码写久了，越发的觉得写到后来回归的都是基础。顿时觉得后悔大1大2没好好学这些计算机基础课程，亏大了。
总结下排序算法：
package 排序算法;
/**
* 1.选择排序
* 2.插入排序
* 3.归并排序
* 4.快速排序
*
* @author Administrator
*
*/
public class 4种排序算法 {
public static void main(String[] args) {
int[] arr = { 2, 5, 6, 7, 4, 3, 1, 1, 3, 4, 5, 1, 3, 6, 3 };
// selectSort(arr);
// insertedSort(arr);
// mergeSort(arr, 0, arr.length - 1);
quickSort(arr, 0, arr.length - 1);
out(arr);
}
// 输出
public static void out(int[] arr) {
for (int e : arr)
System.out.print(e + ",");
}
// 1.选择排序
public static void selectSort(int[] a) {
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++) {
int key = a[i];
if (key > a[j]) {
a[i] = a[j];
a[j] = key;
}
}
}
// 2.插入排序
public static void insertedSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && key < a[j]) {
a[j + 1] = a[j];
a[j] = key;
j--;
}
}
}
// 3.归并排序(分治法)
public static void mergeSort(int[] a, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
// 递归到最小原子
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
// 合并数组
mergeArray(a, low, mid, high);
}
}
// 合并数组
private static void mergeArray(int[] a, int low, int mid, int high) {
int N = high - low;
int[] temp = new int[N + 1];
int i = low, j = mid + 1;
int m = mid, n = high;
int k = 0;
while (i <= m && j <= n)
temp[k++] = (a[i] < a[j] ? a[i++] : a[j++]);
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[low + i] = temp[i];
}
// 4.快速排序(分治法)
public static void quickSort(int[] a, int low, int high) {
if (low < high) {
int r = adjustArray(a, low, high);
quickSort(a, low, r - 1);
quickSort(a, r + 1, high);
}
}
// 提取数组中的首个元素，分割。小的元素放在<strong>标志</strong>的左侧，比
// 标志大的元素放在其右侧，最后返回标志元素的位置
private static int adjustArray(int[] a, int low, int high) {
int i = low, j = high;
int spcValue = a[low];
while (i < j) {
while (a[j] >= spcValue && i < j)
j--;
if (a[j] < spcValue)
a[i++] = a[j];
while (a[i] <= spcValue && i < j)
i++;
if (a[i] > spcValue)
a[j--] = a[i];
}
a[i] = spcValue;
return i;
}
}