0.导语
本节为手撕代码系列之第一弹,主要来手撕排序算法,主要包括以下几大排序算法:
-
直接插入排序
-
冒泡排序
-
选择排序
-
快速排序
-
希尔排序
-
堆排序
-
归并排序
1.直接插入排序
【算法思想】
每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。
【代码实现】
# 直接插入排序 def insert_sort(arr): length = len(arr) for i in range(length): k = i for 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 = True for j in range(length-i-1): if arr[j]>arr[j+1]: t = arr[j] arr[j]=arr[j+1] arr[j+1]=t flag = False if 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 = i for j in range(i+1,length): if arr[min]>arr[j]: min=j if 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 array else: pivot=array[0] small=[i for i in array[1:] if i<=pivot] big=[i for i in array[1:] if i >pivot] return self.quicksort(small)+[pivot]+self.quicksort(big) //递归法,耗时
方法二(双指针前后移动):
def quickSort(arr,left,right): # 递归终止条件 if left>right: return pivot = arr[left] i = left j = right while i<j: while i<j and arr[j]>=pivot: j-=1 while i<j and arr[i]<=pivot: i+=1 if i<j: t = arr[i] arr[i] = arr[j] arr[j] = t # 放入枢椎 arr[left] = arr[i] arr[i]=pivot # 递归调用左区域 quickSort(arr,left,i-1) # 递归调用右区域 quickSort(arr,i+1,right) arr = [6,-2,0,9] quickSort(arr,0,len(arr)-1) print(arr)
5.希尔排序
【算法思想】
该算法也被称为:缩小增量排序。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
【代码实现】
# 希尔排序 def shellSort(arr): length = len(arr) # 设置初始增量 gap = length//2 while gap>0: # 从第gap个元素,逐个对其所在组进行直接插入排序 for i in range(gap,length): j = i while j-gap>=0 and arr[j]<arr[j-gap]: t = arr[j] arr[j] = arr[j-gap] arr[j-gap] = t j-=gap gap//=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,j+1) # 交换最后一个叶子节点与堆顶元素 temp = nums[j] nums[j] = firstNum nums[0] = temp return nums # 调整堆(最大堆),每次返回最大堆顶元素 def adjustHeap(self,nums,length): # 最后一个非叶节点 i = length//2 -1 # 从最后一个非叶节点开始调整,构成最大堆 while i>=0: temp = nums[i] k = 2*i+1 while k<length: if k+1<length and nums[k]<nums[k+1]: k+=1 if nums[k]>temp: nums[i]=nums[k] i=k else: break k=2*k+1 nums[i] = temp i-=1 return nums[0] s = HeapSort() nums = [8,9,7,10] t = s.heapSort(nums) print(t)
方法2:
def buildMaxHeap(self,arr): import math for i in range(math.floor(len(arr) / 2), -1, -1): self.heapify(arr, i) def heapify(self, arr, i): left = 2 * i + 1 right = 2 * i + 2 largest = i if left < arrLen and arr[left] > arr[largest]: largest = left if right < arrLen and arr[right] > arr[largest]: largest = right if 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 arrLen arrLen = len(arr) self.buildMaxHeap(arr) for i in range(len(arr) - 1, 0, -1): self.swap(arr, 0, i) arrLen -= 1 self.heapify(arr, 0) return arr
7.归并排序
【算法思想】
归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
【代码实现】
import math class Solution: def mergeSort(self,arr): if (len(arr) < 2): return arr middle = 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> #include<functional> #include <map> #include <iostream> using namespace std; void BubbleSort(vector<int> &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(vector<int> &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(vector<int> &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--决定插入的具体位置,如(1,3,5)2 } } void QuickSort(vector<int> &arr,int L, int R){ if (L >= R) //递归终止条件 return; int pivot = arr[L]; int i = L, j = R; while (i != j){ //先从右边找,否则会报错 while (arr[j] > pivot&&i < j) j--; while (arr[i] <= pivot&&i < j) i++; if (i < j){ swap(arr[i],arr[j]); } } arr[L] = arr[i]; arr[i] = pivot; //最终pivot位置为i QuickSort(arr, L, i - 1); QuickSort(arr, i + 1,R); } //归并:先拆分为若干子数组,通过merge()对其逐步合并排序 void Merge(vector<int> &arr, int L, int mid, int R){ int i = L, j = mid + 1; vector<int> new_arr; while (i <= mid&&j <= R){ if (arr[i] <= arr[j]) new_arr.push_back(arr[i]),i++; else new_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++) //把值复制回原arr arr[k] = new_arr[t]; } void MergeSort(vector<int> &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){ vector<int> 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); vector<int> 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