经过两个月的各种笔试面试，对各种基础排序算法原理了然于胸，用c闭着眼都能写出完美ac的代码来，今天刚看完java的数组，忍不住用java将各种排序实现一遍
注意，这篇文章只是为了锻炼java语法，不会深入讲各种排序原理，有兴趣的同学可以看我之前的博客，各自排序我都用c讲的非常清楚了
冒泡排序
[java]
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];
}
}
}
}
直接插入排序
[java]
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;
}
}
直接选择排序
[java]
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];
}
}
}
堆排序
[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;
}
}
}
快速排序
[java] view plaincopy在CODE上查看代码片派生到我的代码片
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];
}
}
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;
}
归并排序
[java] view plaincopy在CODE上查看代码片派生到我的代码片
public static void mergeSort(int A[], int bt, int ed) {
if (bt < ed) {
int mid =