网站色彩搭配表,适合初学者做的网页,设计制作幻灯片母版的菜单是,建筑网方成龙在 C 语言中#xff0c;可以通过嵌套循环和比较运算符来实现常见的排序算法#xff0c;比如冒泡排序、选择排序或插入排序 目录
基础算法#xff1a;
1.冒泡排序#xff08;Bubble Sort#xff09;
2.选择排序#xff08;Selection Sort#xff09;
3.插入排序…在 C 语言中可以通过嵌套循环和比较运算符来实现常见的排序算法比如冒泡排序、选择排序或插入排序 目录
基础算法
1.冒泡排序Bubble Sort
2.选择排序Selection Sort
3.插入排序Insertion Sort
高级算法
1. 快速排序Quick Sort
2. 归并排序Merge Sort
3. 堆排序Heap Sort 基础算法简单易实现冒泡排序、选择排序、插入排序
高级算法性能更优快速排序、归并排序、堆排序
基础算法
1. 冒泡排序Bubble Sort
冒泡排序是简单直观的排序方法通过多次比较相邻元素并交换位置来排序。
#include stdio.hvoid 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]) { // 如果当前元素大于后一个元素则交换int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}
}int main() {int arr[] {5, 2, 8, 3, 7};int size sizeof(arr) / sizeof(arr[0]);printf(排序前: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);bubbleSort(arr, size);printf(排序后: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);return 0;
}备注说明这里在内循环jsize-i-1的目的是因为每进行一次外层循环数组末尾的一个最大元素会被排序好因此后续的内层循环会减少比较的次数。 2.选择排序Selection Sort
选择排序通过在未排序部分找到最小最大元素然后将其与未排序部分的第一个元素交换位置。
#include stdio.hvoid 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; // 找到更小的元素}}// 交换最小值和当前位置int temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}
}int main() {int arr[] {5, 2, 8, 3, 7};int size sizeof(arr) / sizeof(arr[0]);printf(排序前: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);selectionSort(arr, size);printf(排序后: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);return 0;
}备注说明
3.插入排序Insertion Sort
插入排序通过逐步将未排序部分的元素插入到已排序部分的正确位置来排序。
#include stdio.hvoid 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;}
}int main() {int arr[] {5, 2, 8, 3, 7};int size sizeof(arr) / sizeof(arr[0]);printf(排序前: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);insertionSort(arr, size);printf(排序后: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);return 0;
}高级算法
1. 快速排序Quick Sort
快速排序是一种分治算法通过选定一个“基准”pivot将数组分为两部分递归排序子数组。
#include stdio.hvoid quickSort(int arr[], int low, int high) {if (low high) {int pivot arr[low]; // 基准int i low, j high;while (i j) {while (i j arr[j] pivot) j--; // 从右向左找小于基准的if (i j) arr[i] arr[j]; // 放到左边while (i j arr[i] pivot) i; // 从左向右找大于基准的if (i j) arr[j--] arr[i]; // 放到右边}arr[i] pivot; // 基准放在最终位置quickSort(arr, low, i - 1); // 排序左边部分quickSort(arr, i 1, high); // 排序右边部分}
}int main() {int arr[] {5, 2, 8, 3, 7};int size sizeof(arr) / sizeof(arr[0]);printf(排序前: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);quickSort(arr, 0, size - 1);printf(排序后: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);return 0;
}2. 归并排序Merge Sort
归并排序也是一种分治算法分为两部分分别排序再合并为有序数组。
#include stdio.hvoid merge(int arr[], int left, int mid, int right) {int n1 mid - left 1;int n2 right - mid;int L[n1], R[n2];// 将数据复制到临时数组for (int i 0; i n1; i) L[i] arr[left i];for (int i 0; i n2; i) R[i] arr[mid 1 i];int i 0, j 0, k left;while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];} else {arr[k] R[j];}}while (i n1) arr[k] L[i];while (j n2) arr[k] R[j];
}void mergeSort(int arr[], int left, int right) {if (left right) {int mid left (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);merge(arr, left, mid, right);}
}int main() {int arr[] {5, 2, 8, 3, 7};int size sizeof(arr) / sizeof(arr[0]);printf(排序前: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);mergeSort(arr, 0, size - 1);printf(排序后: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);return 0;
}3. 堆排序Heap Sort
堆排序通过构造一个堆最大堆或最小堆来实现排序。
#include stdio.hvoid heapify(int arr[], int size, int root) {int largest root;int left 2 * root 1;int right 2 * root 2;if (left size arr[left] arr[largest]) largest left;if (right size arr[right] arr[largest]) largest right;if (largest ! root) {int temp arr[root];arr[root] arr[largest];arr[largest] temp;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--) {int temp arr[0];arr[0] arr[i];arr[i] temp;heapify(arr, i, 0);}
}int main() {int arr[] {5, 2, 8, 3, 7};int size sizeof(arr) / sizeof(arr[0]);printf(排序前: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);heapSort(arr, size);printf(排序后: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);return 0;
}
