如果有一个数组，元素间可以进行比较（>、==、<），要让数组的元素按照大小顺序重新排序，就需要排序算法。
排序算法的特性
- 稳定性
- in place 原地排序，即排序算法不会占用过多的内存空间（比如，如果算法用临时变量
temp来交换a[i]和a[j]就是in place的）。
主要需要了解的排序算法
| 算法 | 时间复杂度 | 稳定排序 | 原地排序 |
|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | √ | √ |
| 插入排序 | $O(n^2)$ | √ | √ |
| 选择排序 | $O(n^2)$ | × | √ |
| 快速排序 | $O(nlog_n)$ | × | √ |
| 归并排序 | $O(n^2)$ | √ | × |
| 计数排序 | $O(nlog_{(n/m)})$，m为桶的个数。桶越多越好，只有一个桶时退化为$O(nlog_n)$ |
√ | × |
| 桶排序 | $O(n)$ | √ | × |
| 基数排序 | $O(dn)$，d是维度 |
√ | × |
- 原地排序（sorted in place）： 指空间复杂度为$O(1)$的算法。
- 排序算法稳定性： 等值元素在排序后，先后顺序不变。
- 逆序度（inversion） 两个元素如果未从小到大排序，则算是一组逆序数。如
E X A M P L E的逆序度为11，有如下11个逆序对E-A, X-A, X-M, X-P, X-L, X-E, M-L, M-E, P-L, P-E, L-E。
冒泡排序、插入排序、选择排序、希尔排序
选择排序
选择排序： 类似插入排序，游标i左侧已经排序好、右侧未排序好。从右侧中找到最小元素（假设为$A_j$），和第1个元素交换，然后游标加1；然后找出第2~n个元素中最小的元素，和数组第2个元素交换位置；一直到最后一个元素。
每次都是选出剩余未排列元素中最小的元素，所以叫选择排序。
这不是一个稳定排序，比如对5,8,5,2,9进行选择排序，会先交换第一个5和2，这样两个5的位置就改变了。
选择排序只需要交换n次元素，其它算法都是$O(nlog_n)$或者$O(n^2)$，当然选择排序算法的比较次数是$O(n^2)$。
python实现如下：
# Traverse through all array elements
for i in range(len(A)):
# Find the minimum element in remaining
# unsorted array
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
# Swap the found minimum element with
# the first element
A[i], A[min_idx] = A[min_idx], A[i]
递归的描述方式： 对于从1~n的每个i，将第i小的元素放到arr[i]。
插入排序
插入排序： 游标i将数据分为左侧的已排序部分（$A_0$到$A_i$）和右侧的未排序部分（$A_{i+1}$到$A_n$），将$A_{i+1}$的元素插入到左侧的合适位置，然后游标右移。将游标从0移动到n然后排序结束。
插入排序优于冒泡排序，因为每次冒泡排序交换元素$A_i$和$A_{i+1}$都需要进行3次赋值语句（需要tmp=A[i]; A[i]=A[i+1];A[i+1]=tmp;），而插入排序只需要1次赋值语句。
扑克牌手一般都会使用该方式来排序手牌。
python实现如下：
# Function to do insertion sort
def insertionSort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
递归的描述方式： 对于从1~n的每个i，每次将新的元素插入到合适的位置使1~i的元素保持有序。
希尔排序
插入排序每次交换操作只能移动相邻的元素，如果元素离最终位置较远，会需要过多的交换操作。希尔排序据此对插入排序进行改进。
h-sort指的是，对于指定的递增值h值比如3，从数组任意一个索引处开始递增（如2、5、8、11..），都已经排序好。 希尔排序先用较大的递增值进行h-sort，直到h减到1。
java实现如下：
public class ShellSort {
public static void sort(int[] array) {
//希尔排序的增量
int d = array.length;
while (d > 1) {
// 使用希尔增量的方式，即每次折半
d = d / 2;
// note: 当d=1时，就是标准的插入排序。 这样来理解这段代码就清晰些了
for (int x = 0; x < d; x++) {
for (int i = x + d; i < array.length; i = i + d) {
int temp = array[i];
int j;
for (j = i - d; j >= 0 && array[j] > temp; j = j - d) {
// 1,3,8,13 7
array[j + d] = array[j];
}
array[j + d] = temp;
}
}
}
}
public static void main
(String[] args) {
int[] array = {5, 3, 9, 12, 6, 1, 7, 2, 4, 11, 8, 10};
sort(array);
System.out.println(Arrays.toString(array));
}
}
冒泡排序
对于相邻两个元素（$A_0$和$A_1$、$A_1$和$A_2$，以此类推…），如果$a_j>a_{j+1}$，则交换j和j+1位置的数据，这样第一轮冒泡会将最大的元素冒泡到$A_n$、第二轮会将第二大的元素冒泡到$A_{n-1}$….
归并和快排
归并排序和快排都使用了递归，前者是将数组不断分成子数组排序，然后再合并各个结果。而快排则是选择一个分区点元素p，将小于p的元素放在左边，大于p的元素放在右边，分成少于p、p、大于p三个区间，再对少于p和大于p的区间进行快排，当区间间隔1时表示排序完毕。
归并排序不是原地排序，所以应用没有快排广泛。
归并排序
两个已经排序好的数组可以很快的合并成一个更大的数组。归并排序(merge sort)正是基于此：为了排序一个数组，先对分数组为两个子数组，排序（递归过程）两个子数组，再合并得到结果。
这是分治算法的典型：我们将一个问题分成多个子问题，通过解决子问题，合并子问题结果得到最终结果。
自顶向下
自顶向上的归并排序是递归调用sort方法并merge结果。时间复杂度$O(Nlog_N)$，空间复杂度$O(N)$。
python实现如下：
# Python program for implementation of MergeSort
def mergeSort(arr):
if len(arr) >1:
mid = len(arr)//2 #Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves
mergeSort(L) # Sorting the first half
mergeSort(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i+=1
else:
arr[k] = R[j]
j+=1
k+=1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i+=1
k+=1
while j < len(R):
arr[k] = R[j]
j+=1
k+=1
自底向上
自顶向下的mergesort是将规模为n的问题分解成2个规模为n/2的子问题，再分解成规模为n/4的子问题，直到规模为1。自顶向上的mergesort是将问题分解为规模为1的子问题，再合并成规模为2、4…的子问题。
自顶向下和自底向上的mergesort的数组访问、比较序列相同，只不过换了顺序。
自顶向下的mergesort算法是将大问题分解成小的子问题，然后将小问题分解成更小的子问题，递归地解决；自底向下的mergesort算法是将大问题分解成最小的子问题（size为1），然后逐渐合并成大的子问题（size为2、4…），直到得到最终结果。
python实现如下：
def merge(left, right):
if not len(left) or not len(right):
return left or right
result = []
i, j = 0, 0
while (len(result) < len(left) + len(right)):
if left[i] < right[j]:
result.append(left[i])
i+= 1
else:
result.append(right[j])
j+= 1
if i == len(left) or j == len(right):
result.extend(left[i:] or right[j:])
break
return result
def mergesort(list):
if len(list) < 2:
return list
middle = len(list)/2
left = mergesort(list[:middle])
right = mergesort(list[middle:])
快排
quicksort是应用最广泛的排序算法。 它相比mergesort的优点是容易实现，且为原地排序，只需要一个比较小的stack。
mergesort是先递归调用两次，再操纵整个数组；quicksort是先操纵整个数组，再递归调用两次。
python实现如下：
# This function takes last element as pivot, places
# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot
def partition(arr,low,high):
i = ( low-1 ) # index of smaller element
pivot = arr[high] # pivot
for j in range(low , high):
# If current element is smaller than or
# equal to pivot
if arr[j] <= pivot:
# increment index of smaller element
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index
# Function to do Quick sort
def quickSort(arr,low,high):
if low < high:
# pi is partitioning index, arr[p] is now
# at right place
pi = partition(arr,low,high)
# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
# Driver code to test above
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %arr[i]),
# This code is contributed by Mohit Kumra
桶排序、计数排序、基数排序
三种时间复杂度为$O(N)$的排序算法，为线性排序（linear sorting。之所以能做到线性的时间复杂度，是因为这些排序算法不是基于比较的，使用条件比较苛刻。
桶排序
桶排序（bucket sort）的核心是桶，将要排序的数据按照数据大小放到多个有序的桶中，然后分别在桶中进行排序（这里可能会使用到比较算法）。当每个桶中的数据都排序好时，全部数据就排序好了。
举例说明：比如将金额在0-50之间的订单，分别放到0-9、10-19…40-49的桶中，每个桶中的元素使用快排，然后合并结果。
时间复杂度分析：将n个数据分到m个桶中，理想情况下每个桶中有k=n/m个元素。每个桶中使用快排，时间复杂度为$O(k·log_k)$，m个桶的时间复杂度就是$O(m·k·log_k)$即$O(n·log_{n/m})$。当桶的个数m接近数据个数n时，$log_{n/m}$就会比较小，时间复杂度就是$O(n)$。
可以看出，使用桶排序需要满足条件：1） 要排序的数据能够方便的划分到m个桶中，且桶有大小顺序； 2）数据在多个桶间分布均匀，如果不均匀，在极端情况下（绝大部分数据在一个桶中）时间复杂度会退化到$O(n·log_n)$。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
计数排序
计数排序Counting sort。计数这一称呼源自数据合并到最终数组的过程，可以见示例。
基数排序
对于11位的手机号，可以分割成11个独立的位，对每一个位使用桶排序或者计数排序。