当前位置： 首页 > news >正文

个人网站设计论文前言,广西钦州有做网站的公司吗,沈阳网站优化公司,做网页公司常见的排序算法 排序是最常用的算法#xff0c;常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外#xff0c;还有桶排序、堆排序、基数排序和计数排序。 1、冒泡排序 冒泡排序就是把小的元素往前放或大的元素往后放#xff0c;比较…常见的排序算法 排序是最常用的算法常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外还有桶排序、堆排序、基数排序和计数排序。 1、冒泡排序 冒泡排序就是把小的元素往前放或大的元素往后放比较的是相邻的两个元素。 时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( 1 ) O(1) O(1)稳定排序。 思想 1比较相邻的两个元素如果第一个比第二个大就交换它俩的位置 2对每一对相邻元素作同样的工作从开始第一对到最后一对一趟下来最后的元素会是最大的数 3针对所有的元素重复以上的步骤除了最后一个 4持续每次对越来越少的元素重复上面的步骤直到没有任何一对元素需要比较。此时该数组排好序。 def bubbleSort(list_1):len_1 len(list_1)# 需要遍历的趟数for i in range(len_1):# 相邻元素的比较次数for j in range(len_1-i-1):# 如果第一个比第二个大则交换两个元素的顺序if list_1[j]list_1[j1]:list_1[j], list_1[j1] list_1[j1], list_1[j]return list_1 改进后的排序算法如果在一轮遍历中没有发生元素交换就可以确定列表已经有序。可以修改冒泡排序函数使其在遇到这种情况时提前终止。 def shortBubble(list_2):# 判断是否需要交换exchange Falselen_2 len(list_2)# 如果在一轮遍历中没有发生元素交换则提前终止for i in range(len_2):exchange Falsefor j in range(len_2-i-1):if list_2[j] list_2[j1]:list_2[j], list_2[j1] list_2[j1], list_2[j]if not exchange: breakreturn list_22、选择排序 选择排序给每个位置选择当前最小的元素。 算法思想 1在所有数组中找到最小大元素将其存放到数组的起始位置 2在剩余元素中继续找最小大元素然后依次放到已排序数组的末尾 3重复操作直到所有元素均排列好。 时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( 1 ) O(1) O(1)非稳定排序 def selectionSort(list_3):len_3 len(list_3)for i in range(len_3):minIndex ifor j in range(i1, len_3):if list_3[j] list_3[minIndex]:minIndex jlist_3[i], list_3[minIndex] list_3[minIndex], list_3[i]return list_33、插入排序 插入排序在一个已经有序的小数组上依次插入一个元素 算法思想 1从第一个元素开始该元素被认为是已经排好序的小数组 2取出下一个元素在已经排好序的小数组中从后向前遍历 3如果排好序小数组的末尾元素大于待插入元素将该末尾元素移动到下一个位置并找小数组末尾元素的前面一个元素 4重复步骤3直到找到已排序的元素小于或等于待插入元素的位置 5将待插入元素插入到该位置后重复步骤2-5直到该数组是有序的。 时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( 1 ) O(1) O(1)稳定排序 def insertionSort(list_4):len_4 len(list_4)#遍历除第一个元素外的所有元素for i in range(1, len_4):# 若第i个元素大于i-1元素直接插入if list_4[i] list_4[i-1]:j i - 1# 待插入元素value list_4[i]while j 0 and value list_4[j]:# 向后移动元素list_4[j1] list_4[j]j - 1list_4[j1] valuereturn list_44、快速排序 快速排序选取一个基准值分成两段左边放小于基准值的所有数右边放大于基准值的数。 思想 1选取基准值 2将比基准值小的元素交换到前面比基准值大的元素交换到后面 3对左右区间重复步骤2直到各区间只有一个数。

分区操作

def partition(alist, first, last):# 基准pivotVal alist[first]# 左右两个leftMark first 1rightMark lastflag Falsewhile not flag:# 加大leftMark直到遇到一个大于基准的元素while alist[leftMark] pivotVal and leftMark rightMark:leftMark 1# 减少rightMark,直到遇到一个小于基准的元素while alist[rightMark] pivotVal and leftMark rightMark:rightMark - 1# 当rightMark leftMark时过程终止if rightMark leftMark:flag Trueelse:#将rightMark对应的元素与当前位于分割点的元素互换alist[leftMark], alist[rightMark] alist[rightMark], alist[leftMark]alist[leftMark], alist[rightMark] alist[rightMark], alist[leftMark]return rightMarkdef quickSortHelper(alist, first, last):if first last:mid partition(alist, first, last)quickSortHelper(alist, first, mid)quickSortHelper(alist, mid1, last)def quickSort(alist):quickSortHelper(alist, 0, len(alist)-1)5、希尔排序 希尔排序是插入排序的一种变种为了加快速度改进的插入排序交换不相邻的元素以对数组的局部进行排序。 思想 1让数组中任意间隔为 h h h 的元素有序 2刚开始 h l e n g t h / 2 h length / 2 hlength/2 3接着让 h l e n g t h / 4 h length / 4 hlength/4让 h h h 一直缩小直到 h 1 h1 h1此时数组中任意间隔为1的元素有序。

对每个子序列进行插入排序需要得到子序列的起始点和长度

def gapInsertSort(list_6, start, gap):for i in range(startgap, len(list_6), gap):# 当前待插入元素curValue list_6[i]j i - gapif list_6[i] list_6[i-gap]:while j 0 and curValue list_6[j]:list_6[jgap] list_6[j]j - gaplist_6[jgap] curValuereturn list_6def shellSort(list_6):# 获取每个子序列的长度subListLen len(list_6) // 2# 子序列的长度要始终大于0while subListLen 0:# 起始位置的取值for startPos in range(subListLen):# 分段进行插入排序gapInsertSort(list_6, startPos, subListLen)# 每次都将子序列的长度减少一半subListLen subListLen // 2return list_66、归并排序 思想将一个无序数组有序首先将这个数组分成两个然后对这两个数组分别进行排序之后再把这两个数组合并成一个有序的数组。此时该数组就有序了。

合并两个有序数组

def merge(list_7, list_8):# 分别获取两个子序列的下标index1 0index2 0# 分别获取两个子序列的长度len_7 len(list_7)len_8 len(list_8)list_sum []while index1 len_7 or index2 len_8:if list_7[index1] list8[index2]:list_sum.append(list_8[index2])index2 1else:list_sum.append(list_7[index1])index1 1list_sum list_7[index1:]list_sum list_8[index2:]return list_sumdef mergeSort(list_9):# 原数组的长度不能少于2if len(list_9) 2:return list_9# 进行二路归并mid len(list_9) // 2# 左边进行归并排序left merge(list_9[:mid])# 右边进行归并排序right merge(list_9[mid:])return merge(left, right)