这种分类技术与卡片分类技术相似,换句话说,我们使用插入分类机制对卡片进行分类。对于这项技术,我们从数据集中拾取一个元素,并移动数据元素以放置一个位置,以便将拾取的元素插入回数据集中。
时间复杂度:最佳情况为O(n),平均情况和最差情况为O(n ^ 2)
空间复杂度:O(1)
Input: The unsorted list: 9 45 23 71 80 55 Output: Array before Sorting: 9 45 23 71 80 55 Array after Sorting: 9 23 45 55 71 80
insertionSort(array, size)
输入-数据数组,以及数组中的总数
输出&− 排序后的数组
Begin for i := 1 to size-1 do key := array[i] j := i while j > 0 AND array[j-1] > key do array[j] := array[j-1]; j := j – 1 done array[j] := key done End
#include<iostream> using namespace std; void display(int *array, int size) { for(int i = 0; i<size; i++) cout << array[i] << " "; cout << endl; } void insertionSort(int *array, int size) { int key, j; for(int i = 1; i<size; i++) { key = array[i];//take value j = i; while(j > 0 && array[j-1]>key) { array[j] = array[j-1]; j--; } array[j] = key;//insert in right place } } int main() { int n; cout << "Enter the number of elements: "; cin >> n; int arr[n]; //create an array with given number of elements cout << "输入元素:" << endl; for(int i = 0; i<n; i++) { cin >> arr[i]; } cout << "Array before Sorting: "; display(arr, n); insertionSort(arr, n); cout << "Array after Sorting: "; display(arr, n); }
输出结果
Enter the number of elements: 6 输入元素: 9 45 23 71 80 55 Array before Sorting: 9 45 23 71 80 55 Array after Sorting: 9 23 45 55 71 80