一直都想写写排序，今天终于有时间了。记得刚刚开始接触算法的时候，遇到的第一问题往往就是排序问题。因为排序很自然，我们每天都要接触，而排序算法十分丰富，可以让初学者大开眼界的同时对算法复杂度和分治思想有一定的认识。今天我也回顾下自己了解的排序算法，算是做个记录吧。
排序问题如何去分呢？首先应该分为基于比较的排序和非基于比较的排序。基于比较的排序有理论的最优时间复杂度O(N*logN)。因为对于N个元素，一共有N!种排列方式。可以想象一颗决策树，树的叶子节点个数为N!，而数的深度即为决策（比较）的次数。根据斯特林公式，这个深度约为O(N*logN)。
基于比较的排序虽然效率有时候没有基于非比较的排序效率高，但是有更好的通用性，下面会重点介绍基于比较的排序算法。基于比较的排序算法还可以分成两种，稳定和非稳定的。排序算法的稳定性在某些场合下非常重要。那么什么是稳定的排序算法呢？简单讲就是，如果两个元素待比较的属性值相等，那么原来排在前面的，排序后必须还排在前面。应该已经很明确了哈。下面具体看一些排序算法。
1、直接插入排序（稳定）
直接插入排序比较简单，每次都从序列中取出一个元素，放入前面已经排好的序列的合适位置，算法的复杂度为O(N^2)。
public void sort(int[] nums) {
for(int i = 1; i < nums.length; i++){
if(nums[i] < nums[i-1]){
int temp = nums[i];
int j = i-1;
for(; j >= 0; j--){
if(nums[j] > temp){
nums[j+1] = nums[j];
} else{
break;
}
}
nums[j+1] = temp;
}
}
}
下面是示意图：
2、希尔排序（非稳定）
希尔排序的基本思想是，先将待排序序列分割成若干子序列，分别进行直接希尔排序，当整个序列中数据呈现“基本有序”时，再对全体进行一次插入排序。复杂度不太好算，介于O(N^2) 和O(N^1.3)之间吧。
public void sort(int[] nums) {
for (int step = nums.length / 2; step >= 1; step/=2) {
for(int i = step; i < nums.length; i++){
if(nums[i] < nums[i-step]){
int temp = nums[i];
int j = i - step;
for(; j >= 0; j -= step){
if(nums[j] > temp){
nums[j+step] = nums[j];
} else{
break;
}
}
nums[j+step] = temp;
}
}
}
}
下面是示意图：
3、冒泡排序(稳定)
冒泡排序就像名字一样，每次选出最大的元素（向后冒泡）或者最小元素（向前冒泡）。下面的算法是向前冒泡，相当于每次都确定剩余元素中最小元素的位置。算法复杂度O(N^2)。
public void sort(int[] nums) {
int n = nums.length;
for(int i = 0; i < n-1; i++){
boolean swap = false;
for(int j = n-1; j >i; j--){
if(nums[j-1] > nums[j]){
int temp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = temp;
swap = true;
}
}
if(!swap){
break;
}
}
}
下面是示意图：
4、快速排序（非稳定）
快速排序是一个比较快的排序算法，是对冒泡排序的一种改进。基本的思想就是分治法。随机选择一个元素，剩余元素都与其比较，大的放其后边，小的放其前边。然后分别对其前后元素进行排序。
def quick_sort(sort_list):
left_list, middle_list, right_list = [], [], []
if len(sort_list) == 0:
return []
pivot = sort_list[0]
for item in sort_list:
if item < pivot:
left_list.append(item)
elif item == pivot:
middle_list.append(item)
else:
right_list.append(item)
return quick_sort(left_list) + middle_list + quick_sort(right_list)
def quick_sort_inplace_helper(sort_list, start, end):
if start == end:
return start
pivot = sort_list[start]
i = start + 1
j = start + 1
while j <= end:
if sort_list[j] < pivot:
sort_list[j], sort_list[i] = sort_list[i], sort_list[j]
i += 1
j += 1
sort_list[i-1], sort_list[start] = sort_list[start], sort_list[i-1]
return i - 1
def quick_sort_inplace(sort_list, start, end):
if start >= end:
return
index = quick_sort_inplace_helper(sort_list, start, end)
quick_sort_inplace(sort_list, start, index - 1)
quick_sort_inplace(sort_list, index+1, end)
public void sort(int[] nums) {
if (nums == null || nums.length <= 1)
return;
quickSort(nums, 0, nums.length - 1);
}
public void quickSort(int[] a, int p, int r) {
if (p < r) {
int q = partition(a, p, r);
quickSort(a, p, q);
quickSort(a, q + 1, r);
}
}
public int partition(int[] a, int p, int r) {
int x = a[p];
int i = p - 1;
int j = r + 1;
while (true) {
i++;
while (i < r && a[i] < x)
i++;
j--;
while (j > p && a[j] > x)
j--;
if (i < j)
swap(a, i, j);
else
return j;
}
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
下面是示意图：
5、简单选择排序（不稳定）
简单选择排序的基本思想是，每一趟在后面待排元素中选取关键字最小的元素，放在剩余元素的最前面。直到所有元素排完。
public void sort(int[] nums) {
int n = nums.length;
for(int i = 0; i < n-1; i++){
int minIndex = i;
for(int j = i+1; j < n; j++){
if(nums[j] < nums[minIndex]){
minIndex = j;
}
}
if(minIndex != i){
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
}
下面是示意图：
6、堆排序（不稳定）
堆排序是一种树形选择排序方法，在排序过程中，将待排序数组视为一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大的元素。
def heap_sort_adjust_down(sort_list, start, length):
i = start * 2 + 1
while i < length:
if i + 1 < length and sort_list[i] < sort_list[i+1]:
i += 1
if sort_list[start] >= sort_list[i]:
break
sort_list[i], sort_list[start] = sort_list[start], sort_list[i]
start = i
i = i * 2 + 1
def heap_sort_build_max_heap(sort_list):
length = len(sort_list)
i = int(length / 2) - 1 if length % 2 == 0 else int(length / 2)
while i >= 0:
heap_sort_adjust_down(sort_list, i, length-1)
i -= 1
def heap_sort(sort_list):
heap_sort_build_max_heap(sort_list)
for i in range(len(sort_list)-1, 0, -1):
sort_list[0], sort_list[i] = sort_list[i], sort_list[0]
heap_sort_adjust_down(sort_list, 0, i)
public void sort(int[] nums) {
buildMaxHeap(nums);
for (int i = nums.length - 1; i > 0; i--) {
int temp = nums[i];
nums[i] = nums[0];
nums[0] = temp;
adjustDown(nums, 0, i);
}
}
private void buildMaxHeap(int[] nums) {
int len = nums.length;
for (int i = len % 2 == 0 ? len / 2 - 1 : len / 2; i >= 0; i--) {
adjustDown(nums, i, len);
}
}
private void adjustDown(int[] nums, int k, int len) {
int temp = nums[k];
for (int i = 2 * k + 1; i < len; i = 2 * i + 1) {
if (i < len - 1 && nums[i] < nums[i + 1]) {
i++;
}
if (temp >= nums[i])
break;
else {
nums[k] = nums[i];
k = i;
}
}
nums[k] = temp;
}
下面是示意图：
7、归并排序（稳定）
归并排序的思想也是分治，归并的含义是讲两个已经排好的序列整合成一个排好的序列。通过不断递归，就可以实现对无序序列的排序。
public class MergeSort {
private int[] numbers;
private int[] helper;
private int number;
public void sort(int[] values) {
this.numbers = values;
number = values.length;
this.helper = new int[number];
mergesort(0, number - 1);
}
private void mergesort(int low, int high) {
// check if low is smaller then high, if not then the array is sorted
if (low < high) {
// Get the index of the element which is in the middle
int middle = low + (high - low) / 2;
// Sort the left side of the array
mergesort(low, middle);
// Sort the right side of the array
mergesort(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
}
private void merge(int low, int middle, int high) {
// Copy both parts into the helper array
for (int i = low; i <= high; i++) {
helper[i] = numbers[i];
}
int i = low;
int j = middle + 1;
int k = low;
// Copy the smallest values from either the left or the right side back
// to the original array
while (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
numbers[k] = helper[i];
i++;
} else {
numbers[k] = helper[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= middle) {
numbers[k] = helper[i];
k++;
i++;
}
}
}
下面是示意图：
8、Introsort（非稳定）
这是一个复合排序算法，当规模较大时使用快速排序，当规模较小时使用堆排序。为什么要这样做呢？直接看wiki上的原文吧。
Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. This combines the good parts of both algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort. Since both algorithms it uses are comparison sorts, it too is a comparison sort.
简单说，就是希望在数据规模较大时达到快速排序的效率，同时又希望优化快速排序最差情况下的时间复杂度，所以规模较小时使用了堆排序。
9、Timsort（稳定）
这也是一个复合排序算法，也是java jdk7内置排序算法（Arrays.sort(), Collections.sort())。其基本思想是利用了数据的局部有序特点，进行排序。当两个局部有序的子序列长度差不多时，使用merge排序，如果长度相差很大时，使用插入排序。