用函数模版写出插入排序算法c++
时间: 2024-01-14 20:03:18 浏览: 29
以下是使用函数模板写出插入排序算法的C++代码:
```c++
template <typename T>
void insertionSort(vector<T>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
T key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
```
该算法使用了模板,可以对任何类型的数组进行排序。在排序过程中,将数组分为已排序和未排序两部分,每次从未排序部分中取出一个元素,插入到已排序部分中的正确位置。时间复杂度为O(n^2)。
相关问题
用函数模版写出归并排序算法c++
以下是使用函数模板写出归并排序算法的C++代码:
```c++
#include <vector>
using namespace std;
template<typename T>
void merge(vector<T>& v, int left, int mid, int right) {
vector<T> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (v[i] <= v[j]) {
temp[k++] = v[i++];
} else {
temp[k++] = v[j++];
}
}
while (i <= mid) {
temp[k++] = v[i++];
}
while (j <= right) {
temp[k++] = v[j++];
}
for (int p = 0; p < k; p++) {
v[left + p] = temp[p];
}
}
template<typename T>
void merge_sort(vector<T>& v, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(v, left, mid);
merge_sort(v, mid + 1, right);
merge(v, left, mid, right);
}
}
```
归并排序是一种分治算法,它将一个大问题分成两个小问题,然后递归地解决这两个小问题,最后将它们的解合并起来得到大问题的解。在归并排序中,我们将待排序的数组分成两个部分,分别对它们进行排序,然后将它们合并起来。归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。
使用java代码写出插入排序算法
以下是Java实现的插入排序算法代码:
```java
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = { 12, 11, 13, 5, 6 };
insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
}
```