1.4 Sorting

Sorting排序算法

complexity

稳定**:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。

coding

#Bubble Sort

性质:1、时间复杂度:O(n2) 2、空间复杂度:O(1) 3、稳定排序 4、原地排序

优化一下冒泡排序的算法

改进思路1:设置标志位,明显如果有一趟没有发生交换(flag = false),说明排序已经完成 改进思路2:记录一轮下来标记的最后位置,下次从头部遍历到这个位置就Ok

#Selection Sort

性质:1、时间复杂度:O(n2) 2、空间复杂度:O(1) 3、非稳定排序 4、原地排序

#Insertion Sort

性质:1、时间复杂度:O(n2) 2、空间复杂度:O(1) 3、稳定排序 4、原地排序

#Shell Sort

性质:1、时间复杂度:O(n^1.5) 2、空间复杂度:O(1) 3、非稳定排序 4、原地排序

#Merge Sort

1、时间复杂度:O(nlogn) 2、空间复杂度:O(n) 3、稳定排序 4、非原地排序

#quick sort

性质:1、时间复杂度:O(nlogn) 2、空间复杂度:O(1) 3、非稳定排序 4、原地排序

#Heap Sort

性质:1、时间复杂度:O(nlogn) 2、空间复杂度:O(1) 3、非稳定排序 4、原地排序

#Counting Sort

只能排自然数

性质:1、时间复杂度:O(k) 2、空间复杂度:O(k) 3、稳定排序 4、非原地排序

k=桶大小

优化一下: 创建的临时数组大小 (max - min + 1)就可以了,然后在把 min作为偏移量。

#Bucket Sort

桶排序就是把最大值和最小值之间的数进行瓜分,例如分成 10 个区间,10个区间对应10个桶,我们把各元素放到对应区间的桶中去,再对每个桶中的数进行排序,可以采用归并排序,也可以采用快速排序之类的。

之后每个桶里面的数据就是有序的了,我们在进行合并汇总。

性质:1、时间复杂度:O(n+k) 2、空间复杂度:O(k) 3、稳定排序 4、非原地排序

注:k 表示桶的个数,下同

#Radix Sort

基数排序的排序思路是这样的:先以个位数的大小来对数据进行排序,接着以十位数的大小来多数进行排序,接着以百位数的大小……

排到最后,就是一组有序的元素了。不过,他在以某位数进行排序的时候,是用“桶”来排序的。

由于某位数(个位/十位….,不是一整个数)的大小范围为0-9,所以我们需要10个桶,然后把具有相同数值的数放进同一个桶里,之后再把桶里的数按照0号桶到9号桶的顺序取出来,这样一趟下来,按照某位数的排序就完成了

1、时间复杂度:O(kn) 2、空间复杂度:O(n+k) 3、稳定排序 4、非原地排序

Sort the Matrix Diagonally

https://leetcode.com/problems/sort-the-matrix-diagonally/arrow-up-right

Sort matrix

Throttling Gateway

any given second cannot exceed 3 any given 10 second period cannot exceed 20 any given minute cannot exceed 60Throttling Gateway

droppedRequests

Last updated