冒泡排序：两两比较相邻记录的值，如果反序则交换，直到没有反序的记录为止。
public void bubbleSort(int[] a) {
boolean notSorted = true;
for (int i = 0; i < a.length - 1 && notSorted; i++) {
notSorted = false;
for (int j = a.length - 2; j >= i; j--) {
if (a[j] > a[j + 1]) { swap(a, j, j + 1); notSorted = true; }
}
}
}
选择排序：通过n-i次值的比较，从n-i+1个记录中选出值最小的记录，并和第i个记录交换。
public void selectionSort(int[] a) {
for (int i = 0, min = 0; i < a.length - 1; i++) {
min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) min = j;
}
if (min != i) swap(a, min, i);
}
}
插入排序：将一个记录插入到已经排好序的有序表中。
public void insertionSort(int[] a) {
int temp;
for (int i = 1, j; i < a.length; i++) {
if (a[i] < a[i - 1]) {
temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--)
a[j + 1] = a[j];
a[j + 1] = temp;
}
}
归并排序：将两个或两个以上的有序表组合成一个新的有序表（递归）。
public viod mergeSort(int[] a) {
int[] temp = new int[a.length];
mergeSort(a, temp, 0, a.length - 1);
}
private void mergeSort(int[] a, int[] temp, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(a, temp, low, mid);
mergeSort(a, temp, mid + 1, high);
merge(a, temp, low, mid, high);
}
}
private void merge(int[] a, int[] temp, int low, int mid, int high) {
for (int i = low, i <= high; i++) {
temp[i] = a[i];
}
int tempLeft = low;
int tempRight = mid + 1;
int current = low;
while (tempLeft <= mid && tempRight <= high) {
if (temp[tempLeft] <= temp[tempRight]) {
a[current] = temp[tempLeft];
tempLeft++;
} else {
a[current] = temp[tempRight];
tempRight++;
}
current++;
}
int remaining = mid - tempLeft;
for (int i = 0; i <= remaining; i++) {
a[current + i] = temp[tempLeft + i];
}
}
快速排序：通过一趟排序将待排序记录分割成独立的两部分，其中一部分的值均比另一部分的值小，然后递归的对这两部分进行排序。
public void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}
private void quickSort(int[] a, int low, int high) {
if (low < high) {
int p = partition(a, low, high);
quickSort(a, low, p - 1);
quickSort(a, p + 1, high);
}
}
private int partition(int[] a, int low, int high) {
int pivot = a[high];
int i = low;
for (int j = low; j <= high - 1; j++) {
if (a[j] <= pivot) { swap(a, i, j); i++; }
}
swap(a, i, high);
return i;
}
转载于:https://www.cnblogs.com/hippiebaby/p/5469169.html
