归并排序
/*
* 归并排序(从上往下)
*
* 参数说明: a -- 待排序的数组 start -- 数组的起始地址 endi -- 数组的结束地址
*/
public void Sort(int[] a, int start, int end) {
if (a == null || start >= end)
return;
int mid = (end + start) / 2;
Sort(a, start, mid); // 递归排序a[start...mid]
Sort(a, mid + 1, end); // 递归排序a[mid+1...end]
// a[start...mid] 和 a[mid...end]是两个有序空间,
// 将它们排序成一个有序空间a[start...end]
merge(a, start, mid, end);
}
/*
* 将一个数组中的两个相邻有序区间合并成一个
*
* 参数说明: a -- 包含两个有序区间的数组 start -- 第1个有序区间的起始地址。 mid --
* 第1个有序区间的结束地址。也是第2个有序区间的起始地址。 end -- 第2个有序区间的结束地址。
*/
public void merge(int[] a, int start, int mid, int end) {
int[] tmp = new int[end - start + 1]; // tmp是汇总2个有序区的临时区域
int i = start; // 第1个有序区的索引
int j = mid + 1; // 第2个有序区的索引
int k = 0; // 临时区域的索引
// 类似于合并两个有序链表,当两个有序链表都有数据时,比较这两个链表的数据,并将小的数据放到新开辟出的空间中
while (i <= mid && j <= end) {
if (a[i] <= a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
// 防止两个数组一个排完了,另一个还没有排完,将剩下的那个数组的值接在后面。
while (i <= mid)
tmp[k++] = a[i++];
while (j <= end)
tmp[k++] = a[j++];
// 将排序后的元素,全部都整合到数组a中。
for (i = 0; i < k; i++)
a[start + i] = tmp[i];
tmp = null;
}
快速排序
/*
* 快速排序
*
* 参数说明: a -- 待排序的数组 l -- 数组的左边界(例如,从起始位置开始排序,则l=0) r --
* 数组的右边界(例如,排序截至到数组末尾,则r=a.length-1)
*/
public static void quickSort(int[] a, int l, int r) {
if (l < r) {
int i, j, x;
i = l;
j = r;
x = a[i];
while (i < j) {
while (i < j && a[j] > x) {
j--; // 从右向左找第一个小于x的数
}
if (i < j) {
a[i++] = a[j];
}
while (i < j && a[i] < x) {
i++; // 从左向右找第一个大于x的数
}
if (i < j) {
a[j--] = a[i];
}
}
a[j] = x;
quickSort(a, l, i - 1); /* 递归调用 */
quickSort(a, i + 1, r); /* 递归调用 */
}
}
网友评论