常用排序算法总结及C源程序

排序算法在计算机科学中占有重要地位，它们是数据处理和信息管理的基础。本文将深入探讨四种常见的排序算法：直接插入排序、折半插入排序、冒泡排序和快速排序，并提供相应的C语言源代码实现。 1. 直接插入排序： 直接插入排序是一种简单直观的排序算法，它的工作原理类似于打扑克牌时的排列。算法首先假设数组的第一个元素是已排序的，然后从第二个元素开始，依次将其插入到已排序的序列中。在C语言中，该算法的实现如下： ```c void InsertSort(int *out, int *op, int length) { int i, j; int data; memcpy(out, op, length * sizeof(int)); for (i = 1; i < length; i++) { data = out[i]; for (j = i - 1; data < out[j] && j >= 0; j--) { out[j + 1] = out[j]; } out[j + 1] = data; } } ``` 2. 折半插入排序： 折半插入排序是直接插入排序的一个优化版本，它利用了二分查找的特性来减少比较次数。在每次插入元素时，我们通过二分查找找到合适的位置，然后将元素插入。C语言实现如下： ```c void BInsertSort(int *out, int *op, int length) { int low, mid, high; int i, j, data; memcpy(out, op, length * sizeof(int)); for (i = 1; i < length; i++) { data = out[i]; low = 0; high = i - 1; while (low <= high) { mid = (low + high) / 2; if (data < out[mid]) high = mid - 1; else low = mid + 1; } for (j = i - 1; j >= high + 1; j--) out[j + 1] = out[j]; out[j + 1] = data; } } ``` 3. 冒泡排序： 冒泡排序是一种简单的交换排序，通过不断地交换相邻的逆序元素来逐步将大元素“冒”到数组的末尾。C语言实现如下： ```c void BubbleSort(int *out, int *op, int length) { int i, j; memcpy(out, op, length * sizeof(int)); for (i = length - 1; i >= 0; i--) { for (j = 0; j < i; j++) { if (out[j] > out[j + 1]) { swap(out + j, out + j + 1); } } } } ``` 4. 快速排序： 快速排序是一种高效的分治排序算法，由C.A.R. Hoare提出。其基本思想是选取一个枢轴元素，将数组分成两部分，一部分所有元素都小于枢轴，另一部分所有元素都大于枢轴，然后对这两部分分别进行快速排序。C语言实现如下： ```c int Partition(int *out, int *op, int length, int low, int high) { int pivokey; memcpy(out, op, length * sizeof(int)); pivokey = out[low]; while (low < high) { while (out[high] > pivokey) high--; out[low] = out[high]; while (out[low] < pivokey) low++; out[high] = out[low]; } out[low] = pivokey; return low; } void QuickSort(int *out, int *op, int length, int low, int high) { if (low < high) { int pivotIndex = Partition(out, op, length, low, high); QuickSort(out, op, length, low, pivotIndex - 1); QuickSort(out, op, length, pivotIndex + 1, high); } } ``` 这四种排序算法各有优缺点。直接插入排序和折半插入排序适合于小规模或部分有序的数据，而冒泡排序效率较低，但在数据近乎有序时表现良好。快速排序则通常是最高效的通用排序算法之一，尤其在处理大数据量时，平均时间复杂度为O(n log n)。了解并熟练掌握这些排序算法对于理解算法设计和分析至关重要，有助于在实际编程中选择最合适的排序方法。