排序 专题讨论
一.问题阐述
前K大问题
从一组元素(n个)中找出前K大个元素
二.解决思路
1.先将n个元素按照从小到大进行排序。
2.然后将排序好的数组从后输出K个元素。
三.关键过程
如何将n个元素进行排序？
代码如下：
void Sort(int* arr, int n)
{
int i=0;
int position=-1;
while(i<n)
{
if(i==0||arr[i-1]<=arr[i])
{
if(position==-1)
{
i++;
}
else{
i=position+1;
position=-1;
}
}else{
if(position==-1)
{
position=i;
}
int tmp=arr[i];
arr[i]=arr[i-1];
arr[i-1]=tmp;
i--;
}
}
}四.分析
代码中的position是用来记录交换时，当前元素的下标。
当前面的元素整理完成，i 可以直接跳到 position+1，减少循环次数。
举例：
[5, 3, 2, 4]
cmp 5 3
change -> [3, 5, 2, 4]
position 为 1
jump 2 #这里jump的位置是position+1
cmp 5 2
change -> [3, 2, 5, 4]
cmp 3 2
change -> [2, 3, 5, 4]
jump 2
cmp 3 5
cmp 5 4
change -> [2, 3, 4, 5]
cmp 3 4
jump 4
运行代码截图：
最好循环执行次数为n，最坏为n(n+1)/2。
所以最好的时间复杂度为O(n)，最坏为O(n^2)。
五.拓展
这个问题和PTA 7-5 选做 寻找大富翁 考核的差不多
所以用这个排序进行测试。
六.结论
这个排序算法比较简单，比较稳定，容易理解，有点类似与插入排序，但是将一个数放入其正确位置的交换同冒泡排序(一系列交换)
简单，只有一层循环，最好的时间复杂度为O(n)，最坏为O(n^2)。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/114446.html原文链接：https://javaforall.net
