数据结构与算法 01
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
image
1. 冒泡排序
def bubbleSort(arr,sortFlag=True):
'''
冒泡排序 时间复杂系数 θ(n^2),空间O(1)
vs插入排序，
冒泡排序: 依次比较没有拍好顺序的 队列，找到最值，拼在已经排好顺序的队列后面
插入排序: 依次与拍好顺序的值进行比较，找到合适位置进行插入
冒泡排序，开始没有排好顺序的数据多，循环次数多，随着排好队列的数据增多，剩余乱序的数据越少
插入排序，开始排好顺序的数据少，随着排好顺序的数据增多，比较增多
'''
arrLength = len(arr)
tmpValue = None
for i in range(0,arrLength-1):
for j in range(1,arrLength-i):
if (arr[j-1]>arr[j]) ==sortFlag:
tmpValue = arr[j]
arr[j] = arr[j-1]
arr[j-1] = tmpValue
return arr
image
image
鸡尾酒实现 冒泡
def bubbleSort2(arr,sortFlag=True):
'''
冒泡排序，鸡尾酒实现方式，左侧到右侧冒出一个最值，右侧到左侧再冒出一个最值，中间数据越来越少
'''
left = 0
right = len(arr)
tmpValue = None
while left<right:
for j in range(left,right-1):
if (arr[j]>arr[j+1]) == sortFlag: #当sortFlag==True 小的往左侧移动
tmpValue = arr[j]
arr[j] = arr[j+1]
arr[j+1] = tmpValue
right = right - 1
index = range(left+1,right)
index.reverse()
for j in index:
if (arr[j]<arr[j-1]) == sortFlag: #当sortFlag==True 大的往右侧移动
tmpValue = arr[j]
arr[j] = arr[j-1]
arr[j-1] = tmpValue
left=left + 1
return arr
image
2. 插入排序
def insertSort(arr,sortFlag=True):
'''
插入排序,时间复杂系数 最差 θ(n^2)，最好情况时 θ(n) 空间 O(1)
'''
if(len(arr)<2):
return arr;
cuValue = 0
# 从第二个元素开始变量
for j in range(1,len(arr)):
cuValue = arr[j]
#数组中的上一个元数据坐标
i = j-1
#循环与之前拍好顺序的值进行比较
while(i>=0):
# 比较成真，交换位置，继续拿当前的值，继续与再上一个值比较
if (cuValue<arr[i]) == sortFlag:
arr[i+1]=arr[i]
arr[i]=cuValue
else:
#不为真，直接跳出，位置已经交换好了，没必要继续循环下去了
break;
i=i-1
return arr
image
image
3. 选择排序
def selectSort(arr,sortFlag=True):
'''
选择排序，标记最值 最后交互位置，交互的次数少了，但是循环比较的次数没有减少
和冒泡类似，只是没有每次交互数据，标记了最值数据，最好交换位置，遍历数据，和没有排好顺序的数据进行比较，标记
'''
arrLength = len(arr)
keyIndex = None
keyValue = None
#从第一个位置开始循环到长度-1 的位置
for i in range(0,arrLength-1):
# 标记最值的 坐标和值
keyIndex = i
keyValue = arr[i]
#循环剩余位置的数据 从i+1，找到最值进行标记
for j in range(i+1,arrLength):
if (keyValue>arr[j]) == sortFlag:
keyIndex = j
keyValue=arr[j]
#如果最值的标记和i的位置不一致，进行交换位置，i 之前的数组是拍好顺序的
if keyIndex!=i:
arr[keyIndex] = arr[i]
arr[i] = keyValue
return arr
image
image
4. 归并排序
def mergeSort(arr,sortFlag=True):
'''
合并 二分排序,方法递归，时间复杂系数 θ (nlgn) 空间 O(1)
'''
nlength = len(arr)
#如果长度大于2，进行二分
if(nlength>2):
harf = nlength/2
#元数组查成俩，进行排序
arr1 = mergeSort(arr[0:harf],sortFlag)
arr2 = mergeSort(arr[harf:],sortFlag)
arr = []
#俩数组进行合并
while True:
#有一个数组空了，直接拼加上就行了
if len(arr1)==0 or len(arr2)==0:
arr.extend(arr2)
arr.extend(arr1)
break
#判断合并时，先pop哪个数组里的一个最小坐标的
if (arr1[0] < arr2[0]) == sortFlag:
arr.append(arr1.pop(0))
else:
arr.append(arr2.pop(0))
elif(nlength==2):
#如果长度=2，进行比较，交换位置
if(arr[0]>arr[1]) == sortFlag:
tmp = arr[1]
arr[1] = arr[0]
arr[0] = tmp
else:
#长度=1 时不做任何事
pass
return arr
image
使用归并排序为一列数字进行排序的宏观过程：[图片上传失败...(image-ef24a5-1538122813391)]
5. 快速排序
def quickSort2(arr,sortFlag=True):
'''
快速排序，与二分排序类似，复杂系数 最差 和冒泡一样，θ(n^2) 平均 θ(nlgn)，类似二分，mergeSort，递归实现，找出轴位置，再对轴位置左右进行排序
难点在于找到轴位，对轴位左右进行排序
'''
def sorting(arr,left,right,sortFlag):
if left>=right:
return arr;
i=left
pivotIndex = None
j = right
pivot=arr[left]
t = None
while i!=j:
while (arr[j]>pivot)==sortFlag and (arr[j]!=pivot) and i<j:
j=j-1
while ((arr[i]<pivot)==sortFlag or arr[i]==pivot) and i<j:
i=i+1
if i<j:
t = arr[i]
arr[i]=arr[j]
arr[j]=t
if i==j:
pivotIndex= i
if pivotIndex!=None and pivotIndex!=left:
arr[left]=arr[pivotIndex]
arr[pivotIndex]=pivot
sorting(arr,left,i-1,sortFlag)
arr = sorting(arr,i+1,right,sortFlag)
return arr
return sorting(arr,0,len(arr)-1,sortFlag)
image
6. 希尔排序
希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n^2)的排序（冒泡排序或直接插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
希尔排序的代码如下：
def shellSort(arr,sortFlag=True):
'''
希尔排序
最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
最优时间复杂度 ---- O(n)
平均时间复杂度 ---- 根据步长序列的不同而不同。
所需辅助空间 ------ O(1)
稳定性 ------------ 不稳定
'''
h = 0
n = len(arr)
while h<=n:
h = 3 * h + 1 # 计算合适的步长
while (h >= 1):
for i in range(h,n):
j = i - h
get = arr[i]
while (j >= 0 and (arr[j] > get)==sortFlag):
arr[j + h] = arr[j]
j = j - h
arr[j + h] = get
h = (h - 1) / 3; # 递减修改步长
return arr
以23, 10, 4, 1的步长序列进行希尔排序：
image
参考
网友评论