常用排序算法详解：插入排序、交换排序与选择排序

"这篇文档介绍了三种常见的排序方法：选择排序、插入排序以及交换排序，包括它们的基本思想、时间复杂度和简单的C/C++程序实现。这些排序算法的时间复杂度都是O(n^2)，适用于小规模数据或部分有序的数据排序。" ### 选择排序 选择排序是一种简单直观的排序算法。其基本思想是在每一轮排序中，从未排序的元素中找到最小（或最大）的元素，将其放到已排序序列的末尾。这个过程会重复n-1次，直到所有元素都有序。由于在排序过程中可能会改变相同元素的相对顺序，所以选择排序是不稳定的排序方法。其时间复杂度为O(n^2)。 ```c void selection_sort(int r[], int n) { int i, j, min_idx; for (i = 0; i < n - 1; i++) { min_idx = i; for (j = i + 1; j < n; j++) { if (r[j] < r[min_idx]) { min_idx = j; } } if (min_idx != i) { int temp = r[i]; r[i] = r[min_idx]; r[min_idx] = temp; } } } ``` ### 插入排序 插入排序分为直接插入排序和二分插入排序。直接插入排序是将每个元素插入到已排序序列的正确位置，每趟排序后，未排序部分的元素减少一个。而二分插入排序则在插入时利用二分查找，提高插入效率。两种插入排序的时间复杂度也是O(n^2)。 ```c // 直接插入排序 void insert_sort(int r[], int n) { int i, j, t; for (i = 1; i < n; i++) { t = r[i]; j = i - 1; while (j >= 0 && r[j] > t) { r[j + 1] = r[j]; j--; } r[j + 1] = t; } } // 二分插入排序 void binary_insert_sort(int r[], int n) { int i, low, mid, high, t; for (i = 1; i < n; i++) { t = r[i]; low = 0; high = i - 1; while (low <= high) { mid = (low + high) / 2; if (t < r[mid]) { high = mid - 1; } else { low = mid + 1; } } for (j = i - 1; j >= low; j--) { r[j + 1] = r[j]; } r[low] = t; } } ``` ### 交换排序 交换排序中最典型的是冒泡排序，通过不断比较相邻元素并交换，使得每一轮排序后最大的元素“浮”到数组的末尾。同样，冒泡排序的时间复杂度为O(n^2)。 ```c // 冒泡排序 void bubble_sort(int r[], int n) { int i, j, t; for (i = 0; i < n - 1; i++) { for (j = 0; j < n - 1 - i; j++) { if (r[j] > r[j + 1]) { t = r[j]; r[j] = r[j + 1]; r[j + 1] = t; } } } } ``` 以上就是选择排序、插入排序（直接插入与二分插入）以及交换排序（冒泡排序）的基本概念、时间复杂度和C/C++实现。这三种排序算法都属于基础排序，虽然在最坏情况下时间复杂度较高，但它们的实现简单，易于理解，对于小规模数据或者部分有序的数据，表现还是可以接受的。