C语言常用排序算法[借鉴].pdf

"C语言常用排序算法" 稳定排序和非稳定排序是两种不同的排序方法。稳定排序是指在排序过程中，所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序。例如，一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。如果变成a1,a4,a2,a3,a5就不是稳定的了。 内排序和外排序是两种不同的排序方式。在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序。在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 算法的时间复杂度和空间复杂度是衡量算法性能的两个重要指标。时间复杂度是指执行算法所需要的计算工作量，空间复杂度是指执行这个算法所需要的内存空间。 选择排序是一种简单的排序算法。其思想是：在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。选择排序是不稳定的，时间复杂度为O(n2)。 选择排序的实现代码如下： ```c void select_sort(int *x, int n) { int i, j, min, t; for (i = 0; i < n - 1; i++) { min = i; for (j = i + 1; j < n; j++) { if (*(x + j) < *(x + min)) { min = j; } } if (min != i) { t = *(x + i); *(x + i) = *(x + min); *(x + min) = t; } } } ``` 直接插入排序是一种稳定的排序算法。其思想是：在要排序的一组数中，假设前面（n-1）[n>=2]个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。直接插入排序的时间复杂度为O(n2)。 直接插入排序的实现代码如下： ```c void insert_sort(int *x, int n) { int i, j, t; for (i = 1; i < n; i++) { t = *(x + i); for (j = i - 1; j >= 0 && t < *(x + j); j--) { *(x + j + 1) = *(x + j); } *(x + j + 1) = t; } } ``` 冒泡排序是一种稳定的排序算法。其思想是：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。冒泡排序的时间复杂度为O(n2)。 冒泡排序的实现代码如下： ```c void bubble_sort(int *x, int n) { int j, k, h, t; for (h = n - 1; h > 0; h = k) { k = 0; for (j = 0; j < h; j++) { if (*(x + j) > *(x + j + 1)) { t = *(x + j); *(x + j) = *(x + j + 1); *(x + j + 1) = t; k = j; } } } } ``` 排序算法的选择取决于具体情况的需求，例如稳定性、时间复杂度、空间复杂度等。在实际应用中，需要根据具体情况选择合适的排序算法，以保证算法的正确性和效率。