排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。下面主要对一些常见的排序算法做介绍，并分析它们的时空复杂度。
1. 选择排序
1.1 简单选择排序
简单选择排序的思想是：设排序序列的记录个数为n，进行n-1次大遍历，每次遍历i，找出（i到n中）的最小值并与i进行交换。
static void funSelectionSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
int length = array.length;
for(int start = 0; start < length; start++) {
int minIndex = start;
for (int i = start + 1; i < length; i++) {
if (array[i] < array[minIndex]) {
minIndex = i;
}
}
int temp = array[start];
array[start] = array[minIndex];
array[minIndex] = temp;
}
}
1.2 堆排序
堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。
如果把堆对应一个数组，假设一个堆的数组A，树的根为A[1]，i表示某一结点的下标，则父结点为PARENT(i)，左儿子LEFT[i]，右儿子RIGHT[i]的关系如下：
PARENT(i)
return |_i/2_|
LEFT(i)
return 2i
RIGHT(i)
return 2i + 1
我们可以很容易的定义堆排序的过程：
- 由输入的无序数组构造一个最大堆，作为初始的无序区
- 把堆顶元素（最大值）和堆尾元素互换
- 把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
- 重复步骤2，直到堆的尺寸为1
这里我思维的误区：
最大堆的的左树和右树之间没有大小的可比性，他们两个只是都比父节点小；所以再是用最大堆概念的时候，只有最大值是有意义的。这事是为什么每次循环都会把堆顶提出来调整出一个最大堆（类似最大堆的删除），重复。
public class HeapSort {
public void main(String[] args) {
int arr[] = {5, 6, 1, 0, 2, 9};
heapsort(arr, 6);
System.out.println(Arrays.toString(arr));
}
/***
* 创建最大堆
* @param a
* @param len
*/
void buildHeap(int a[], int len) {
for (int i = len / 2 - 1; i >= 0; i--) {
heapfy(a, i, len);
}
}
/***
* 对某一子树进行最大堆判断&调整
* @param a
* @param index 子树根节点index
* @param heapsize 最大堆元素数
*/
void heapfy(int a[], int index, int heapsize) {
int left = index * 2 + 1;
int right = left + 1;
if (right < heapsize && a[right] > a[left]) {
left = right;
}
if (a[index] < a[right]) {
swap(a, index, left);
heapfy(a, left, heapsize);
}
}
/***
* 最大堆排序
* @param a
* @param len
*/
void heapsort(int a[], int len) {
buildHeap(a, len);
for (int i = len - 1; i >= 0; i--) {
swap(a, i, 0);
heapfy(a, 0, i);
}
}
private void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
2. 交换排序
2.1 冒泡排序
冒泡排序的基本思想是：设排序序列的记录个数为n，进行n-1次遍历，每次遍历从开始位置依次往后比较前后相邻元素，这样较大的元素往后移，n-1次遍历结束后，序列有序。
例如，对序列(3,2,1,5)进行排序的过程是：共进行3次遍历，第1次遍历时先比较3和2，交换，继续比较3和1,交换，再比较3和5，不交换，这样第1次遍历结束，最大值5在最后的位置，得到序列(2,1,3,5)。第2次遍历时先比较2和1，交换，继续比较2和3，不交换，第2次遍历结束时次大值3在倒数第2的位置，得到序列(1,2,3,5)，第3次遍历时，先比较1和2，不交换，得到最终有序序列(1,2,3,5)。
需要注意的是，如果在某次遍历中没有发生交换，那么就不必进行下次遍历，因为序列已经有序。
static void funBubbleSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
int len = array.length;
for (int i = 0; i < len - 1; i++) {
boolean swap = false;
for (int j = 0; j < len - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap = true;
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
if (!swap) {
return;
}
}
}
2.2 快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：
- 从序列中挑出一个元素，作为"基准"(pivot).
- 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
- 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
class Quick {
public void main() {
int arr[] = {5, 6, 1, 0, 2, 9};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
void quickSort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int pivotIndex = partition(array, start, end);
quickSort(array, start, pivotIndex - 1);
quickSort(array, pivotIndex + 1, end);
}
void swap(int[] array, int start, int end) {
int tmp = array[start];
array[start] = array[end];
array[end] = tmp;
}
int partition(int[] array, int start, int end) {
int pivot = array[end]; //选取最后一个元素作为比较基准
int tail = start - 1; //基准元素左侧元素index
for (int i = start; i < end; i++) {
if (array[i] <= pivot) {
swap(array, i, tail++);
}
}
swap(array, tail + 1, end);
return tail + 1;
}
}
3. 插入排序
3.1 直接插入排序
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
void funDInsertSort(int[] array) {
if (array == null) {
return;
}
int len = array.length;
for (int i = 1; i < len; i++) {
int j = i;
int tmp = array[i];
while (j >= 1 && array[j - 1] > tmp) {
array[j] = array[j - 1];
j--;
}
array[j] = tmp;
}
}
3.2 shell排序|希尔排序
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
-
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
希尔排序示例
void shellSort(int[] array) {
if (array == null) {
return;
}
for (int gap = array.length / 2; gap > 0; gap /= 2) {
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for (int i = gap; i < array.length; i++) {
int j = i - gap;
int tmp = array[i];
while (j >= 0 && array[j] > tmp) {
array[j + gap] = array[j];
j -= gap;
}
array[j + gap] = tmp;
}
}
}
4. 归并排序
归并排序是分治法的一个典型应用，它的主要思想是：将待排序序列分为两部分，对每部分递归地应用归并排序，在两部分都排好序后进行合并。
其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序，但是归并排序是一种稳定的排序算法，快速排序则不然。所谓稳定排序，表示对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型而言，一个排序算法是否稳定，影响很小，但是对于结构体数组，稳定排序就十分重要。例如对于student结构体按照关键字score进行非降序排序：
class MergeSort {
public void main() {
int arr[] = {5, 6, 1, 0, 2, 9};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
void mergeSort(int[] array, int start, int end) {
if (start + 1 < end) {
int len1 = (end - start) / 2;
int len2 = end - start + 1 - len1;
mergeSort(array, start, start + len1 - 1);
mergeSort(array, start + len1, end);
mergeArray(array, start, end);
}
}
private void mergeArray(int[] array, int start, int end) {
int len1 = (end - start) / 2;
int len2 = end - start + 1 - len1;
int i = 0;
int j = 0;
int[] result = new int[end - start + 1];
while (i < len1 && j < len2) {
if (array[start + i] <= array[start + len1 + j]) {
result[i + j] = array[start + i];
i++;
} else {
result[i + j] = array[start + len1 + j];
j++;
}
}
System.arraycopy(result, 0, array, start, len1 + len2);
}
}
