冒泡排序
比较相邻的两项,交换顺序排错的项
时间复杂度为O(n^2)
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
选择排序
在未排序的序列中找到最小(或最大)的元素,存放到排序序列的起始位置
时间复杂度为O(n^2)
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;
}
}
// 将最小元素交换到已排序部分的末尾
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
插入排序
将未排序的元素插入到已排序的序列中的适当位置,以达到排序的目的
时间复杂度为O(n^2)
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
// 将大于key的元素向右移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}