插入排序

直接插入思路：

每趟将一个待排序的关键字按照其值的大小，插入到有序序列中的正确的位置，直到全部序列有序。其时间复杂度为$O(n^2)$, 待排序的元素超过$10^5$的规模时是无法承受的。

代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <cstdio> #include <algorithm> template <class T> int getArrayLen(T&array){ return sizeof(array) / sizeof(array[0]); } //插入排序的代码 void insertSort(int A[],int n){ for(int i = 1; i<= n; i++){ int temp = A[i], j = i; while(j>0 && temp < A[j - 1]){ A[j] = A[j - 1]; j--; } A[j] = temp; } } int main(){ int A[] = {6,3,5,2,1,4}; int n = getArrayLen(A); insertSort(A,n); for(int i = 0; i < n; i++){ printf("%d\n",A[i]); } return 0; }

---

• ← Previous Post
• Next Post →

---