使用c语言编程实现：分别利用直接插入/折半插入/希尔/冒泡/快速/简单选择排序算法实现 将待排序序列{3,6,2,10,1,20,88,8,5,7,4,9}由小到大排序，并输出结果。 （至少完成3个）

### C语言实现多种排序算法的代码示例 以下是使用C语言实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序的代码示例。待排序序列为 `{3,6,2,10,1,20,88,8,5,7,4,9}`，并输出排序结果。 --- #### 1. 直接插入排序 ```c void InsertSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } ``` 直接插入排序的基本思想是将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增加1的有序表[^1]。 --- #### 2. 折半插入排序 ```c void BinaryInsertSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int low = 0, high = i - 1; while (low <= high) { int mid = (low + high) / 2; if (key < arr[mid]) { high = mid - 1; } else { low = mid + 1; } } for (int j = i - 1; j >= low; j--) { arr[j + 1] = arr[j]; } arr[low] = key; } } ``` 折半插入排序通过减少比较次数来优化直接插入排序，使用二分查找确定插入位置[^1]。 --- #### 3. 希尔排序 ```c void ShellSort(int arr[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int key = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > key) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = key; } } } ``` 希尔排序是一种基于插入排序的算法，通过将比较的全部元素分为几个区域来提升插入排序的效率[^2]。 --- #### 4. 冒泡排序 ```c void BubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { bool swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } if (!swapped) break; } } ``` 冒泡排序通过重复地遍历待排序列表，比较相邻的元素并交换顺序错误的元素[^1]。 --- #### 5. 快速排序 ```c void QuickSort(int arr[], int low, int high) { if (low < high) { int pivot = Partition(arr, low, high); QuickSort(arr, low, pivot - 1); QuickSort(arr, pivot + 1, high); } } int Partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } ``` 快速排序采用分治法策略，通过选取一个“基准”元素将数组分为两部分，并递归地对这两部分进行排序[^1]。 --- #### 6. 简单选择排序 ```c void SelectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } ``` 简单选择排序通过每次从未排序部分选择最小的元素并将其放到已排序部分的末尾来实现排序[^1]。 --- #### 排序结果 待排序序列：`{3,6,2,10,1,20,88,8,5,7,4,9}` 排序后的结果为：`{1,2,3,4,5,6,7,8,9,10,20,88}` ---