030-数据结构与算法|一文搞掂十大经典排序算法数据结构|排序算法|插入排序

一文搞掂十大经典排序算法今天整理一下十大经典排序算法。
1、冒泡排序 ——越小的元素会经由交换慢慢“浮”到数列的顶端
算法演示

文章图片

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。

算法实现

def bubbleSort(arr): for i in range(1, len(arr)): for j in range(0, len(arr)-i): if arr[j] > arr[j+1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr

2、选择排序 —— 最小的出来排第一，第二小的出来排第二…
算法演示

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

算法实现

def selectionSort(arr): for i in range(len(arr) - 1): # 记录最小数的索引 minIndex = i for j in range(i + 1, len(arr)): if arr[j] < arr[minIndex]: minIndex = j # i 不是最小数时，将 i 和最小数进行交换 if i != minIndex: arr[i], arr[minIndex] = arr[minIndex], arr[i] return arr

3、简单插入排序 ——通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法演示

文章图片

算法步骤

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

算法实现

def insertionSort(arr): for i in range(len(arr)): preIndex = i-1 current = arr[i] while preIndex >= 0 and arr[preIndex] > current: arr[preIndex+1] = arr[preIndex] preIndex-=1 arr[preIndex+1] = current return arr

4、希尔排序 ——希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。
算法演示

文章图片

算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法实现

def shellSort(arr): import math gap=1 while(gap < len(arr)/3): gap = gap*3+1 while gap > 0: for i in range(gap,len(arr)): temp = arr[i] j = i-gap while j >=0 and arr[j] > temp: arr[j+gap]=arr[j] j-=gap arr[j+gap] = temp gap = math.floor(gap/3) return arr

5、归并排序 ——建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法演示

算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

算法实现

def mergeSort(arr): import math if(len(arr)<2): return arr middle = math.floor(len(arr)/2) left, right = arr[0:middle], arr[middle:] return merge(mergeSort(left), mergeSort(right))def merge(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

6、快速排序 ——快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
算法演示

算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

算法实现

def quickSort(arr, left=None, right=None): left = 0 if not isinstance(left,(int, float)) else left right = len(arr)-1 if not isinstance(right,(int, float)) else right if left < right: partitionIndex = partition(arr, left, right) quickSort(arr, left, partitionIndex-1) quickSort(arr, partitionIndex+1, right) return arrdef partition(arr, left, right): pivot = left index = pivot+1 i = index whilei <= right: if arr[i] < arr[pivot]: swap(arr, i, index) index+=1 i+=1 swap(arr,pivot,index-1) return index-1def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i]

7、堆排序 ——利用堆这种数据结构所设计的一种排序算法
算法演示

算法步骤

创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

算法实现

def buildMaxHeap(arr): import math for i in range(math.floor(len(arr)/2),-1,-1): heapify(arr,i)def heapify(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 = rightif largest != i: swap(arr, i, largest) heapify(arr, largest)def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i]def heapSort(arr): global arrLen arrLen = len(arr) buildMaxHeap(arr) for i in range(len(arr)-1,0,-1): swap(arr,0,i) arrLen -=1 heapify(arr, 0) return arr

8、计数排序 ——作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法演示

算法步骤

找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

算法实现

def countingSort(arr, maxValue): bucketLen = maxValue+1 bucket = [0]*bucketLen sortedIndex =0 arrLen = len(arr) for i in range(arrLen): if not bucket[arr[i]]: bucket[arr[i]]=0 bucket[arr[i]]+=1 for j in range(bucketLen): while bucket[j]>0: arr[sortedIndex] = j sortedIndex+=1 bucket[j]-=1 return arr

9、桶排序 ——桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
算法演示
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9ybEGKPU-1633970885002)(C:\Users\LANWEI~1\AppData\Local\Temp\1633970398356.png)]

文章图片

算法步骤

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。

算法实现

function bucketSort(arr, bucketSize) {if (arr.length === 0) {return arr; } var i; var minValue = https://www.it610.com/article/arr[0]; var maxValue = arr[0]; for (i = 1; i < arr.length; i++) {if (arr[i] < minValue) {minValue = arr[i]; // 输入数据的最小值 } else if (arr[i]> maxValue) {maxValue = https://www.it610.com/article/arr[i]; // 输入数据的最大值 } } // 桶的初始化 var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5 bucketSize = bucketSize || DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var buckets = new Array(bucketCount); for (i = 0; i < buckets.length; i++) {buckets[i] = []; } // 利用映射函数将数据分配到各个桶中 for (i = 0; i < arr.length; i++) {buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]); } arr.length = 0; for (i = 0; i < buckets.length; i++) {insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序 for (var j = 0; j < buckets[i].length; j++) {arr.push(buckets[i][j]); } } return arr; }

10、基数排序基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
算法演示
【030-数据结构与算法|一文搞掂十大经典排序算法】

文章图片

算法步骤

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；

算法实现

var counter = []; function radixSort(arr, maxDigit) {var mod = 10; var dev = 1; for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {for(var j = 0; j < arr.length; j++) {var bucket = parseInt((arr[j] % mod) / dev); if(counter[bucket]==null) {counter[bucket] = []; } counter[bucket].push(arr[j]); } var pos = 0; for(var j = 0; j < counter.length; j++) {var value = https://www.it610.com/article/null; if(counter[j]!=null) {while ((value = counter[j].shift()) != null) {arr[pos++] = value; } } } } return arr; }