Insertion sort
时间: 2024-06-18 16:04:05 浏览: 13
插入排序是一种简单的排序算法,它通过对数组中的元素进行比较和交换来排序。其基本思想是将一个待排序的数组分为两部分,第一部分是已排序的数组,一开始只有一个元素,第二部分是未排序的数组,初始时包含除第一个元素之外的所有元素。排序过程从第二部分开始,每次将一个未排序的元素插入到已排序数组中的适当位置,直到所有元素都被排序为止。插入排序的时间复杂度为O(n^2)。
以下是一个Python的实现。
```python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
```
相关问题
c++insertion sort
插入排序(Insertion Sort)是一种简单直观的排序算法。它的基本思想是将待排序的数组分为已排序和未排序两部分,每次从未排序部分取出一个元素,插入到已排序部分的合适位置,直到全部元素都被插入完毕。
以下是C语言实现插入排序的代码示例:
```C
#include <iostream>
using namespace std;
void insertionSort(int a[], int len) {
for (int i = 1; i < len; i++) {
int j = i - 1;
int temp = a[i];
while (j >= 0 && a[j] > temp) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
int main() {
int a[10] = { 7, 1, 12, 10, 6, 2, 8, 4, 3, 5 };
int len = sizeof(a) / sizeof(a[0]);
insertionSort(a, len);
for (int i = 0; i < len; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}
```
在上述代码中,我们通过`insertionSort`函数实现了插入排序算法,然后在`main`函数中调用该函数对数组进行排序。最后,我们使用循环打印排序后的数组。
Python insertion sort
Sure, here's an implementation of the insertion sort algorithm in Python:
```python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
```
To use this function, simply pass in an array of integers:
```python
my_array = [4, 2, 7, 1, 3]
sorted_array = insertion_sort(my_array)
print(sorted_array) # Outputs [1, 2, 3, 4, 7]
```
The insertion sort algorithm works by iterating through each element in the array one by one, and inserting it into its correct position among the already sorted elements. It does this by comparing the current element to each of the previous elements, and swapping them if necessary until the current element is in the correct position.