七叶笔记 » golang编程 » 插入排序 python golang 实现

插入排序 python golang 实现

分类: golang编程 | 浏览: 249

思路：从下标为1的地方开始遍历数组，选择 J 插入到前面有序队列的合适位置，保证前面部分有序

C++实现: 

 template<typename T>
void insertionSort(T arr[], int n) {
   for (int i = 1; i < n; i++)
      for (int j = i; j > 0; j--) {
         if (arr[j] < arr[j - 1])
            swap(arr[j], arr[j - 1]);
         else
            break;
      }
}

GoLang实现: 

 func insertSort(slice []int) {
   for i := 1; i < len(slice); i++ {
      for j := i; j > 0; j-- {
         if slice[j] < slice[j-1] {
            slice[j], slice[j-1] = slice[j-1], slice[j]
         } else {
            break
         }
      }
   }
}

python实现: 

 def insertSort(lst):
    for i in range(1,len(lst)):
        for j in range(i,0,-1):
            if lst[j-1]>lst[j]:
                lst[j-1],lst[j]=lst[j],lst[j-1]
            else:
                break

插入排序为稳定排序，时间复杂度为 O(n^2)

相关文章