需要一个插入排序算法代码
时间: 2023-11-05 19:03:12 浏览: 39
下面是一个Python实现的插入排序算法代码:
```python
def insertion_sort(array):
for i in range(1, len(array)):
key = array[i]
j = i - 1
while j >= 0 and array[j] > key:
array[j + 1] = array[j]
j -= 1
array[j + 1] = key
return array
```
这个算法的思路是将数组分为已排序的部分和未排序的部分。在每次循环中,从未排序的部分中选取一个元素,插入到已排序的部分中的合适位置,直到所有元素都被插入到已排序的部分中。
在具体实现中,我们从第二个元素开始循环,将其作为key值,然后将其与已排序的部分中的元素比较,找到合适的位置插入。在比较时,我们将已排序的部分中的所有比key值大的元素向右移动一位,直到找到比key值小的元素或者已经遍历完所有已排序的元素。最后,我们将key值插入到找到的位置中。
相关问题
c++写份插入排序算法代码
当然可以!以下是一个使用C++编写的插入排序算法代码示例:
```cpp
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
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--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {5, 2, 8, 12, 1, 6};
int n = sizeof(arr) / sizeof(arr);
insertionSort(arr, n);
cout << "排序后的数组:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
这段代码实现了插入排序算法。插入排序的基本思想是将数组分为已排序和未排序两部分,每次从未排序部分取出一个元素,插入到已排序部分的正确位置。通过不断重复这个过程,最终完成整个数组的排序。
c++插入排序算法代码
以下是C语言的插入排序算法代码:
```c
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
/* 将比 key 大的元素向右移动 */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
```
其中,`arr`是待排序的数组,`n`是数组的大小。算法的时间复杂度是O(n^2)。