蓝桥杯—排序

type

status

date

slug

summary

1.冒泡排序（Bubble sort）

1.1 算法思路

从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。

以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。

1.2 java算法实现

平均时间复杂度：O（n^2) 空间复杂度：O（1）

2.选择排序（Selection sort）

2.1 算法思路

第一次从待排序的中数据元素选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

2.2 算法实现

平均时间复杂度：O（n^2) 空间复杂度：O（1）选择排序是不稳定的排序方法。

3.插入排序（Insertion sort）

3.1 算法思路

对于少量元素的排序，插入排序是一个有效的算法。

1.从第一个元素开始，该元素可以认为已经被排序 2.取下一个元素tem，从已排序的元素序列从后往前扫描 3.如果该元素大于tem，则将该元素移到下一位 4.重复步骤3，直到找到已排序元素中小于等于tem的元素 5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置 6.重复步骤2~5

3.2 算法实现

平均时间复杂度：O（n^2) 空间复杂度：O（1）

4.归并排序（Merge sort）

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

4.1 算法思路

将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。

将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

4.2 算法实现

时间复杂度：O（nlogn）空间复杂度：O（n）速度仅此于快速排序

5.快速排序(Quick sort)

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

5.1 算法思路

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

5.2 算法实现

6.桶排序（Bucket sort）

又称箱排序，是一种比较常用的排序算法。其算法原理是将数组分到有限数量的桶里，再对每个桶分别排好序（可以是递归使用桶排序，也可以是使用其他排序算法将每个桶分别排好序），最后一次将每个桶中排好序的数输出。

6.1 算法思路

1、取序列中的最大值max和最小值min

取桶的范围 size=（max-min）/arr.length+1个桶

桶的个数是 count=(max=min)/size+1

2、扫描一遍数组，将各个数据放入对应的桶中。

第一个桶范围[min,min+size),第二个桶范围[min+size,min+size*2)……以此类推

3、每个桶中的元素分别做快速排序

4、遍历所有的桶，则完成了排序

6.2 算法实现

平均时间复杂度：O（n+k）空间复杂度：O（n+k）

7.堆排序（Heap sort）

堆排序是指利用堆这种数据结构所设计的一种排序算法

7.1 算法思路

1）将待排序序列构造成一个大顶堆

2)此时，整个序列的最大值就是堆顶的根节点。

3)将其与末尾元素进行交换，此时末尾就为最大值。

4)然后将剩余n-1 个元素重新构造成-一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

7.2 算法实现

8.基数排序（Radix sort）

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

2种排序方式：

最低位优先法(LSD)：从最低位向最高位依次按位进行排序。

最高位优先法(MSD)：从最高位向最低位依次按位进行排序。