# 使用下面的命令来检查您的系统上是否安装了 GCC gcc -v # 如果没有安装 使用下面命令安装 apt install gcc
排序算法 冒泡排序
比对 的双方 放在一个盒子中， 盒子 就像泡泡一样，一步一步冒出去。
#include选择排序// 程序运行命令 gcc main.c -o aaa; ./aaa int main() { int arr[] = {4, 2, 1, 3,5, 10, 11,2,3,1}; int len = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, len); printf("[ "); int i; for (i = 0; i < len; i++) printf("%d， ", arr[i]); printf("]"); printf("n"); return 0; } void bubbleSort(int *arr, unsigned int length) { if (length < 2) return; //长度小于2的数组 无需排序 int i; // 轮数 计数器 int j; // 每轮 比对数 计数器 int tmp; // 变量交换的临时变量 for (i = 0; i < length - 1; i++) //总的执行多少轮 { // 从前往后，两两比，每轮最大值放后面 for (j = 0; j < length - 1 - i; j++) //每轮执行的次数 { if (arr[j] > arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } }
熊瞎子剥玉米，一轮过去手里只有一个最大（小）的。
void selectionSort(int *arr, unsigned int length)
{
if (length < 2)
return; //长度小于2的数组 无需排序
int i;
int j;
int tmp;
for (i = 0; i < length - 1; i++)
{
int min = i;
// 从前往后，每一轮的 首个元素 依次和后面元素对比， 将 最小的 放在每一轮的首位置
for (j = i + 1; j < length; j++)
{
if (arr[min] > arr[j])
{
min = j;
}
}
tmp = arr[min];
arr[min] = arr[i];
arr[i] = tmp;
}
}
插入排序
抓扑克排序
void insertSort(int *arr, unsigned int length)
{
if (length < 2)
return; //长度小于2的数组 无需排序
int i;
int j;
int current; // 当前比对元素
for (i = 1; i < length; i++)
{
current = arr[i];
// 从已排序的最右边开始，把大于 当前排序 的元素 后移
for (j = i - 1; j >= 0; j--)
{
// 如果找到 当前排序元素 比 有序序列中 大的元素，就证明 前面的元素都会 比 前排序元素， 则此轮无需再找，直接跳出循环
if (current >= arr[j])
break;
// 有序序列中 大于 当前比对元素 的元素 后移一位
arr[j + 1] = arr[j];
}
// 将 当前比对元素 放到 比较过程中，最后一次比较的元素 后面
arr[j + 1] = current;
}
}
希尔排序
插入排序的升级版本， 分组之后 在进行插入排序
void shellSort(int *arr, int length)
{
int i, step; // 步长
// 强类型语言中： 3/2 == 2/2 == 1，
// 所以 每次取一半， 最后一次步长 必定为1
for (step = length / 2; step > 0; step = step / 2)
{
printf("此次分组的步长：%dn", step);
// 步长 为几， 就将原数组 分成 几组，
// 对 ===每一组=== 都进行 插入排序
for (i = 0; i < step; i++)
{
InsertSortByStep(arr, length, i, step);
}
}
}
// length 数组总长度； i 分组的起始位置； step 步长（增量）
void InsertSortByStep(int arr[], int length, int i, int step)
{
int current; // 当前排序元素
int current_index; // 当前排序元素 的 计时器
int j; // 插入时，需要后移元素 的计数器
for (current_index = i + step; current_index < length; current_index=current_index+step)
{
current = arr[current_index];
for (j = current_index - step; j >= 0; j = j - step)
{
if (current >= arr[j]) break;
// 有序序列中 大于 当前比对元素 的元素 后移一位
arr[j + step] = arr[j];
}
// 将 当前比对元素 放到 比较过程中，最后一次比较的元素 后面
arr[j + step] = current;
}
}
快速排序
void quickSort(int *arr, int length)
{
if (length<2) return; //递归的结束条件
int center = arr[0]; // 选最左侧的 数 作为中心轴
int left = 0; // 左下标
int right = length-1; // 右下标
int moving = 2; // 当前应该移动 哪边的坐标， 1：左下标 2：右下标
// 交替式 移动， 左下标 比较大小时 如果 移动了元素到 右侧， 则下次循环 就 比较 左下标，反复交替，
// 直到 左下标==右下标， 当 两标 重合，证明此轮排序完成
while (left < right)
{
if (moving ==2) // 移动右下标的case
{
// 如果右下标位置元素的值 大于等于 中心轴， 继续移动 右下标
if (arr[right] >= center)
{
right--; // 此次比对 没有找到 比中心轴小的，则无需移动比对元素，比对 右侧的 下一个元素
continue;
}
// 如果右下标位置元素的值 小于 中心轴， 把它填到左下标的坑中
arr[left] = arr[right];
left++; //左下标向由移动
moving = 1; // 右边移动了元素，空出坑了，那么下次循环将移动 左下标
continue;
}
if (moving ==1) // 移动左下标的case
{
// 如果左下标位置元素小于等于 中心轴，继续移动左下标
if (arr[left]<=center)
{
left++;
continue;
}
// 如果左下标位置元素的值大于中心轴， 把它填到右下标的坑中
arr[right] = arr[left];
right--;
moving= 2; // 左边移动了元素，空出坑了，那么下次循环将移动 右下标
continue;
}
}
// 如果循环结束，把 中心轴 的值 放回去
arr[left] = center;
quickSort(arr, left); // 对中心轴 左边 的序列进行排序
quickSort(arr + left+1, length-left-1); // 对中心轴 右边 的序列进行排序
}
合并排序
// A 待排序数组
// begin 索引起始位置 0
// end 索引终止位置 len-1
void MERGE_SORT(int *A, int begin, int end)
{
if (begin < end) //递归结束条件， 数组只有一个元素时 结束
{
int mid = (begin + end) / 2; // 计算中间元素下标，将数组 分为 左右两个部分
MERGE_SORT(A, begin, mid); // 左部分 递归
MERGE_SORT(A, mid + 1, end); // 右部分 递归
MERGE(A, begin, mid, end); // 合并 左半部分 和 右半部分
}
}
// b 第一个元素索引； m 中间元素索引； e 最后一个元素索引
void MERGE(int *A, int b, int m, int e)
{
int l = m - b + 1; // 左半部分 数组长度
int L[l]; // 存放 左半部分 的外部数组
int r = e - m; // 右半部分 数组长度
int R[r]; // 存放 右半部分 的外部数组
int i, j, k;
// 下面两个循环，分别将 已排序的 左、右半部分 的 原始数组元素 拷贝到 左、右外部数组
for (i = 0; i < l; i++)
{
L[i] = A[b + i];
}
for (j = 0; j < r; j++)
{
R[j] = A[m + j + 1];
}
i = 0; // 左 外部数组 的索引
j = 0; // 右 外部数组 的索引
k = b; // 原始数组 的 索引
// 合并函数 的 核心， 分为3种情况：
// case1： 左、右 外部数组 都有元素待 比较合并 的情况
while (i < l && j < r)
{
// 通过 k 指定 原始数组 首个要 放入 外部数组 的一个坑位
// 哪个外部数组的 元素小 就 放到 原始数组 的坑中
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
k++; // 指定 原始数组 的下一个坑位
}
// case2： 右 外部数组 元素都比较合并完了，只剩下 左 外部数组 的情况
while (i < l)
{
A[k] = L[i]; // 将 左 外部数组 元素 依次放入到 原始数组 中
i++;
k++;
}
// case3： 左 外部数组 元素都比较合并完了，只剩下 右 外部数组 的情况
while (j < r)
{
A[k] = R[j]; // 将 右 外部数组 元素 依次放入到 原始数组 中
j++;
k++;
}
}
