因为对算法这一项实在是弱爆了,对自己从零开始学习,慢慢记录过程,加油哦
再因为最近在学习python和lua,就分别用两种语言都实现了
快速插入排序
基本思想:(假设是:从小到大,升序)
每次选择一个元素K插入已排好序的L[1...i]部分,如果L[x]>K,则K插入到L[x]前面,
要对L[x]后面的元素进行后移
时间复杂度:
最好情况:正序有序(从小到大)只需比较n次,不需要移动,复杂度O(n)
最坏情况:逆序有序(从大到小),插入第2个元素需要考察前1个元素,插入第3个元素需要考察前2个元素...插入第n个元素需要考察前n-1个元素,等差数列求和得n^2/2,
所以,复杂度为O(n^2)
稳定性:
稳定性,就是有两个相同的元素,排序先后的相对位置是否变化,
插入排序中,K如果和L[x]相等,直接插入L[x]后面,这样不用后移元素,所以插入排序是稳定的排序
代码示例1:python代码:quick_insert_sort.py
def quick_insert_sort(l):
for i in range(1, len(l)): #python数组下标是从0开始的
tmp = l[i]
j = i - 1
while(j >= 0 and tmp < l[j]): #进行元素后移操作
l[j+1] = l[j]
j -= 1
l[j+1] = tmp #将待插入元素放到j+1位置
print('result:' + str(l))
if __name__ == '__main__':
quick_insert_sort([74,62,97,88,8,75,49,16,9])
代码示例2:lua代码quick_insert_sort.lua
function quick_insert_sort(t)
len = table.getn(t)
for i=2,len do --lua table下标是1开始的
tmp = t[i]
j = i - 1
while(j > 0 and tmp < t[j]) do --元素后移
t[j+1] = t[j]
j = j - 1
end
end
end
t = {65,71,21,13,84,49,106,56,98}
quick_insert_sort(t)
for _,v in ipairs(t) do
print(v)
end
分享到:
相关推荐
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
NULL 博文链接:https://xieyan30.iteye.com/blog/1922400
排序算法:排序算法汇总--各类排序算法 冒泡,选择,插入,快排,归并,堆排
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...
C语言版的排序方法---插入排序,非常有用的代码,可以实际中使用。
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...
详解Java常用排序算法-插入排序
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
这是C语言的冒泡、插入法、选择排序算法分析-word版本
Python算法之---冒泡,选择,插入排序算法.py
用c++类实现多种排序算法。一个类中实现全部算法,另一个类中实现界面设置和控制。
排序作为最基础的算法,有选择排序,冒泡排序,插入排序,希尔排序,堆排序,快速排序,归并排续等,我会用c++写一下,欢迎交流~
输入n个数,用直接插入排序算法排序,并输出这n个数
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...