排序 专题讨论

一.问题阐述

前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)。