C语言实现：Shaker排序——优化的气泡排序算法

"C语言中的Shaker排序法，也被称为改良的气泡排序，是一种效率更高的排序算法，它基于原气泡排序的基础上进行了优化。Shaker排序利用了气泡排序的冒泡过程，同时结合了“右端左移”和“左端右移”的策略，以减少不必要的比较和交换操作，从而提高排序速度。 原始的气泡排序通过相邻元素的比较和交换，将较大的元素逐渐“浮”到数组的一端。在每一轮迭代中，最大的元素会被移动到最后。然而，如果数组已经部分排序，这种简单的气泡排序会浪费很多时间在已经正确排序的部分。 Shaker排序法改进了这一情况。它分为两个阶段：前半部分从数组的起始位置向结束位置进行比较和交换（就像普通的气泡排序），但当到达数组末尾时，不立即停止，而是立即反转方向，从结束位置向起始位置进行比较和交换，直到返回到起始位置。这样，每个元素都有机会在两个方向上与其他元素进行比较，从而提高了排序效率。 以下是一个简单的C语言实现Shaker排序的代码示例： ```c #include<stdio.h> #include<stdlib.h> #include<time.h> #define MAX 10 #define SWAP(x, y) { int t; t = x; x = y; y = t;} void shakersort(int number[]) { int i, j, flag = 1; for (i = 0; i < MAX/2 && flag == 1; i++) { // 主循环，控制外层的移动方向 flag = 0; // 设定初始无交换状态 for (j = 0; j < MAX-i-1; j++) { // 向右冒泡 if (number[j+1] < number[j]) { SWAP(number[j+1], number[j]); flag = 1; // 如果有交换发生，更新标志位 } } for (j = MAX-i-2; j >= 0 && flag == 1; j--) { // 向左冒泡 if (number[j] > number[j+1]) { SWAP(number[j], number[j+1]); flag = 1; } } } } int main(void) { int number[MAX] = {0}; int i; srand(time(NULL)); // 初始化随机种子 // 随机填充数组 for (i = 0; i < MAX; i++) { number[i] = rand() % 100; } shakersort(number); printf("Sorted array: "); for (i = 0; i < MAX; i++) { printf("%d ", number[i]); } printf("\n"); return 0; } ``` 在这个代码中，`shakersort`函数实现了Shaker排序。首先，初始化一个长度为`MAX`的整数数组，并用随机数填充。然后调用`shakersort`对数组进行排序，最后打印出排序后的结果。`SWAP`宏用于交换两个元素的值，使得代码更简洁。 通过这样的方式，Shaker排序在保持了气泡排序的基本思想的同时，显著减少了比较和交换的次数，尤其在处理近乎有序的数组时，其效率表现远优于标准的气泡排序。这种改进的排序算法在实际编程中可以作为一个高效且易于理解的选择。"