插入排序
每次选择一个元素K插入到之前已排好序的部分A[1…i]中，由后向前移动元素直到找到一个合适的位置。
插入排序是稳定的（相等的时候表示找到合适位置了，就不需要再移动元素了）。
void InsertSort(RecType R[], int n){
int i, j;
RecType temp;
for(i = 1; i<n; ++i){
temp = R[i];
j = i - 1;//从后往前找到一个合适的位置
while(j >= 0 && temp.key < R[j].key){
R[j + 1] = R[j];
j--;
}
R[j + 1] = temp;//将元素放置到该合适位置
}
}
冒泡排序
通过交换元素，使关键字最大的记录如气泡一般逐渐往上“漂浮”直至“水面”。
排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以，它们的相对位置并没有改变，冒泡排序算法是稳定的
void BubbleSort(RecType R[], int n){
int i, j;
RecType temp;
for(i=0; i<n-1; i++){//每个元素
bool flag = false;
for(j=n-1;j > i; j--){//对每个元素进行冒泡
if(R[j].key < R[j - 1].key){
temp = R[j];
R[j] = R[j - 1];
R[j - 1] = temp;
flag = true;
}
if(!flag){//如果没有交换，说明已经有序了
return;
}
}
}
}
选择排序
搜索无序数组，找到当前最小的元素，并与无序数组首元素交换，缩小整个无序数组，并重复操作。直到整个数组有序。
由于每次都是选取未排序序列A中的最小元素x与A中的第一个元素交换，因此跨距离了，很可能破坏了元素间的相对位置，因此选择排序是不稳定的！
void SelectSort(RecType R[], int n){
int i, j, k;
RecType temp;
for(i = 0; i < n - 1; ++i){
k = i;
//便利无序数组，找到最小的元素
for(j = i + 1; j < n; j++){
if(R[j].key < R[k].key){
k = j;
}
}
if(k != i){
swap(R[i], R[k]);
}
}
希尔排序
思想：希尔排序也是一种插入排序方法,实际上是一种分组插入方法。先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量d2(＜d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
希尔排序时间复杂度平均为O(nlogn)
