整理了下一些常用的排序算法。
一、冒泡排序
冒泡排序：一排n个元素的序列，通过两两比较交换位置保持大的(或者小的)在右侧，这样经过n-1轮这样的操作完成排序。
源码：
#define SWAP(a,b) {a=a+b;b=a-b;a=a-b;}
// 冒泡排序
void BubbleSort(int src[], int n)
{
for (int i = 0; i <= n - 2; i++)
{
for (int j = 0; j <= n - 2 - i; j++)
{
if (src[j] > src[j + 1])
{
SWAP(src[j], src[j+1])
}
}
}
}
空间复杂度：O(1)
时间复杂度：最好：O(n)，最坏O(n^2)，平均O(n^2)
冒泡排序是稳定排序
二、选择排序
选择排序：一排n个元素的序列，每次通过两两比较，选出最大的索引与最右侧的元素交换，这样第一轮排出最大的元素在最右侧，第二轮选出第二大的元素在最右侧左移一个元素，这样经过n-1轮完成排序。
源码：
#define SWAP(a,b) {a=a+b;b=a-b;a=a-b;}
// 选择排序
void SelectionSort(int src[], int n)
{
for (int i = 0; i <= n - 2; i++)
{
int key = 0;
for (int j = 0; j <= n - 2 - i; j++)
{
if (src[key] < src[j])
key = j;
}
if (src[key]> src[n - 1 - i])
{
SWAP(src[key], src[n-1-i])
}
}
}
空间复杂度：O(1)
时间复杂度：最好：O(n)，最坏O(n^2)，平均O(n^2)
选择排序是不稳定排序
三、插入排序
插入排序：一排n个元素的序列，从左向右遍历，遍历的每一个元素与它左侧元素逐一比较，找到刚好小于它的元素插入到后面，比他大的逐一向右侧移动一个元素，直至遍历完毕完成排序。
源码：
// 插入排序
void InsertSort(int src[], int n)
{
for (int pt = 1; pt < n; pt++)
{
int key = src[pt];
int idx = pt - 1;
while (idx >= 0 && src[idx] > key)
{
src[idx + 1] = src[idx];
idx--;
}
src[idx + 1] = key;
}
}
空间复杂度：O(1)
时间复杂度：最好：O(n)，最坏O(n^2)，平均O(n^2)
插入排序是稳定排序
四、快速排序
快速排序：快速排序将n个元素的序列通过递归的方法，每次规定一个关键值，将小于等于关键值的元素放置到关键值左侧，大于关键值的元素放置到关键值右侧，这样直到递归完毕完成排序。
源码：
#define SWAP(a,b) {a=a+b;b=a-b;a=a-b;}
//快速排序
void QuickSort(int src[],int begin, int end)
{
if (begin >= end)
return;
int key = src[begin];
int l = begin;
int r = end;
while (l < r)
{
while (src[l] <= key && l < r)
l++;
while (src[r] > key && r > l)
r--;
if (r > l)
SWAP(src[l], src[r])
}
if (r > begin)
SWAP(src[begin], src[r])
QuickSort(src, begin, r-1);
QuickSort(src, r+1, end);
}
空间复杂度：O(log2n)
时间复杂度：最好：O(nlog2n)，最坏：O(n^2)，平均：O(nlog2n)
快速排序是不稳定排序
五、归并排序
归并排序：一个n个元素的序列，进行递归，每次递进时平均拆分成两个序列，然后对拆分后的序列进行排序，最后对排好序的两个序列进行合并。这样递归结束完成排序。
源码：
// 归并排序
void Combine(int src[], int begin, int end)
{
int mid = (begin + end) / 2;
int p = begin;
int q = mid + 1;
int k = 0;
int* tmp = new int[end - begin + 1];
while (p <= mid && q <= end)
{
if (src[p] <= src[q])
tmp[k++] = src[p++];
else
tmp[k++] = src[q++];
}
while (p <= mid)
tmp[k++] = src[p++];
while (q <= end)
tmp[k++] = src[q++];
//复制到原数组
for (int i = 0; i < end - begin + 1; i++)
{
src[begin + i] = tmp[i];
}
delete[] tmp;
}
void MergeSort(int src[], int begin, int end)
{
if (begin >= end)
return;
int mid = (begin + end) / 2;
MergeSort(src, begin, mid);
MergeSort(src, mid + 1, end);
Combine(src, begin, end);
}
空间复杂度：O(nlog2n)
时间复杂度：最好，最坏，平均：O(nlog2n)
归并排序是稳定排序
六、堆排序
堆排序：堆排序是将一个n个元素的序列描述成一个二叉树的形式，建立大根堆(每个根节点都不小于它的叶子节点的值)，或者小根堆(每个根节点都不大于它的叶子节点的值)，然后通过n-1次调堆完成排序。
源码：
#define LEFTCHILD(i) (i * 2 + 1)
#define RIGHTCHILD(i) (i * 2 + 2)
#define SWAP(a,b) {a=a+b;b=a-b;a=a-b;}
//调堆
void MaxHeap(int src[], int heapsize, int pos)
{
int lastest = pos;
while (1)
{
int l = LEFTCHILD(pos);
int r = RIGHTCHILD(pos);
if (l < heapsize && src[lastest] < src[l])
lastest = l;
if (r < heapsize && src[lastest] < src[r])
lastest = r;
if (lastest == pos)
break;
SWAP(src[pos], src[lastest]);
pos = lastest;
}
}
// 堆排序
void HeapSort(int src[], int heapsize)
{
//建堆
for (int k = heapsize / 2 - 1; k >= 0; k--)
{
MaxHeap(src, heapsize, k);
}
//调堆
for (int k = heapsize - 1; k > 0; k--)
{
SWAP(src[0], src[k]);
heapsize--;
MaxHeap(src, heapsize, 0);
}
}
空间复杂度：O(1)
时间复杂度：最好：O(nlog2n)，最坏：O(nlog2n)，平均：O(nlog2n)
堆排序是不稳定排序
七、希尔排序
希尔排序：希尔排序是插入排序的一种优化，是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，就变成了直接插入排序，算法终止。
源码：
//希尔排序
void ShellSort(int src[], int n)
{
for (int gap = n / 2; gap > 0; gap = gap / 2)
{
for (int pt = gap; pt < n; pt++)
{
int key = src[pt];
int idx = pt - gap;
while (idx >= 0 && src[idx] > key)
{
src[idx + gap] = src[idx];
idx = idx - gap;
}
src[idx + gap] = key;
}
}
}
空间复杂度：O(1)
时间复杂度：最好，平均：O(nlog2n)，最坏O(n^2)
希尔排序是不稳定排序
