常见排序算法简析
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。这里我们说的排序算法只对内部排序。
1.简单选择排序
实现原理
首先从未排序序列中找到最小的元素，放置到排序序列的起始位置，然后从剩余的未排序序列中继续寻找最小元素，放置到已排序序列的末尾。所以称之为选择排序。
select.jpg
代码示例
public int[] selectSort(int[] a){
int position = 0;
for(int i = 0; i < a.length; i++){
int j = i + 1;
position = i;
int temp = a[i];
for(; j < a.length; j++){
if(a[j] < temp){
temp = a[j];
position = j;
}
}
a[position] = a[i];
a[i] = temp;
}
return a;
}
算法分析
每次要找一遍最小值，最坏情况下找n次，这样的过程要执行n次，所以时间复杂度还是O(n^2)。空间复杂度是O(1)。
2.直接插入排序
实现原理
插入排序的基本思想是：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。例如：认为第一个元素是排好序的，从第二个开始遍历。拿出当前元素的值，从排好序的序列中从后往前找。如果序列中的元素比当前元素大，就把它后移。直到找到一个小的。把当前元素放在这个小的后面（后面的比当前大，它已经被后移了）。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
insertSort.jpg
代码示例
public int[] inserSort(int[] arrays){
int temp = 0;
for(int i = 1; i < arrays.length; i++){
int j = i-1;
temp = arrays[i];
for(; j >= 0 && temp < arrays[j]; j--){
arrays[j+1] = arrays[j]; //将大于temp的值整体后移一个单位
}
arrays[j+1] = temp;
}
return arrays;
}
算法分析
因为要选择n次，而且插入时最坏要比较n次，所以时间复杂度同样是O(n^2)。空间复杂度是O(1)。
3.冒泡排序
实现原理
依次比较相邻的两个元素，如果第一个元素大于第二个元素就交换它们的位置。这样比较一轮之后，最大的元素就会跑到队尾。然后对未排序的序列重复这个过程，最终转换成有序序列。
BubbleSort.jpg
代码示例
public int[] bubbleSort(int[] a){
int temp = 0;
for(int i = 0; i < a.length-1; i++){
for(int j = 0; j < a.length-1-i; j++){
if(a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
return a;
}
算法分析
由于我们要重复执行n次冒泡，每次冒泡要执行n次比较（实际是1到n的等差数列，也就是(a1 + an) * n / 2），也就是 O(n^2)。 空间复杂度是O(1)。
4.快速排序
实现原理
在数据集之中，选择一个元素作为”基准”（pivot）。
所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition)。
操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
quicksort.jpg
代码示例
public void quickSort(int[] input){
sort(input, 0, input.length-1);
}
public void sort(int[] input,int low,int high){
if (high <= low){
return;
}
int mid=partition (input, low, high);
sort (input, low, mid-1);
sort (input, mid+1, high);
}
public int partition(int[] input, int low, int high){
return 0;
}
算法分析
快速排序也是一个不稳定排序，平均时间复杂度是O(nlogn)。空间复杂度是O(logn)。
5.希尔排序
实现原理
先取一个正整数 d1(d1 < n)，把全部记录分成 d1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序，然后取 d2(d2 < d1)重复上述分组和排序操作；直到取 di = 1(i >= 1) 位置，即所有记录成为一个组，最后对这个组进行插入排序。一般选 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
shellSort.jpg
代码示例
public int[] shellSort(int[] a){
double d1 = a.length;
int temp = 0;
while(true){
d1 = Math.ceil(d1/2);
int d = (int) d1;
for(int x = 0; x < d; x++){
for(int i = x + d; i < a.length; i += d){
int j = i - d;
temp = a[i];
for(; j >= 0 && temp < a[j]; j -= d){
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
if(d==1){
break;
}
}
return a;
}
算法分析
希尔排序的时间复杂度受步长的影响，平均时间复杂度是O(n log2 n),空间复杂度是O(1)。希尔排序方法是一个不稳定的排序方法。
6.堆排序
实现原理
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
- 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
- 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
heapSort.jpg
代码示例
/**
* 堆排序
*/
public static int[] heapSort(int[] arr) {
// 将待排序的序列构建成一个大顶堆
for (int i = arr.length / 2; i >= 0; i--){
heapAdjust(arr, i, arr.length);
}
// 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
}
return arr;
}
/**
* 构建堆的过程
* @param arr 需要排序的数组
* @param i 需要构建堆的根节点的序号
* @param n 数组的长度
*/
private static void heapAdjust(int[] arr, int i, int n) {
int child;
int father;
for (father = arr[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
// 如果左子树小于右子树，则需要比较右子树和父节点
if (child != n - 1 && arr[child] < arr[child + 1]) {
child++; // 序号增1，指向右子树
}
// 如果父节点小于孩子结点，则需要交换
if (father < arr[child]) {
arr[i] = arr[child];
} else {
break; // 大顶堆结构未被破坏，不需要调整
}
}
arr[i] = father;
}
// 获取到左孩子结点
private static int leftChild(int i) {
return 2 * i + 1;
}
// 交换元素位置
private static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
算法分析
堆执行一次调整需要O(logn)的时间，在排序过程中需要遍历所有元素执行堆调整，所以最终时间复杂度是O(nlogn)。空间复杂度是O(1)。
7.归并排序
实现原理
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
把 n 个记录看成 n 个长度为 l 的有序子表；进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表；重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。
Merge.jpg
代码示例
public static int[] mergeSort(int[] arr){
int[] temp =new int[arr.length];
internalMergeSort(arr, temp, 0, arr.length-1);
return temp;
}
private static void internalMergeSort(int[] a, int[] b, int left, int right){
//当left==right的时，已经不需要再划分了
if (left<right){
int middle = (left+right)/2;
internalMergeSort(a, b, left, middle); //左子数组
internalMergeSort(a, b, middle+1, right); //右子数组
mergeSortedArray(a, b, left, middle, right); //合并两个子数组
}
}
// 合并两个有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]。temp是辅助数组。
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
int i=left;
int j=middle+1;
int k=0;
while ( i<=middle && j<=right){
if (arr[i] <=arr[j]){
temp[k++] = arr[i++];
}
else{
temp[k++] = arr[j++];
}
}
while (i <=middle){
temp[k++] = arr[i++];
}
while ( j<=right){
temp[k++] = arr[j++];
}
//把数据复制回原数组
for (i=0; i<k; ++i){
arr[left+i] = temp[i];
}
}
算法分析
在合并数组过程中，实际的操作是当前两个子数组的长度，即2m。又因为打散数组是二分的，最终循环执行数是logn。所以这个算法最终时间复杂度是O(nlogn)，空间复杂度是O(1)。
