排序算法(二)
排序算法(二)
希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
代码片
下面展示一些 内联代码片
。
// A code block
var foo = 'bar';
arr=[1,4,5,2,7,8,3]
def shellsort(arr):
n=len(arr)
h=1
while h<n/3:
h=3*h+1
while h>=1:
for i in range(h,n):
j=i
while j>=h and arr[j]<arr[j-h]:
arr[j], arr[j-h] = arr[j-h], arr[j]
j-=h
h=h//3
shellsort(arr)
print (arr)
快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。时间复杂是最优O(nlogn)最坏O(n**2)不稳定
代码片
下面展示一些 内联代码片
。
// A code block
var foo = 'bar';
arr=[4,5,2,7,8,3]
def quicksort(arr,first,last):
# n=len(arr)
if first>=last:
return
mid_value=arr[first]
low=first
high=last
while low<high:
while low<high and arr[high]>=mid_value:
high-=1
arr[low]=arr[high]
while low<high and arr[low]<mid_value:
low+=1
arr[high]=arr[low]
arr[low]=mid_value
quicksort(arr,first,low-1)
quicksort(arr,low+1,last)
quicksort(arr,0,len(arr)-1)
print(arr)