目录
一、冒泡排序
【思路】冒泡排序算法通过多次比较和交换来实现排序，其排序流程如下
1)对数组中的各数据，依次比较相邻的两个元素的大小；
2)如果前面的数据大于后面的数据，就交换这两个数据。经过第一轮的多次比较排序后，便可把最大的数据排好；
3)再用相同的方法把剩下的数据逐个进行比较，最后便可按照从小到大的顺序排好。
void BubbleSort(int *a, int len) {
for (int i = 0; i < len - 1; i++) //进行 len-1 次比较
for (int j = 0; j < len - i - 1; j++) //在每次中进行 len-i-1 次比较
if (a[j] > a[j + 1]) //按升序排序，降序用<
{
int temp = a[j + 1]; //交换相邻的两个元素
a[j + 1] = a[j];
a[j] = temp;
}
}
?
?
二、选择排序（擂台法）
【思路】选择排序法在每一步中选取最小值来重新排序。
排序基本流程：
1)首先从原始数组中选择一个最小的数据，将其和位置位于第1个的数据交换；
2)从剩下的n-1个数据中选择次小的一个元素，将其和位于第2个的数据交换；
3)这样不断重复，知道最后两个数据完成交换。
void SelectionSort(int *a, int len) {//升序
int i, j, k;
for (i = 0; i < len - 1; i++) {//进行 len-1 次比较
k = i;
for (j = i + 1; j < len; j++)
if (a[j] < a[k]) k = j;//存储下标，不直接交换
if (k != i) {
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
}
void SelectionSort1(int *a, int len) {//降序，按住一个位置不动，循环出一个最大值，好比打擂台
int i, j, max=0;
for (i = 0; i < len - 1; i++) {
max = i;
for (j = i + 1; j < len; j++) {
if (a[max] < a[j]) {
int temp = a[j];
a[j] = a[max];
a[max] = temp;
}
}
}
}以上两个都是选择排序，SelectionSort更高效。
?
?
三、插入排序
【思路】插入排序算法通过比较和插入来实现排序，其排序流程如下：
1)首先对数组的前两个数据进行从小到大排序；
2)将第3个数据与排好序的两个数据比较，将第3个数据插入合适的位置；
3)将第4个数据插入已排好的前3个数据中；
4)不断重复上述过程，直到把最后一个数据插入合适的位置。
void InsertionSort(int *a, int len) {
int i, j, t;
for (i = 1; i < len; i++) {
t = a[i];
j = i - 1;
while (j >= 0 && t < a[j]) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = t;
}
}
?
?
四、希尔排序（缩小增量排序）
【思路】希尔排序算法严格来说是基于插入排序的思想，Shell排序算法的排序流程如下：
- 将有n个元素的素组分为n/2个序列，第1个数据和第n/2+1个数据为1对，等等，依次类推；
- 一次循环使每一个序列对排好顺序；
- 变为n/4个序列，再次排序；
- 不断重复上述过程，随着序列减少直至最后变为1个，完成整个排序。
void ShellSort(int *a, int len) {
int i, j, r, temp;
for (r = len / 2; r >= 1; r /= 2) {//划组排序
//每一趟采用插入排序
for (i = r; i < len; i++) {
temp = a[i];
j = i - r;
while (j >= 0 && temp < a[j]) {
a[j + r] = a[j];
j -= r;
}
a[j + r] = temp;
}
}
}
?
?
五、快速排序
【思路】快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
- 首先设置一个分界值，通过分界值将数组分成左右两部分；
- 将大于或等于分界值的数据集中到数组右边，小于边界值的数据集中到数组的左边；
- 左边和右边的数据可以独立排序。对于左侧的数据，又可以取一个分界值，将该数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数据也可以做类似处理；
- 重复以上过程，可以看出这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。
void Quick_Sort(int *a, int begin, int end) {
if (begin > end)
return;
int tmp = a[begin];
int i = begin;
int j = end;
while (i != j) {
while (a[j] >= tmp && j > i)
j--;//从右往左找比tmp小的
while (a[i] <= tmp && j > i)
i++;//从左往右找比tmp大的
if (j > i) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
a[begin] = a[i];
a[i] = tmp;
Quick_Sort(a, begin, i - 1);
Quick_Sort(a, i + 1, end);
}六、堆排序
堆（heap）：完全二叉树，父结点的值大于子结点的值。
void print(int a[], int n) {//打印数组
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
void HeapSort(int a[], int n) {
int i, j, k;
int t;
for (i = n / 2 - 1; i >= 0; i--) {//建成大顶堆
while (2*i+1<n)//第2个结点有右子树
{
j = 2 * i + 1;
if (j + 1 < n) {
if (a[j] < a[j + 1])//左子树小于右子树，则需要比较右子树
j++;//序号加1，指向右子树
}
if (a[i]<a[j]){//比较i与j为序号的数据
t = a[i];
a[i] = a[j];
a[j] = t; //交换数据
i = j;//堆被破坏，需要重新调整
}
else {//比较左右子节点均大，则堆未破坏，不再需要调整
break;
}
}
}
//输出构成的堆
cout << "原数据构成的堆：";
print(a, n);
for (i = n - 1; i > 0; i--) {
t = a[0];
a[0] = a[i];
a[i] = t;
k = 0;
while (2 * k + 1 < i) {
j = 2 * k + 1;
if (j + 1 < i) {
if (a[j] < a[j + 1])
j++;
}
if (a[k] < a[j]) {
t = a[k];
a[k] = a[j];
a[j] = t;
k = j;
}
else {
break;
}
}
cout << "第" << n - i << "步排序：";
print(a, 10);
}
}??
?第1步排序 对应上面第5个树，
?第2步排序 对应上面第8个树，
?第2步排序 对应上面最后个树
?
?
七、归并排序（合并排序）
归并排序:采用分治的思想，将数组(Array)划分为两个子数组(left和right)，然后递归(MergeSort)的将每个子数组再进行划分，直到数组中只剩一下一个元素，然后开始排序合并(Merge)，直到将所有的子数组合并完成，整个数据就是有序的了。
void print(int a[], int n) {
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
void MergeOne(int a[], int b[], int n, int len) {//完成一遍合并的函数
int i, j, k, s, e;
s = 0;
while (s + len < n) {
e = s + 2 * len - 1;
if (e >= n) {//最后一段可能少于len个结点
e = n - 1;
}
//相邻有序段合并
k = s;
i = s;
j = s + len;
while (i < s + len && j <= e) {//如果两个有序表都未结束时，循环比较
if (a[i] <= a[j])//将较小的数组放到数组b中
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while (i < s + len) {//未合并的部分复制到数组b中
b[k++] = a[i++];
}
while (j <= e) {//未合并的部分复制到数组b中
b[k++] = a[j++];
}
s = e + 1;//下一对有序段中左段的开始下标
}
if (s < n) {//将剩余的一个有序段从数组a中复制到数组b
for (; s < n; s++) {
b[s] = a[s];
}
}
}
void MergeSort(int a[], int n) {//合并排序
int *p;
int h, count, len, f;
count = 0;//排序步骤
len = 1;//有序序列的长度
f = 0;//标志
if (!(p = (int *)malloc(sizeof(int)*n))) {//分配内存空间
cout << "分配内存失败！";
exit(0);
}
while (len < n) {
if (f == 1) {
MergeOne(p, a, n, len);//p合并到a
}
else
{
MergeOne(a, p, n, len);//a合并到p
}
len = len * 2;//增加有序序列长度
f = 1 - f;//使f值在0和1之间切换
count++;
cout << "第" << count << "步排序：";
print(a, n);
}
if (f) {//如果进行了排序
for (h = 0; h < n; h++)//将内存p中的数据复制到数组a中
a[h] = p[h];
}
free(p);//释放内存
}
?
?
八、递归排序
编写sort()函数将一组无序数排列成降序，要求利用递归算法来实现外层循环，主函数中对数据{5,3,7,4,2,9,8,32,54,21,6,43}调用sort()函数实现排序。
void sort(int *x, int n) {
int j, t;
if (n == 1)
return;
for ( j = 0; j < n; j++)
{
if (x[0] < x[j]) {
t = x[0];
x[0] = x[j];
x[j] = t;
}
}
sort(x + 1, n - 1);
}
int main() {
int a[12] = { 5,3,7,4,2,9,8,32,54,21,6,43 };
sort(a, 12);
for (int k = 0; k < 12; k++)
cout << a[k] << ' ';
cout << endl;
return 0;
}