目录
排序算法比较
冒泡排序
时间复杂度O(N^2)
工作原理：
1.比较相邻两个元素，如果前者比后者大就交换
2.对第0个到第n-1个数重复步骤1，使得最大的数到达数组的末尾
3.重复以上步骤，直到比较完
c++版:
```c++
class BubbleSort {
public:
int* bubbleSort(int* A, int n) {
<pre><code> for(int i=0;i <= n;i++)
for(int j = n-1;j > i;j--){
if(A[j-1]>A[j])
{
swap(A[j],A[j-1]);
}
}
return A;
// write code here
}
</code></pre>
};
<pre><code class=" line-numbers">python版：
```python
def bubble_sort(arry):
n = len(arry) #获得数组的长度
for i in range(n):
for j in range(1,n-i):
if arry[j-1] > arry[j] : #如果前者比后者大
arry[j-1],arry[j] = arry[j],arry[j-1] #则交换两者
return arry
选择排序
时间复杂度O(N^2)
工作原理：
1.在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3.以此类推，直到所有元素均排序完毕。
c++版:
```c++
class SelectionSort {
public:
int* selectionSort(int* A, int n) {
for(int i = 0;i<n;i++){
int min = i;
for(int j=i+1;j<n;j++) //循环扫描找到值最小的下标
{
if(A[j]<A[min])
min= j;
}
swap(A[i],A[min]);
}
return A;
}<br />
};
<pre><code class=" line-numbers">python 版：
```python
def select_sort(ary):
n = len(ary)
for i in range(0,n):
min = i #最小元素下标标记
for j in range(i+1,n):
if ary[j] < ary[min] :
min = j #找到最小值的下标
ary[min],ary[i] = ary[i],ary[min] #交换两者
return ary
插入排序
时间复杂度O(N^2)
工作原理：
对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
c++版:
```c++
class InsertionSort {
public:
int* insertionSort(int* A, int n) {
// write code here
int i;
for(i=1;i<n;i++)
{
int j;<br />
int temp = A[i];
for(j=i;j>0;j--) //从后往前找插入位置
{<br />
if(A[j-1] > temp )
{
A[j] = A[j-1];
}
else
{
break;
}
}
<pre><code> A[j]=temp;
}
return A;
</code></pre>
}
};
<pre><code class=" line-numbers">python版：
```python
def insert_sort(ary):
n = len(ary)
for i in range(1,n):
if ary[i] < ary[i-1]:
temp = ary[i]
index = i #待插入的下标
for j in range(i-1,-1,-1): #从i-1 循环到 0 (包括0)
if ary[j] > temp :
ary[j+1] = ary[j]
index = j #记录待插入下标
else :
break
ary[index] = temp
return ary
归并排序
时间复杂度为O(N*logN)
工作原理：
归并排序的思想就是先递归分解数组，再合并数组。
让数组中的每个数单独成为长度为1的有序的区间，然后让相邻的长度为1 的有序区间进行合并，得到最大长度为2的有序区间，接下来再把相邻有序区间进行合并，得到最大长度为4的有序区间，依次进行下去，直到合并成一个有序区间。
c++版：
```c++
class MergeSort {
public:
void merge(int* A, int start, int mid, int end){
for(int i = mid + 1; i <= end; i++) {
for(int j=i;j>start;j--){
if(A[j]<A[j-1]){
swap(A[j],A[j-1]);
}
}
<pre><code> }
}
void myMergeSort(int* A, int start, int end){
if(start < end) {
int mid = (start + end )/2;
myMergeSort(A, start, mid);
myMergeSort(A, mid+1, end);
merge(A, start, mid, end);
}
}
int* mergeSort(int* A, int n) {
// write code here
myMergeSort(A,0,n-1);
return A;
}
</code></pre>
};
<pre><code class=" line-numbers">python版：
```python
def merge_sort(ary):
if len(ary) <= 1 : return ary
num = int(len(ary)/2) #二分分解
left = merge_sort(ary[:num])
right = merge_sort(ary[num:])
return merge(left,right) #合并数组
def merge(left,right):
'''合并操作，
将两个有序数组left[]和right[]合并成一个大的有序数组'''
l,r = 0,0 #left与right数组的下标指针
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
快速排序
时间复杂度为O(N*logN)
工作原理：
1.从数列中挑出一个元素作为基准数。
2.分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。
3.再对左右区间递归执行第二步，直至各区间只有一个数。
c++版：
```c++
void quickSort(int arr[], int left, int right){
int index = partition(arr, left, right);
if (left < index - 1){
quickSort(arr, left, index - 1);
}
if (index < right){
quickSort(arr, index, right);
}
}
int partition(int arr[], int left, int right){
int pivot = arr[(left + right) / 2];
while (left <= right){
while (arr[left] < pivot) left++;
while (arr[right] > pivot) right--;
<pre><code> // Swap elements, and move left and right indices
if (left <= right){
swap(arr, left, right);
left++;
right--;
}
}
return left;
</code></pre>
}
<pre><code class=" line-numbers">python版：
```python
def quick_sort(ary):
return qsort(ary,0,len(ary)-1)
def qsort(ary,left,right):
#快排函数，ary为待排序数组，left为待排序的左边界，right为右边界
if left >= right : return ary
key = ary[left] #取最左边的为基准数
lp = left #左指针
rp = right #右指针
while lp < rp :
while ary[rp] >= key and lp < rp :
rp -= 1
while ary[lp] <= key and lp < rp :
lp += 1
ary[lp],ary[rp] = ary[rp],ary[lp]
ary[left],ary[lp] = ary[lp],ary[left]
qsort(ary,left,lp-1)
qsort(ary,rp+1,right)
return ary
堆排序
时间复杂度为O(N*logN)
工作原理：
1.构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。
2.堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap1交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。
3.最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点。
python版：
def heap_sort(ary) :
n = len(ary)
first = int(n/2-1) #最后一个非叶子节点
for start in range(first,-1,-1) : #构造大根堆
max_heapify(ary,start,n-1)
for end in range(n-1,0,-1): #堆排，将大根堆转换成有序数组
ary[end],ary[0] = ary[0],ary[end]
max_heapify(ary,0,end-1)
return ary
#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置，end为调整边界
def max_heapify(ary,start,end):
root = start
while True :
child = root*2 +1 #调整节点的子节点
if child > end : break
if child+1 <= end and ary[child] < ary[child+1] :
child = child+1 #取较大的子节点
if ary[root] < ary[child] : #较大的子节点成为父节点
ary[root],ary[child] = ary[child],ary[root] #交换
root = child
else :
break
希尔排序
时间复杂度为O(N*logN)
工作原理：
希尔排序，也称递减增量排序算法，实质是分组插入排序。由 Donald Shell 于1959年提出。希尔排序是非稳定排序算法。
希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：
13 14 94 33 82
5 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序（此时退化到简单的插入排序了）。
python版：
def shell_sort(ary):
n = len(ary)
gap = round(n/2) #初始步长 , 用round四舍五入取整
while gap > 0 :
for i in range(gap,n): #每一列进行插入排序 , 从gap 到 n-1
temp = ary[i]
j = i
while ( j >= gap and ary[j-gap] > temp ): #插入排序
ary[j] = ary[j-gap]
j = j - gap
ary[j] = temp
gap = round(gap/2) #重新设置步长
return ary
计数排序
时间复杂度为O(N)
工作原理：
对排序数组按元素进行计数。使用前提是需要先知道待排序数组的元素范围，将这些一定范围的元素置于新数组中，新数组的大小为待排序数组中最大元素与最小元素的差值。
定新数组大小——找出待排序的数组中最大和最小的元素
统计次数——统计数组中每个值为i的元素出现的次数，存入新数组C的第i项
对统计次数逐个累加——对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组——将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
其中反向填充主要是为了避免重复元素落入新数组的同一索引处。
def countingSort(A, n):
# write code here
maxVal, minVal = max(A), min(A)
hash = [0] * (maxVal - minVal + 1)
for a in A:
hash[a - minVal] += 1
A = []
for i, v in enumerate(hash):
A += [minVal + i] * v
return A
基数排序
时间复杂度为O(N)
工作原理：
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
c++版：
```c++
int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
int maxData = data[0]; ///< 最大数
/// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
for (int i = 1; i < n; ++i)
{
if (maxData < data[i])
maxData = data[i];
}
int d = 1;
int p = 10;
while (maxData >= p)
{
//p <em>= 10; // Maybe overflow
maxData /= 10;
++d;
}
return d;
/</em> int d = 1; //保存最大的位数
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
p <em>= 10;
++d;
}
}
return d;</em>/
}
void radixsort(int data[], int n) //基数排序
{
int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int[10]; //计数器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //进行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix * 10;
}
delete []tmp;
delete []count;
}
<pre><code class=" line-numbers"><br />python版
```python
import math
def sort(a, radix=10):
"""a为整数列表， radix为基数"""
K = int(math.ceil(math.log(max(a), radix))) # 用K位数可表示任意整数
bucket = [[] for i in range(radix)] # 不能用 [[]]*radix
for i in range(1, K+1): # K次循环
for val in a:
bucket[val%(radix**i)/(radix**(i-1))].append(val) # 析取整数第K位数字 （从低到高）
del a[:]
for each in bucket:
a.extend(each) # 桶合并
bucket = [[] for i in range(radix)]
