常见的排序（Sort）算法有选择排序、堆排序、归并排序、插入排序和快速排序等。排序算法的稳定性意味着如果列表中的两个元素被定义为相等，那么它们将在排序完成后保持它们的相对顺序。
算法原理
选择排序 O(N^2)
参考博客选择排序算法原理及实现（Java/Python）
归并排序 O(NlogN)
参考博客归并排序算法原理及实现（Java）
堆排序 O(NlogN)
使用最大堆（maxHeap）进行排序；
首先将待排序的元素放入maxHeap中，再将maxHeap中的元素输出到结果数组中。
改进堆排序：就地维护一个maxHeap，节约空间。
插入排序 O(N^2)
从左到右依次遍历数组中的元素，将当前元素通过swap的方式放到左边正确的位置上。
快速排序 O(NlogN)
从数组中随机选择一个元素，将其他小于等于它的元素放在左半部分，将大于等于它的元素放在右半部分；
对左右两部分的元素进行快速排序，直到数组大小为1。
对分区方式的改进：
每次选择数组最左边的元素P；
使用两个指针L和G分别从剩下部分的左边和右边进行遍历；
L遇到大于等于P的元素停止遍历；
G遇到小于等于P的元素停止遍历；
当两个指针都停止遍历时交换两个指针指向的元素，当G指针出现在L指针左边时停止遍历，将P和G的元素进行交换；
对P左右两边的数组分别进行快速排序。
java代码
Sorts.java
public class Sorts {
public int[] heapSort(int[] arr) {
maxHeap nums = new maxHeap();
for (int i = 0; i < arr.length; i++) {
nums.insert(arr[i]);
}
int[] res = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
res[i] = nums.remove();
}
return res;
}
public int[] heapSortInPlace(int[] arr) {
maxHeap temp = new maxHeap();
for (int i = arr.length - 1; i >= 0; i--) {
int cur = i;
int next = temp.checkSwap(arr, cur, arr.length);
while (next != -1) {
swap(arr, cur, next);
cur = next;
next = temp.checkSwap(arr, cur, arr.length);
}
}
int curLast = arr.length - 1;
int curFirst = 0;
while (curFirst <= curLast) {
swap(arr, curFirst, curLast);
int nextIdx = temp.checkSwap(arr, curFirst, curLast);
int curIdx = curFirst;
while (nextIdx != -1) {
swap(arr, curIdx, nextIdx);
curIdx = nextIdx;
nextIdx = temp.checkSwap(arr, curIdx, curLast);
}
curLast -= 1;
}
return arr;
}
public int[] insertionSort(int[] arr) {
int cur;
int prev;
for (int i = 0; i < arr.length; i++) {
cur = i;
prev = cur - 1;
while (prev >= 0 && arr[cur] < arr[prev]) {
swap(arr, cur, prev);
cur = prev;
prev = cur - 1;
}
}
return arr;
}
public int[] quickSort(int[] arr) {
if (arr.length < 2) {
return arr;
}
int P = 0;
int L = P + 1;
int G = arr.length - 1;
while (L <= G) {
if (arr[L] < arr[P]) {
L += 1;
}
if (arr[G] > arr[P]) {
G -= 1;
}
if (L <= G && arr[L] >= arr[P] && arr[G] <= arr[P]) {
swap(arr, L, G);
L += 1;
G -= 1;
}
}
swap(arr, P, G);
int leftLen = G;
int rightLen = arr.length - G - 1;
if (leftLen > 0) {
int[] arrLeft = new int[G];
System.arraycopy(arr, 0, arrLeft, 0, leftLen);
System.arraycopy(quickSort(arrLeft), 0, arr, 0, leftLen);
}
if (rightLen > 0) {
int[] arrRight = new int[rightLen];
System.arraycopy(arr, G + 1, arrRight, 0, rightLen);
System.arraycopy(quickSort(arrRight), 0, arr, G + 1, rightLen);
}
return arr;
}
private void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
maxHeap.java
public class maxHeap {
private int[] arr;
private int totalSize;
private int size;
maxHeap() {
totalSize = 100;
arr = new int[totalSize];
size = 0;
}
public void insert(int t) {
arr[size] = t;
int curIdx = size;
int parentIdx = getParent(curIdx);
while (parentIdx >= 0 && curIdx != 0) {
if (arr[curIdx] > arr[parentIdx]) {
swap(arr, curIdx, parentIdx);
}
curIdx = parentIdx;
parentIdx = getParent(curIdx);
}
size += 1;
}
private int getParent(int idx) {
return (idx - 1) / 2;
}
public void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public int remove() {
int res = arr[0];
arr[0] = arr[size - 1];
size -= 1;
int curIdx = 0;
int nextIdx = checkSwap(arr, curIdx, size);
while (nextIdx != -1) {
swap(arr, curIdx, nextIdx);
curIdx = nextIdx;
nextIdx = checkSwap(arr, curIdx, size);
}
return res;
}
public int checkSwap(int[] arr, int cur, int size) {
int leftIdx = getLeft(cur);
int rightIdx = getRight(cur);
if (leftIdx >= size && rightIdx >= size) {
return -1;
} else if (leftIdx >= size) {
if (arr[cur] < arr[rightIdx]) {
return rightIdx;
} else {
return -1;
}
} else if (rightIdx >= size) {
if (arr[cur] < arr[leftIdx]) {
return leftIdx;
} else {
return -1;
}
} else {
return maxInThree(arr, cur, leftIdx, rightIdx);
}
}
private int maxInThree(int[] arr, int a, int b, int c) {
if (arr[b] > arr[c]) {
if (arr[a] > arr[b]) {
return -1;
} else {
return b;
}
} else {
if (arr[a] > arr[c]) {
return -1;
} else {
return c;
}
}
}
private int getLeft(int curIdx) {
return (curIdx + 1) * 2 - 1;
}
private int getRight(int curIdx) {
return (curIdx + 1) * 2;
}
}
