java实现各种基础排序（冒泡排序、快速排序、直接选择排序、堆排序、直接插入排序、归并排序）(二)
bt + (ed - bt) / 2;
mergeSort(A, bt, mid);
mergeSort(A, mid + 1, ed);
mergeArray(A, bt, mid, ed);
}
}
private static void mergeArray(int A[], int bt, int mid, int ed) {
int i, j, k, len = ed - bt + 1;
int tmp[] = new int[len];
for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
if (A[i] <= A[j]) {
tmp[k] = A[i++];
} else {
tmp[k] = A[j++];
}
}
while (i <= mid) {
tmp[k++] = A[i++];
}
while (j <= ed) {
tmp[k++] = A[j++];
}
for (i = 0; i < k; i++) {
A[bt + i] = tmp[i];
}
}
测试程序
[java]
import java.util.Scanner;
public class
JavaSort {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int A[], n;
while (cin.hasNext()) {
n = cin.nextInt();
A = new int[n];
for (int i = 0; i < n; i++) {
A[i] = cin.nextInt();
}
// bubbleSort(A, n);
// insertSort(A, n);
// selectSort(A, n);
// heapSort(A, n);
// quickSort(A, 0, n - 1);
mergeSort(A, 0, n - 1);
printArr(A);
}
}
/**
* 归并排序
*
* @param A
* @param bt
* @param ed
*/
public static void mergeSort(int A[], int bt, int ed) {
if (bt < ed) {
int mid = bt + (ed - bt) / 2;
mergeSort(A, bt, mid);
mergeSort(A, mid + 1, ed);
mergeArray(A, bt, mid, ed);
}
}
/**
* 合并数组
*
* @param A
* @param bt
* @param mid
* @param ed
*/
private static void mergeArray(int A[], int bt, int mid, int ed) {
int i, j, k, len = ed - bt + 1;
int tmp[] = new int[len];
for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
if (A[i] <= A[j]) {
tmp[k] = A[i++];
} else {
tmp[k] = A[j++];
}
}
while (i <= mid) {
tmp[k++] = A[i++];
}
while (j <= ed) {
tmp[k++] = A[j++];
}
for (i = 0; i < k; i++) {
A[bt + i] = tmp[i];
}
}
/**
* 快速排序
*
* @param A
* @param bt
* @param ed
*/
public static void quickSort(int A[], int bt, int ed) {
if (bt < ed) {
int pivot = pivotPartition(A, bt, ed);
quickSort(A, bt, pivot - 1);
quickSort(A, pivot + 1, ed);
}
}
private static void swapVar(int A[], int bt, int ed) {
int mid = bt + (ed - bt) / 2;
if (mid != bt) {
A[bt] = A[bt] ^ A[mid];
A[mid] = A[bt] ^ A[mid];
A[bt] = A[bt] ^ A[mid];
}
}
/**
* 快排寻找基准点位置
*
* @param A
* @param bt
* @param ed
* @return
*/
private static int pivotPartition(int A[], int bt, int ed) {
// 取中间值作为stand，防止数组有序出现O(n^2)情况
swapVar(A, bt, ed);
int stand = A[bt];
while (bt < ed) {
while (bt < ed && A[ed] >= stand) {
ed--;
}
if (bt < ed) {
A[bt++] = A[ed];
}
while (bt < ed && A[bt] <= stand) {
bt++;
}
if (bt < ed) {
A[ed--] = A[bt];
}
}
A[bt] = stand;
return bt;
}
/**