六种基础排序算法解析
目录
- 冒泡排序
- 插入排序
- 归并排序
- 快速排序
- 选择排序
- 堆排序
冒泡排序
算法原理
通过重复遍历待排序序列，比较相邻元素并交换位置，将较大元素逐步"冒泡"到数组末尾。每轮遍历后，最后一个元素会成为当前未排序部分的最大值。
时间复杂度
O(n²)
实现代码
void sortBubble(int arr[], int size) {
if(size <= 1) return;
for(int i = 0; i < size-1; i++) {
for(int j = 0; j < size-1-i; j++) {
if(arr[j] > arr[j+1]) {
std::swap(arr[j], arr[j+1]);
}
}
}
}
示例
输入：[5, 3, 8, 4, 2]
输出：[2, 3, 4, 5, 8]
插入排序
算法原理
将未排序元素逐个插入到已排序序列的合适位置。通过维护一个有序子数组，每次将未排序部分的第一个元素插入到正确位置。
时间复杂度
O(n²)
实现代码
void insertionSort(int arr[], int size) {
for(int i = 1; i < size; 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;
}
}
示例
输入：[6, 2, 9, 1, 7]
输出：[1, 2, 6, 7, 9]
归并排序
算法原理
采用分治策略，将数组分成两个子数组分别排序，然后合并两个有序子数组。通过递归分解直到单个元素，再逐步合并排序。
时间复杂度
O(n log n)
实现代码
void mergeSort(int arr[], int temp[], int left, int right) {
if(left >= right) return;
int mid = left + (right - left)/2;
mergeSort(arr, temp, left, mid);
mergeSort(arr, temp, mid+1, right);
int i = left, j = mid+1, k = left;
while(i <= mid && j <= right) {
if(arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while(i <= mid) temp[k++] = arr[i++];
while(j <= right) temp[k++] = arr[j++];
for(int m = left; m <= right; m++) {
arr[m] = temp[m];
}
}
示例
输入：[10, 5, 8, 1, 3]
输出：[1, 3, 5, 8, 10]
快速排序
算法原理
选择一个基准元素，将数组分为两部分：小于基准的元素和大于基准的元素。递归处理左右子数组，最终得到有序序列。
时间复杂度
O(n log n) 平均，O(n²) 最坏情况
实现代码
void quickSort(int arr[], int left, int right) {
if(left >= right) return;
int pivot = arr[left];
int l = left, r = right;
while(l < r) {
while(l < r && arr[r] >= pivot) r--;
while(l < r && arr[l] <= pivot) l++;
if(l < r) std::swap(arr[l], arr[r]);
}
std::swap(arr[left], arr[l]);
quickSort(arr, left, l-1);
quickSort(arr, l+1, right);
}
示例
输入：[7, 2, 1, 6, 8]
输出：[1, 2, 6, 7, 8]
选择排序
算法原理
每次遍历未排序部分，找到最小元素与未排序部分的第一个元素交换。重复此过程直到整个数组有序。
时间复杂度
O(n²)
实现代码
void selectionSort(int arr[], int size) {
for(int i = 0; i < size-1; i++) {
int minIndex = i;
for(int j = i+1; j < size; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
示例
输入：[9, 3, 5, 1, 7]
输出：[1, 3, 5, 7, 9]
堆排序
算法原理
构建最大堆，重复提取堆顶元素（最大值）并重新调整堆。通过维护堆结构实现排序。
时间复杂度
O(n log n)
实现代码
void heapify(int arr[], int size, int index) {
int largest = index;
int left = 2*index + 1;
int right = 2*index + 2;
if(left < size && arr[left] > arr[largest]) {
largest = left;
}
if(right < size && arr[right] > arr[largest]) {
largest = right;
}
if(largest != index) {
std::swap(arr[index], arr[largest]);
heapify(arr, size, largest);
}
}
void heapSort(int arr[], int size) {
for(int i = size/2 - 1; i >= 0; i--) {
heapify(arr, size, i);
}
for(int i = size-1; i > 0; i--) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
示例
输入：[4, 10, 3, 5, 1]
输出：[1, 3, 4, 5, 10]
