第5章 第6节 排序

推荐给朋友

● 对一千万个整数排序,整数范围在[-1000,1000]间,用什么排序最快?

参考回答:

在以上的情景下最好使用计数排序,计数排序的基本思想为在排序前先统计这组数中其它数小于这个数的个数,其时间复杂度为,其中n为整数的个数,k为所有数的范围,此场景下的,所以计数排序要比其他基于的比较排序效果要好。

● 堆排序的思想

参考回答:

将待排序的序列构成一个大顶堆,这个时候整个序列的最大值就是堆顶的根节点,将它与末尾节点进行交换,然后末尾变成了最大值,然后剩余n-1个元素重新构成一个堆,这样得到这n个元素的次大值,反复进行以上操作便得到一个有序序列。

● 冒泡排序

参考回答:

def bubble_sort(lst):
count=len(lst)
for i in range(0,count):
for j in range(i,count):
if lst[i]>lst[j]:
lst[i],lst[j]=lst[j],lst[i]

● 快速排序的最优情况

参考回答:

快速排序的最优情况是Partition每次划分的都很均匀,当排序的元素为n个,则递归树的深度为。在第一次做Partition的时候需对所有元素扫描一遍,获得的枢纽元将所有元素一分为二,不断的划分下去直到排序结束,而在此情况下快速排序的最优时间复杂度为

● 抽了两道面试题目两道。8个球,1个比较重,天平,几步找到重的?

参考回答:

两次。分成3-3-2。

详情:数据结构与算法

● 算法题:topK给出3种解法

参考回答:

1)局部淘汰法 -- 借助“冒泡排序”获取TopK

思路:(1)可以避免对所有数据进行排序,只排序部分;(2)冒泡排序是每一轮排序都会获得一个最大值,则K轮排序即可获得TopK。

时间复杂度空间复杂度:(1)时间复杂度:排序一轮是O(N),则K次排序总时间复杂度为:O(KN)。(2)空间复杂度:O(K),用来存放获得的topK,也可以O(1)遍历原数组的最后K个元素即可。

2)局部淘汰法 -- 借助数据结构"堆"获取TopK

思路:(1)堆:分为大顶堆(堆顶元素大于其他所有元素)和小顶堆(堆顶其他元素小于所有其他元素)。(2)我们使用小顶堆来实现。(3)取出K个元素放在另外的数组中,对这K个元素进行建堆。(4)然后循环从K下标位置遍历数据,只要元素大于堆顶,我们就将堆顶赋值为该元素,然后重新调整为小顶堆。(5)循环完毕后,K个元素的堆数组就是我们所需要的TopK。

时间复杂度与空间复杂度:(1)时间复杂度:每次对K个元素进行建堆,时间复杂度为:O(KlogK),加上N-K次的循环,则总时间复杂度为O((K+(N-K))logK),即O(NlogK),其中K为想要获取的TopK的数量N为总数据量。(2)空间复杂度:O(K),只需要新建一个K大小的数组用来存储topK即可

3)分治法 -- 借助”快速排序“方法获取TopK

思路:(1)比如有10亿的数据,找处Top1000,我们先将10亿的数据分成1000份,每份100万条数据。(2)在每一份中找出对应的Top 1000,整合到一个数组中,得到100万条数据,这样过滤掉了999%%的数据。(3)使用快速排序对这100万条数据进行”一轮“排序,一轮排序之后指针的位置指向的数字假设为S,会将数组分为两部分,一部分大于S记作Si,一部分小于S记作Sj。(4)如果Si元素个数大于1000,我们对Si数组再进行一轮排序,再次将Si分成了Si和Sj。如果Si的元素小于1000,则我们需要在Sj中获取1000-count(Si)个元素的,也就是对Sj进行排序(5)如此递归下去即可获得TopK。

时间复杂度与空间复杂度:(1)时间复杂度:一份获取前TopK的时间复杂度:O((N/n)logK)。则所有份数为:O(NlogK),但是分治法我们会使用多核多机的资源,比如我们有S个线程同时处理。则时间复杂度为:O((N/S)logK)。之后进行快排序,一次的时间复杂度为:O(N),假设排序了M次之后得到结果,则时间复杂度为:O(MN)。所以 ,总时间复杂度大约为O(MN+(N/S)logK) 。(2)空间复杂度:需要每一份一个数组,则空间复杂度为O(N)。

● 快排

参考回答:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
#include <iostream>
using namespace std;
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;

int key = a[first];/*用字表的第一个记录作为枢轴*/

while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}

a[first] = a[last];/*将比第一个小的移到低端*/

while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];

/*将比第一个大的移到高端*/

}

a[first] = key;/*枢轴记录到位*/

Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
int main()
{
int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};

Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/

for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << "";
}
return 0;
}

● 快排

参考回答:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
#include <iostream>
using namespace std;
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;

int key = a[first];/*用字表的第一个记录作为枢轴*/

while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}

a[first] = a[last];/*将比第一个小的移到低端*/

while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];

/*将比第一个大的移到高端*/

}

a[first] = key;/*枢轴记录到位*/

Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
int main()
{
int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};

Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/

for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << "";
}
return 0;
}