打开网页出现网站建设中,阿里云网站建设如何,网站后台安全性,用spl做网站排序算法
排序算法可以分为内部排序和外部排序#xff0c;内部排序是数据记录在内存中进行排序#xff0c;而外部排序是因排序的数据很大#xff0c;一次不能容纳全部的排序记录#xff0c;在排序过程中需要访问外存。 常见的内部排序算法有#xff1a;插入排序、希尔排序…排序算法
排序算法可以分为内部排序和外部排序内部排序是数据记录在内存中进行排序而外部排序是因排序的数据很大一次不能容纳全部的排序记录在排序过程中需要访问外存。 常见的内部排序算法有插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等
排序算法的稳定性
稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的当有两个相等键值的纪录R和S且在原本的列表中R出现在S之前在排序过的列表中R也将会是在S之前。 例如序列
51313271如果按照数组的第一个值进行排序 稳定性算法排序后不会改变31和32的次序结果为
31325171非稳定性算法排序后可能会改变31和32的次序结果为
32315171一、冒泡排序稳定性排序
最坏时间复杂度O(n^2) 最好时间复杂度O(n) 平均时间复杂度O(n^2) 空间复杂度:O(1)
1. 冒泡排序的思路不额外增加空间依次遍历相邻元素两两交换 首先从数组索引为0的位置开始遍历比较该元素A和下一个元素B的大小如果A更大则交换AB的位置直到遍历到末尾整体遍历一次之后保证了最后一位是最大的。但是除最后一位以外前面的元素还是无序的状态所以在下一次遍历时按照上面的比较则再从头到尾 这里的尾指的是无序数组的尾即不包括之前遍历过程中已经被放到数组尾部排好序的其他元素 进行比较与交换。直到把所有的元素遍历完成。 2. python实现 参考 def BubbleSort(array):arr_len len(array)# 遍历的次数外循环从第一位迭代至最后一位for i in range(arr_len-1):# 一次遍历内需要比较和交换的次数# 内循环将第一位迭代比较至arr_len-i位因为i位置后的是已经排好序的不用重复比较for j in range(arr_len-i):if (j 1 arr_len):breakelif(array[j] array[j1]): temparray[j]array[j]array[j1]array[j1]tempelse:continuereturn array选择排序非稳定性排序
最坏时间复杂度O(n^2) 最好时间复杂度O(n^2) 平均时间复杂度O(n^2) 空间复杂度:O(1)
1. 选择排序的思路不额外增加空间依次遍历不一定是相邻元素两两交换 无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候数据规模越小越好。 具体来说假设长度为n的数组arr要按照从小到大排序那么先从n个数字中找到最小值min1如果最小值min1的位置不在数组的最左端(也就是min1不等于arr[0])则将最小值min1和arr[0]交换接着在剩下的n-1个数字中找到最小值min2如果最小值min2不等于arr[1]则交换这两个数字依次类推直到数组arr有序排列 如果冒泡排序是从数组的末端开始依次变的有序那么选择排序就是从数组的起始段开始变得有序
2. python实现
def SelectSort(array):for i in range(len(array)-1): # 最后一个数字不用比较一定是最大的min array[i]min_index ifor j in range(i1,len(array)):if(array[j] min):min array[j]min_index j # 记录比min小的数的下标else:continueif(min_index ! i): # 如果i位置不是最小的就不用交换temparray[i]array[i]array[min_index]array[min_index]tempelse:continue # 否则就不交换从下一个i再次开始遍历return array插入排序稳定性排序
最坏时间复杂度O(n^2) 最好时间复杂度O(n) 平均时间复杂度O(n^2) 空间复杂度:O(1)
1. 插入排序思路不额外增加空间依次遍历相邻元素两两交换 插入排序可以理解为无序数组和有序数组两个部分这里的插入就是指将无序数组中的元素插入到有序数组的合适位置假如一个数组[5,2,3,1]把5当成初始的有序数组剩余元素[2,3,1]为无序数组我们的目的就是遍历无序数组再从后往前扫描有序数组如果无序数组中的元素比有序数组中的元素小就说明需要把这个元素插入到有序数组中。 2比5小交换2和5的位置 3比5小交换3和5的位置但是3比2大所以不交换3和2的位置…依次类推
2. 代码实现 def insertSort(self,array):for i in range(1,len(array)): # 无序数组indexi-1while index -10: # 无序数组中第一个元素和有序数组中所有元素进行比较交换直到无序数组的元素大于有序数组里面的结束交换if array[index1]array[index]:temparray[index]array[index]array[index1]array[index1]tempindex-1else:breakreturn array快速排序非稳定算法
最坏时间复杂度O(n^2) 最好时间复杂度O(nlogn) 平均时间复杂度O(nlogn) 空间复杂度:O(n*logn)
1. 快速排序算法思路 通过一趟排序将待排记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分记录继续进行排序已达到整个序列有序。一趟快速排序的具体过程可描述为从待排序列中任意选取一个记录(通常选取第一个记录)作为基准值然后将记录中关键字比它小的记录都安置在它的位置之前将记录中关键字比它大的记录都安置在它的位置之后
2.python实现 参考 def QuickSort(array,left,right):# 选取数组的一个数为基准数i leftj rightif(left right):pivot array[left]while(left right):# 在找得到比基准小的数之前直从后往前找否则交换while(left right and array[right] pivot): # 当前i的位置为基准值right right -1if(left right):swap(array,left,right)# 在找到比较基准大的数之前一直从前往后找 否者交换while(left right and array[left] pivot): # 当前j的位置为基准值left left 1if (left right):swap(array, left, right)# 递归的进行左右两部分的快排QuickSort(array, i, right-1) # 左边QuickSort(array, right1, j) # 右边return array
