/*
* 排序算法
*/
class Solution {
public void swap(int[] arr, int i, int j) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
// 直接插入排序, O(n^2), 稳定
public void directInsert(int[] arr) {
for (int i = 0; i < arr.length; i ++) {
for (int j = 0; j < i; j ++) {
if (arr[j] > arr[i]) {
int temp = arr[i];
System.arraycopy(arr, j, arr, j + 1, i - j);
arr[j] = temp;
}
}
}
}
// 折半插入排序,O(nlogn),稳定
public void binaryInsert(int[] arr) {
for (int i = 0; i < arr.length; i ++) {
int left = 0, right = i - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[i]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
int temp = arr[i];
System.arraycopy(arr, left, arr, left + 1, i - left);
arr[left] = temp;
}
}
// 选择排序, O(n^2),不稳定
public void directSelect(int[] arr) {
for (int i = 0; i < arr.length - 1; i ++) {
for (int j = i + 1; j < arr.length; j ++) {
if (arr[i] > arr[j]) {
swap(arr, i, j);
}
}
}
}
// 堆排序, O(nlogn),不稳定,最大堆
public void heap(int[] arr) {
for (int i = arr.length - 1; i >= 0; i --) {
for (int j = i / 2 - 1; j >= 0; j --) {
if (j * 2 + 1 == i && i % 2 == 1) {
if (arr[j] < arr[j * 2 + 1]) {
swap(arr, j, j * 2 + 1);
}
} else {
if (arr[j] < arr[j * 2 + 1]) {
swap(arr, j, j * 2 + 1);
}
if (arr[j] < arr[j * 2 + 2]) {
swap(arr, j, j * 2 + 2);
}
}
}
swap(arr, 0, i);
}
}
// 冒泡排序,O(n^2), 稳定
public void bubble(int[] arr) {
for (int i = arr.length - 1; i >= 0; i --) {
for (int j = 0; j < i; j ++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
// 快排,O(nlogn),不稳定
public void quick(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int left, int right) {
if (arr == null || left >= right || arr.length <= 1) {
return;
}
int mid = partition(arr, left, right);
quickSort(arr, left, mid);
quickSort(arr, mid + 1, right);
}
private int partition(int[] arr, int left, int right) {
int temp = arr[left];
while (left < right) {
while (left < right && temp <= arr[right]) {
right --;
}
if (left < right) {
arr[left] = arr[right];
left ++;
}
while (left < right && temp >= arr[left]) {
left ++;
}
if (left < right) {
arr[right] = arr[left];
right --;
}
}
arr[left] = temp;
return left;
}
// 归并排序, O(nlogn), 稳定
public void mergeSort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
private void sort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, index = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[index ++] = arr[i ++];
} else {
temp[index ++] = arr[j ++];
}
}
while (i <= mid) {
temp[index ++] = arr[i ++];
}
while (j <= right) {
temp[index ++] = arr[j ++];
}
for (int k = 0; k < temp.length; k ++) {
arr[left ++] = temp[k];
}
}
}
原文:https://www.cnblogs.com/ipython258/p/14800379.html