大气宽屏的网站,做豆制品的网站,公司创建的法制网站,简单网页设计作品欣赏0.导语 本节为手撕代码系列之第一弹#xff0c;主要来手撕排序算法#xff0c;主要包括以下几大排序算法#xff1a; 直接插入排序 冒泡排序 选择排序 快速排序 希尔排序 堆排序 归并排序 1.直接插入排序 【算法思想】 每一步将一个待排序的记录#xff0c;插入到前面… 0.导语 本节为手撕代码系列之第一弹主要来手撕排序算法主要包括以下几大排序算法 直接插入排序 冒泡排序 选择排序 快速排序 希尔排序 堆排序 归并排序 1.直接插入排序 【算法思想】 每一步将一个待排序的记录插入到前面已经排好序的有序序列中去直到插完所有元素为止。 【代码实现】 # 直接插入排序
def insert_sort(arr):length len(arr)for i in range(length):k ifor j in range(k,0,-1):if arr[j]arr[j-1]:t arr[j]arr[j]arr[j-1]arr[j-1]t
arr [4,3,0,-1]
insert_sort(arr)
print(arr) 2.冒泡排序 【算法思想】 对相邻的元素进行两两比较顺序相反则进行交换这样每一趟会将最小或最大的元素“浮”到顶端最终达到完全有序。 【代码实现】 # 冒泡排序
def bubbleSort(arr):length len(arr)for i in range(length-1):flag Truefor j in range(length-i-1):if arr[j]arr[j1]:t arr[j]arr[j]arr[j1]arr[j1]tflag Falseif flag:break
arr [6,-2,0,9]
bubbleSort(arr)
print(arr) 3.选择排序 【算法思想】 每一趟从待排序的数据元素中选择最小或最大的一个元素作为首元素直到所有元素排完为止简单选择排序是不稳定排序。 【代码实现】 def selectSort(arr):length len(arr)for i in range(length-1):min ifor j in range(i1,length):if arr[min]arr[j]:minjif min!i:t arr[i]arr[i]arr[min]arr[min]t
arr [6,-2,0,9]
selectSort(arr)
print(arr) 4.快速排序 【算法思想】 快速排序思想----分治法。 先从数列中取出一个数作为基准数。 分区过程将比这个数大的数全放到它的右边小于或等于它的数全放到它的左边。 再对左右区间重复第二步直到各区间只有一个数。 每次划分得到枢椎的左边比它小右边比它大。 【代码实现】 方法一(通过遍历直接得到大于pivot和小于pivot的元素) class Solution:def quicksort(self, array)::type numRows: int:rtype: List[List[int]]if len(array)1:return arrayelse:pivotarray[0]small[i for i in array[1:] if ipivot]big[i for i in array[1:] if i pivot]return self.quicksort(small)[pivot]self.quicksort(big) //递归法耗时 方法二(双指针前后移动): def quickSort(arr,left,right):# 递归终止条件if leftright:returnpivot arr[left]i leftj rightwhile ij:while ij and arr[j]pivot:j-1while ij and arr[i]pivot:i1if ij:t arr[i]arr[i] arr[j]arr[j] t# 放入枢椎arr[left] arr[i]arr[i]pivot# 递归调用左区域quickSort(arr,left,i-1)# 递归调用右区域quickSort(arr,i1,right)arr [6,-2,0,9]
quickSort(arr,0,len(arr)-1)
print(arr) 5.希尔排序 【算法思想】 该算法也被称为缩小增量排序。 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止。 【代码实现】 # 希尔排序
def shellSort(arr):length len(arr)# 设置初始增量gap length//2while gap0:# 从第gap个元素逐个对其所在组进行直接插入排序for i in range(gap,length):j iwhile j-gap0 and arr[j]arr[j-gap]:t arr[j]arr[j] arr[j-gap]arr[j-gap] tj-gapgap//2
arr [6,-2,0,9]
shellSort(arr)
print(arr) 6.堆排序 【算法思想】 堆是具有以下性质的完全二叉树每个结点的值都大于或等于其左右孩子结点的值称为大顶堆或者每个结点的值都小于或等于其左右孩子结点的值称为小顶堆。 基本思路 a.将无需序列构建成一个堆根据升序降序需求选择大顶堆或小顶堆; b.将堆顶元素与末尾元素交换将最大元素沉到数组末端;(升序方法) c.重新调整结构使其满足堆定义然后继续交换堆顶元素与当前末尾元素反复执行调整交换步骤直到整个序列有序。 【代码实现】 方法1 class HeapSort:def heapSort(self, nums):length len(nums)# 从后往前遍历交换堆顶与最后叶子节点并依次调整堆重复操作for j in range(length-1,0,-1):# 获取堆顶元素(获取同时调整堆)firstNum self.adjustHeap(nums,j1)# 交换最后一个叶子节点与堆顶元素temp nums[j]nums[j] firstNumnums[0] tempreturn nums# 调整堆(最大堆)每次返回最大堆顶元素def adjustHeap(self,nums,length):# 最后一个非叶节点i length//2 -1# 从最后一个非叶节点开始调整构成最大堆while i0:temp nums[i]k 2*i1while klength:if k1length and nums[k]nums[k1]:k1if nums[k]temp:nums[i]nums[k]ikelse:breakk2*k1nums[i] tempi-1return nums[0]
s HeapSort()
nums [8,9,7,10]
t s.heapSort(nums)
print(t) 方法2 def buildMaxHeap(self,arr):import mathfor i in range(math.floor(len(arr) / 2), -1, -1):self.heapify(arr, i)def heapify(self, arr, i):left 2 * i 1right 2 * i 2largest iif left arrLen and arr[left] arr[largest]:largest leftif right arrLen and arr[right] arr[largest]:largest rightif largest ! i:self.swap(arr, i, largest)self.heapify(arr, largest)def swap(self, arr, i, j):arr[i], arr[j] arr[j], arr[i]def heapSort(self, arr):global arrLenarrLen len(arr)self.buildMaxHeap(arr)for i in range(len(arr) - 1, 0, -1):self.swap(arr, 0, i)arrLen - 1self.heapify(arr, 0)return arr 7.归并排序 【算法思想】 归并排序是利用归并的思想实现的排序方法该算法采用经典的分治策略分治法将问题分(divide)成一些小的问题然后递归求解而治(conquer)的阶段则将分的阶段得到的各答案修补在一起即分而治之)。 【代码实现】 import math
class Solution:def mergeSort(self,arr):if (len(arr) 2):return arrmiddle math.floor(len(arr) / 2)left, right arr[0:middle], arr[middle:]return self.merge(self.mergeSort(left), self.mergeSort(right))def merge(self,left, right):result []while left and right:if left[0] right[0]:result.append(left.pop(0));else:result.append(right.pop(0));while left:result.append(left.pop(0));while right:result.append(right.pop(0));return result 来自于wx公众号“光城”。 几种排序算法代码c版本 (暂无堆排和希尔排序) #include ../stdafx.h
#include stdio.h
#include stdlib.h
#include string
#include algorithm
#include vector
#include queue
#includefunctional
#include map
#include iostream
using namespace std;void BubbleSort(vectorint arr){if (arr.size() 0)return;for (int len arr.size() - 1; len 1; len--){for (int i 0; i len; i){if (arr[i]arr[i 1])swap(arr[i], arr[i 1]);}}
}void SelectionSort(vectorint arr){if (arr.size() 0)return;for (int i 0; i arr.size() - 1; i){int min_index i;for (int j i 1; j arr.size(); j){/*if (arr[j]arr[j-1]) //每次左边起始位置向前移一个但是并不能保证一轮下来左边的数为最小值swap(arr[j-1], arr[j]);*/min_index arr[min_index] arr[j] ? min_index : j;}swap(arr[min_index],arr[i]);}
}void InsertSort(vectorint arr){if (arr.size() 0)return;for (int i 1; i arr.size(); i){ //从索引1开始前面索引0区域为插入空间for (int j i - 1; j 0 arr[j]arr[j 1]; j--) //--逆序直接和插入空间最右(也即最大)的数比较就可知是否进行插入swap(arr[j], arr[j 1]); //不是i,j直接比较 j--决定插入的具体位置如1352}
}void QuickSort(vectorint arr,int L, int R){if (L R) //递归终止条件return;int pivot arr[L];int i L, j R;while (i ! j){//先从右边找否则会报错while (arr[j] pivoti j)j--;while (arr[i] pivoti j)i;if (i j){swap(arr[i],arr[j]);}}arr[L] arr[i];arr[i] pivot; //最终pivot位置为iQuickSort(arr, L, i - 1);QuickSort(arr, i 1,R);
}//归并先拆分为若干子数组通过merge()对其逐步合并排序
void Merge(vectorint arr, int L, int mid, int R){int i L, j mid 1;vectorint new_arr;while (i midj R){if (arr[i] arr[j])new_arr.push_back(arr[i]),i;elsenew_arr.push_back(arr[j]),j;}while (i mid)new_arr.push_back(arr[i]), i;while (j R)new_arr.push_back(arr[j]), j;for (int k L, t 0; k R; k, t) //把值复制回原arrarr[k] new_arr[t];
}void MergeSort(vectorint arr, int L, int R){if (L R)return;else{int mid (L R) / 2;MergeSort(arr, L, mid);MergeSort(arr, mid 1, R);Merge(arr, L, mid, R);}
}int main(void){vectorint array {2, 1, 3, 5, 2, 6, 9, 2, 7 };//BubbleSort(array);//SelectionSort(array);//InsertSort(array);//QuickSort(array, 0, array.size() - 1);MergeSort(array, 0, array.size() - 1);vectorint vec array;vector int::iterator it;for (it vec.begin(); it ! vec.end();it)cout *it endl;getchar();return 0;
} 基本算法复杂度 参考来源https://linux.cn/article-7480-1.html 转载于:https://www.cnblogs.com/nicetoseeyou/p/10512700.html
