<>一文搞掂十大经典排序算法

今天整理一下十大经典排序算法。

<>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; }

技术
今日推荐
阅读数 23
阅读数 17
阅读数 11
阅读数 11
阅读数 10
友情链接
码工具
Toolsou
API参考文档
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信