java实现各种基础排序（冒泡排序、快速排序、直接选择排序、堆排序、直接插入排序、归并排序）(三)
* 堆排序（从小到大）
*
* @param A
* @param n
*/
public static void heapSort(int A[], int n) {
int tmp;
// 构建大根堆
buildMaxHeap(A, n);
for (int j = n - 1; j >= 1; j--) {
tmp = A[0];
A[0] = A[j];
A[j] = tmp;
maxheapIfy(A, 0, j);
}
}
/**
* 构建大根堆
*
* @param A
* @param n
*/
private static void buildMaxHeap(int A[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
maxheapIfy(A, i, n);
}
}
/**
* 维护从下标i开始的最大堆
*
* @param A
* @param i
* @param n
*/
private static void maxheapIfy(int A[], int i, int n) {
int left, right, loc;
while (i < n) {
left = 2 * i + 1;
right = 2 * i + 2;
loc = i;
if (left < n && A[left] > A[i]) {
i = left;
}
if (right < n && A[right] > A[i]) {
i = right;
}
if (loc != i) {
A[i] = A[loc] ^ A[i];
A[loc] = A[loc] ^ A[i];
A[i] = A[loc] ^ A[i];
} else {
break;
}
}
}
/**
* 直接选择排序
*
* @param A
* @param n
*/
public static void selectSort(int A[], int n) {
int i, j, loc;
for (i = 0; i < n; i++) {
loc = i;
for (j = i + 1; j < n; j++) {
if (A[j] < A[loc]) {
loc = j;
}
}
if (loc != i) {
A[i] = A[i] ^ A[loc];
A[loc] = A[i] ^ A[loc];
A[i] = A[i] ^ A[loc];
}
}
}
/**
* 直接插入排序
*
* @param A
* @param n
*/
public static void insertSort(int A[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = A[i];
for (j = i - 1; j >= 0; j--) {
if (A[j] > tmp) {
A[j + 1] = A[j];
} else {
break;
}
}
A[j + 1] = tmp;
}
}
/**
* 冒泡排序
*
* @param A
* @param n
*/
public static void bubbleSort(int A[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (A[j] > A[j + 1]) {
A[j] = A[j] ^ A[j + 1];
A[j + 1] = A[j] ^ A[j + 1];
A[j] = A[j] ^ A[j + 1];
}
}
}
}
/**
* 打印数组
*
* @param A
*/
public static void printArr(int A[]) {
for (int i = 0; i < A.length; i++) {
if (i == A.length - 1) {
System.out.printf("%d\n", A[i]);
} else {
System.out.printf("%d ", A[i]);
}
}
}
}