有n个记录的序列
,顺序与其前面记录的关键字
进行比较，将所有关键字大于的记录依次向后移动一个位置，直到遇到一个关键字小于或等于的记录，此时该记录后面一定有空位置，将第i个记录插入到该空位置即可。
#include
#include
using namespace std;
void Printf(int* a,size_t n)
{
for (size_t i = 0; i < n; ++i)
{
cout << a[i] << " ";
}
cout << endl;
}
void InsertSort(int* a, size_t n)
{
assert(a);
for (int i = 0; i < n - 1; ++i)
{
int end = i;
int tmp = a[end + 1];
for (; end >= 0; --end)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void TestInsertSort()
{
int a[] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };
Printf(a, sizeof(a) / sizeof a[0]);
InsertSort(a, sizeof(a) / sizeof a[0]);
Printf(a, sizeof(a) / sizeof a[0]);
}
void ShellSort(int* a, size_t n)
{
assert(a);
int gap = n;
while (gap > 1)
{
gap = (gap / 3) + 1;
for (size_t i = 0; i < n-gap; ++i)
{
int end = i;
int tmp = a[end + gap];
for (; end >= 0; end -= gap)
{
if (a[end]>tmp)
{
a[end + gap] = a[end];
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
void TestShellSort()
{
int a[] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };
Printf(a, sizeof(a) / sizeof a[0]);
ShellSort(a, sizeof(a) / sizeof a[0]);
Printf(a, sizeof(a) / sizeof a[0]);
}运行结果：
注意：当子序列记录间的间隔为d时，共有d个子序列，需要对d个子序列分别进行插入排序。在具体实现时，并不是先对一个子序列完成插入排序，再对另外一个子序列进行插入排序，而是从第一个子序列的第二个记录开始，顺序扫描整个待排序记录序列，当前记录属于哪个子序列，就在哪一个子序列中进行插入排序。（各子序列的记录将轮流出现）
（3）选择排序
算法思想：第一趟排序时，从第一个记录开始，通过n-1次关键字的比较，从n个记录中选出关键字最小记录，并和第一个记录进行交换；第二趟排序时，从第二个记录开始，通过n-2次关键字的比较，从n-1个记录中选出关键字最小记录，并和第二个记录进行交换；如此反复，经过n-1趟排序，将n-1个记录排到位，剩下的一个直接排在最后。
该方法一次选择两个记录，进行排序。
依次类推，即可完成排序。
代码实现：
void SelectSort(int* a, size_t n)
{
assert(a);
size_t begin = 0, end = n - 1;
while (begin < end)
{
size_t min = begin, max = begin;
for (size_t i = begin; i <= end; ++i)
{
if (a[i]
a[max])
{
max = i;
}
}
swap(a[begin], a[min]);
if (begin == max)
{
max = min;
}
swap(a[end], a[max]);
++begin;
--end;
}
}
void TestInsertSort()
{
int a[] = { 2, 5, 4, 9, 3, 5, 8, 7, 1, 5 };
Printf(a, sizeof(a) / sizeof a[0]);
SelectSort(a, sizeof(a) / sizeof a[0]);
Printf(a, sizeof(a) / sizeof a[0]);
}
（4）堆排序
算法思想：把待排序的记录的关键字存放在一个数组中，将其看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录作为二叉树的根，接下来依次逐层从左到右顺序排列，最终对
代码实现：
void AdjustDown(int* a, int n, size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n&&a[child + 1] > a[child])
{
++child;
}
if (a[child]>a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void heapSort(int* a, size_t n) //升序建大堆
{
assert(a);
for (int i = (n - 2) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
size_t end = n - 1;
while (end > 0)
{
swap(a[0], a[end]);
AdjustDown(a, end, 0);
--end;
}
}
void TestInsertSort()
{
int a[] = { 2, 5, 4, 9, 3, 5, 8, 7, 1, 0 };
Printf(a, sizeof(a) / sizeof a[0]);
heapSort(a, sizeof(a) / sizeof a[0]);
Printf(a, sizeof(a) / sizeof a[0]);
}运行结果：
(5)冒泡排序
算法思想：通过对相邻的数据元素进行交换，逐步将待排序序列变成有序序列的过程。以升序为例，在第一趟冒泡排序中，从第一个记录开始，扫描整个待排序记录序列，若相邻的两个记录逆序，则交换位置，然后进行第二趟排序，对前n-1个记录进行同样的操作，其结果是使次大的记录被放在第n-1个记录的位置上。，如此反复，每一趟排序都将一个记录排到位，直到剩下一个最小的记录。若在某一趟冒泡排序过程中，没有发现一个逆序，则可直接结束整个排序过程。
代码实现：
void BubbleSort(int* a, size_t n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
size_t first = 0;
size_t second = 1;
while (second < end)
{
if (a[first]>a[second])
{
swap(a[first], a[second]);
}
++first;
++second;
}
}
}
void TestInsertSort()
{
int a[] = { 2, 5, 4, 9, 3, 5, 8, 7, 1, 0 };
Printf(a, sizeof(a) / sizeof a[0]);
BubbleSort(a, sizeof(a) / sizeof a[0]);
Printf(a, sizeof(a) / sizeof a[0]);
}
（6）快速排序
从待排序记录序列中选取一个记录为枢轴，其关键字设为
算法思想：
通过一次划分后，就以关键字为
快速排序可以有以下三种方法实现：
（a）左右指针法
代码实现：
int PartSort1(int* a, int begin, int end)
{
int key = end;
while (begin < end)
{
while (begin
=a[key])
{
--end;
}
if (begin < end)
{
swap(a[begin], a[end]);
}
}
swap(a[begin], a[key]);
return begin;
}
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left < right)
{
int div = PartSort1(a, left, right);
QuickSort(a, left, div - 1);
QuickSort(a, div + 1, right);
}
}
（2）挖坑法
代码实现：
//挖坑法
int PartSort2(int* a, int begin, int end)
{
int key = a[end];
while (begin < end)
{
while (begin < end && a[begin] <= key)
{
++begin;
}
if (begin
= key)
{
--end;
}
if (begin
运行结果： 
（3）前后指针
代码实现：
//前后指针
int PartSort3(int* a, int begin, int end)
{
int key = end;
int cur = begin;
int prev = cur - 1;
while (cur < end)
{
if (a[cur] < a[key] && ++prev != cur)
{
swap(a[prev], a[cur]);
}
++cur;
}
swap(a[++prev], a[key]);
return prev;
}
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left < right)
{
int div = PartSort3(a, left, right);
QuickSort(a, left, div - 1);
QuickSort(a, div + 1, right);
}
}
运行结果： 
（7）归并排序
基本思想：是基于合并，将两个或两个以上有序表合并成一个新的有序表。
代码实现：
void _Merge(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
int start = begin1;
int finsh = end2;
size_t index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
memcpy(a + start, tmp + start,(finsh - start + 1)*sizeof(int));
}
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin >= end)
return;
int mid = begin + (end - begin) / 2;
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
_Merge(a, tmp, begin, mid, mid + 1, end);
}
void MergeSort(int* a, int n)
{
assert(a);
int* tmp = new int[n];
_MergeSort(a, tmp, 0, n - 1);
delete[] tmp;
}
void TestInsertSort()
{
int a[] = { 2, 0, 4, 9, 3, 5, 8, 7, 1, 5 };
Printf(a, sizeof(a) / sizeof a[0]);
MergeSort(a, sizeof(a) / sizeof a[0]);
Printf(a, sizeof(a) / sizeof a[0]);
}
关于几种排序的比较总结，及优化见下篇博客。