©2020-2024 ioDraw All rights reserved
<>一文搞掂十大经典排序算法
今天整理一下十大经典排序算法。
<>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 arr def partition(arr, left, right): pivot = left index = pivot+1 i =
indexwhile i <= right: if arr[i] < arr[pivot]: swap(arr, i, index) index+=1 i+=1
swap(arr,pivot,index-1) return index-1 def 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 = right if 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 = 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 = 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、基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
<>算法演示
<>算法步骤
* 取得数组中的最大数，并取得位数；
* 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 = null; if(counter[j]!=
null) { while ((value = counter[j].shift()) != null) { arr[pos++] = value; } } }
} return arr; }