c语言实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序和二路归并排序算法

### C语言实现多种排序算法 #### 直接插入排序 直接插入排序是一种简单的排序方法，其基本操作是在已排序序列中找到合适的位置并插入新元素。 ```c void InsertionSort(int a[], int n) { int i, j; int current; for (i = 1; i < n; ++i) { current = a[i]; j = i - 1; while (j >= 0 && a[j] > current) { a[j + 1] = a[j]; --j; } a[j + 1] = current; } } ``` #### 折半插入排序 折半插入排序通过减少比较次数来提高效率，在每次插入时利用二分查找确定插入位置。 ```c int BinarySearch(int a[], int low, int high, int key) { int mid; while (low <= high) { mid = (low + high) / 2; if (key < a[mid]) high = mid - 1; else low = mid + 1; } return low; } void BinaryInsertionSort(int a[], int n) { int i, location, j; int selected; for (i = 1; i < n; ++i) { j = i - 1; selected = a[i]; // Find location where element should be inserted using binary search. location = BinarySearch(a, 0, j, selected); while (j >= location) { a[j + 1] = a[j]; --j; } a[j + 1] = selected; } } ``` #### 希尔排序 希尔排序是对直接插入排序的一种改进，它允许间隔较大的元素进行交换，从而加速整个过程。 ```c void ShellSort(int a[], int n) { int gap, i, j; int temp; for (gap = n / 2; gap > 0; gap /= 2) { for (i = gap; i < n; ++i) { temp = a[i]; for (j = i; j >= gap && a[j - gap] > temp; j -= gap) { a[j] = a[j - gap]; } a[j] = temp; } } } ``` #### 冒泡排序 冒泡排序重复遍历列表，依次比较相邻两个元素，并按需交换它们的位置直到不再发生任何交换为止。 ```c void BubbleSort(int a[], int n) { bool swapped; int i, j; for (i = 0; i < n - 1; ++i) { swapped = false; for (j = 0; j < n - 1 - i; ++j) { if (a[j] > a[j + 1]) { swap(&a[j], &a[j + 1]); swapped = true; } } if (!swapped) break; } } ``` #### 快速排序 快速排序采用分治法策略，选择一个基准值将数组分为两部分，分别对这两部分继续执行相同的操作直至完全有序。 ```c void QuickSort(int a[], int left, int right) { if (left >= right) return; int pivotIndex = Partition(a, left, right); QuickSort(a, left, pivotIndex - 1); QuickSort(a, pivotIndex + 1, right); } int Partition(int a[], int left, int right) { int pivotValue = a[right]; int storeIndex = left; for (int i = left; i < right; ++i) { if (a[i] < pivotValue) { swap(&a[storeIndex++], &a[i]); } } swap(&a[right], &a[storeIndex]); return storeIndex; } ``` #### 简单选择排序 简单选择排序每一轮从未排序区域选出最小（最大）的一个记录放到已排序区间的末端。 ```c void SelectionSort(int a[], int n) { int minIdx; for (int i = 0; i < n - 1; ++i) { minIdx = i; for (int j = i + 1; j < n; ++j) { if (a[j] < a[minIdx]) minIdx = j; } if (minIdx != i) swap(&a[minIdx], &a[i]); } } ``` #### 堆排序 堆排序基于二叉堆数据结构，先构建最大堆再逐步取出堆顶元素形成有序序列。 ```c void Heapify(int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2 * i + 1; // left child index int r = 2 * i + 2; // right child index // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { swap(&arr[i], &arr[largest]); // Recursively heapify the affected sub-tree Heapify(arr, n, largest); } } void HeapSort(int arr[], int n) { // Build max heap for (int i = n / 2 - 1; i >= 0; i--) Heapify(arr, n, i); // Extract elements from heap one by one for (int i = n - 1; i >= 0; i--) { swap(&arr[0], &arr[i]); // Move current root to end Heapify(arr, i, 0); // call max heapify on reduced heap } } ``` #### 归并排序 归并排序也是一种典型的分治算法，递归地把当前区间分成两半，然后合并这两个已经排好序的部分得到完整的排序结果。 ```c void Merge(int array[], int const left, int const mid, int const right) { auto const subArrayOne = mid - left + 1; auto const subArrayTwo = right - mid; // Create temporary arrays auto* leftArray = new int[subArrayOne], *rightArray = new int[subArrayTwo]; // Copy data to temp arrays leftArray[] and rightArray[] for (auto i = 0; i < subArrayOne; i++) leftArray[i] = array[left + i]; for (auto j = 0; j < subArrayTwo; j++) rightArray[j] = array[mid + 1 + j]; auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0; int indexOfMergedArray = left; // Merge the temp arrays back into array[left..right] while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) { if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) { array[indexOfMergedArray] = leftArray[indexOfSubArrayOne++]; } else { array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo++]; } indexOfMergedArray++; } // Copy remaining elements of leftArray[], if any while (indexOfSubArrayOne < subArrayOne) { array[indexOfMergedArray++] = leftArray[indexOfSubArrayOne++]; } // Copy remaining elements of rightArray[], if any while (indexOfSubArrayTwo < subArrayTwo) { array[indexOfMergedArray++] = rightArray[indexOfSubArrayTwo++]; } delete[] leftArray; delete[] rightArray; } void MergeSort(int array[], int const begin, int const end) { if (begin >= end) return; auto mid = begin + (end - begin) / 2; MergeSort(array, begin, mid); MergeSort(array, mid + 1, end); Merge(array, begin,