【记】基础排序 $O(N^2)$
作者:
老坛算粉
,
2022-05-06 10:22:03
,
所有人可见
,
阅读 188
#include <iostream>
using namespace std;
// 优化 buddleSort ,每次记录 参与交换的最后一个元素
template<typename T>
void buddleSort(T arr[], int n) {
do {
int newN = 0;
for (int i = 0; i < n - 1; i ++ ) {
if(arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
newN = i + 1;
}
}
// n--; // 最后一个元素是当前趟中最大的值,不需要再比较
n = newN;
} while(n);
}
template<typename T>
void insertionSort(T arr[], int n) {
for (int i = 1; i < n; i ++ ) {
T e = arr[i]; // 保存现在的值
int j; // j 从 i 处向前走
for (j = i; j > 0; j -- ) {
if(arr[j - 1] > e) {
arr[j] = arr[j - 1];
} else break;
}
arr[j] = e; // j 是 e 合适的位置
}
}
template <typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n; i ++ ) {
int minIndex = i;
for (int j = i + 1; j < n; j ++ ) {
if(arr[j] < arr[minIndex]) minIndex = j;
}
swap(arr[i], arr[minIndex]);
}
}
int main() {
int arr[8] = {1,2,6,4,7,3,9,0};
// selectionSort(arr, 8);
// insertionSort(arr, 8);
buddleSort(arr, 8);
for(int i=0; i < 8; i ++) cout << arr[i] << " ";
return 0;
}