排序算法是计算机科学中的基础概念,它们用于对数据集合进行有序排列。插入排序(Insertion Sort)是其中一种简单而有效的排序算法。本文将详细介绍插入排序的工作原理,并提供Python、Go、Java和C语言的示例代码。
插入排序的基本思想
插入排序的基本思想是将数据分成已排序和未排序两部分,初始时已排序部分只包含第一个元素,而未排序部分包含其他元素。然后,它从未排序部分依次选择元素,将其插入到已排序部分的合适位置,直到所有元素都在已排序部分。
让我们通过一个简单的示例来理解插入排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4]
,我们希望按升序排序它。
- 初始状态: 首先,已排序部分只包含第一个元素
5
,未排序部分包含其他元素[2, 9, 3, 4]
。 - 第一次插入: 从未排序部分选择第一个元素
2
,将它与已排序部分的5
比较。因为2 < 5
,所以2
插入到5
的前面,得到[2, 5]
和[9, 3, 4]
。 - 第二次插入: 继续选择未排序部分的第一个元素
9
,将它与已排序部分的5
和2
比较。由于9 > 5
,不需要交换。已排序部分保持不变[2, 5]
,未排序部分为[3, 4]
。 - 继续插入: 依此类推,依次选择未排序部分的元素并插入到已排序部分的正确位置。最终,数组被完全排序成
[2, 3, 4, 5, 9]
。
插入排序的关键在于将元素逐个插入到已排序部分,并确保已排序部分始终保持升序。
插入排序的时间复杂度
插入排序的时间复杂度取决于输入数据的顺序。在最好的情况下,即数据已经按升序排列,插入排序的时间复杂度为O(n),其中n是数组的长度。这是因为在最好情况下,不需要执行元素交换,只需遍历一次数组。
在最坏的情况下,即数据逆序排列,插入排序的时间复杂度为O(n^2),因为每个元素都需要与已排序部分的所有元素进行比较和移动。
插入排序在小型数据集上通常表现良好,但对于大型数据集,更高效的排序算法可能更合适。
插入排序的应用场景
尽管插入排序不如一些高级排序算法那样高效,但它仍然有一些应用场景:
- 小型数据集: 插入排序在处理小型数据集时性能良好,因为其常数因子较低。
- 部分有序数据: 如果数据集已经部分有序,插入排序的性能会较好,因为不需要多次交换元素。
- 稳定性要求: 插入排序是一种稳定的排序算法,可以保持相同元素的相对位置。
- 在线排序: 插入排序可以应用于在线排序场景,即数据不一次性全部可用,而是逐个元素到达。
示例代码
以下是插入排序的示例代码,分别使用Python、Go、Java和C语言编写。
Python 插入排序
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
arr = [5, 2, 9, 3, 4]
insertion_sort(arr)
print("排序后的数组:", arr)
Go 插入排序
package main
import "fmt"
func insertionSort(arr []int) {
n := len(arr)
for i := 1; i < n; i++ {
key := arr[i]
j := i - 1
for j >= 0 && key < arr[j] {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func main() {
arr := []int{5, 2, 9, 3, 4}
insertionSort(arr)
fmt.Println("排序后的数组:", arr)
}
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 && key < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 4};
insertionSort(arr);
System.out.print("排序后的数组: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
C 语言 插入排序
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && key < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {5, 2, 9, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("排序后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
这些示例代码演示了插入排序的工作原理,并提供了Python、Go、Java和C语言的不同语言版本的实现。插入排序虽然简单,但在一些特定情况下是一种有效的排序算法,特别适合处理小型数据集或部分有序的数据。
标签:arr,int,插入排序,元素,算法,深入,key,排序 From: https://blog.51cto.com/u_16170163/7443146