排序算法简述1

&＃xff08;拿一个数去和其他数比&＃xff09;数组中的一个元素分别和数组中的其他元素比较&＃xff0c;满足一定要求时&＃xff0c;便将两数的索引进行交换&＃xff0c;不停的进行此操作。&＃xff08;此方法表示在原地进行&＃xff09;

def bubble_sort(li):for i in range(len(li)-1): #第i趟排序for j in range(len(li)-i-1):if li[j]>li[j&＃43;1]: #升序&＃xff0c;若要降序排序将大于号改为小于号即可li[j],li[j&＃43;1]&＃61;li[j&＃43;1],li[j]
选择排序

不停遍历整个数组&＃xff0c;将满足要求的元素取出放入一个新列表中

(此代码复杂度较高&＃xff09;
def select_sort_simple(li):li&＃61;[]for i in range(len(li)):min_val&＃61;min(li)li.append(min_val)li.remove(min_val)return li

插入排序

插入排序&＃xff1a;&＃xff08;用其他数与一个数比&＃xff09;控制前方数字&＃xff0c;将后面的数字陆续与前方的数字做比较&＃xff0c;满足要求时便将数字插入即可&＃xff08;原地进行&＃xff09;

def insert_sort(li):for i in range(1,len(li)):tmp&＃61;li[i]j&＃61;i-1while li[j]>tmp and j>&＃61;0:li[j&＃43;1]&＃61;li[j]j-&＃61;1li[j&＃43;1]&＃61;tmp

快速排序

先将第一个元素取出&＃xff0c;然后现在开始用右边的数与其比较&＃xff0c;若有一个比其小的数&＃xff0c;便将这个数移到取出的第一个元素的位置&＃xff0c;这时&＃xff0c;这个数的位置便又空了&＃xff0c;接着就需要看左边比取出元素大的数&＃xff0c;将其移到右边空的位置&＃xff0c;然后再看右边比取出元素小的数移到左边的位置&＃xff0c;周而复始的左右左右移动&＃xff0c;即可完成程序

def partition(li,left,right): #left表示第一个元素的索引&＃xff0c;即0&＃xff1b;right表示最后一个元素的索引&＃xff0c;即len(li)-1tmp&＃61;li(left)while left<right:while li[right]>&＃61;tmp and left<right:right-&＃61;1li[left]&＃61;li[right]while left<right and li[left]<&＃61;tmp:left&＃43;&＃61;1li[right]&＃61;li[left]li[left]&＃61;tmp

归并排序

归并排序&＃xff1a;即对序列的元素进行逐层折半分组&＃xff0c;然后从最小分组开始比较排序&＃xff0c;合并成一个大的分组&＃xff0c;逐层进行&＃xff0c;最终所有的元素都是有序的。归并一般使用情况是先分解&＃xff0c;即将列表越分越小&＃xff0c;直至分成一个元素&＃xff1b;终止条件是当一个元素是有序的&＃xff1b;最后是合并是将两个有序列表归并&＃xff0c;列表越来越大.

def merge(li,low,mid,high):i&＃61;lowj&＃61;mid&＃43;1tmp&＃61;[]while i<&＃61;mid and j<&＃61;high:if li[i]<li[j]:tmp.append(li[i])i&＃43;&＃61;1else:tmp.append(li[j])j&＃43;&＃61;1while i<&＃61;mid:tmp.append(li[i])i&＃43;&＃61;1while j<&＃61;high:tmp.append(li[i])j&＃43;&＃61;1li[low:high&＃43;1]&＃61;tmp

希尔排序

是一种分组插入排序算法&＃xff0c;首先取一个整数d1&＃61;n//2&＃xff0c;将元素分为d1个组&＃xff0c;每组相邻量元素之间距离为d1&＃xff0c;在各组内进行直接插入排序&＃xff0c;同理之后取第二个整数d2&＃61;d1//2&＃xff0c;继续以上操作&＃xff0c;直至dn&＃61;1&＃xff0c;就表明已将所有元素在同一组内进行直接插入排序。注&＃xff1a;希尔排序每次遍历排序并没有使一些元素有序&＃xff0c;是混乱的&＃xff0c;但是整体是趋于有序的

def insert_sort_gap(li,gap):for i in range(gap,len(li)):tmp&＃61;li[i]j&＃61;i-gapwhile j>&＃61;0 and li[j]>tmp:li[j&＃43;gap]&＃61;li[j]j-&＃61;gapli[j&＃43;gap]&＃61;tmpprint(li)def shell_sort(li):d&＃61;len(li)//2while d>&＃61;1:insert_sort_gap(li,d)d//&＃61;2