【每天一道算法题】时间复杂度为O(n)的排序-白红宇

【每天一道算法题】时间复杂度为O(n)的排序

阅读量：6496 次

发布时间：2019-06-24

本文共 997 字，大约阅读时间需要 3 分钟。

有1，2，……一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂度为O(1)，使用交换，而且一次只能交换两个数。

这个是以前看到的算法题，题目不难。但是要求比较多，排序算法中，时间复杂度为O(n)就是基数排序了。

现在介绍两种解法：

解法一：用数组特性——下标实现交换

扫描数组，每次arr[i],arr[arr[i]-1]交换，如果arr[i]=i+1，则什么都不做。这样交换一次保证一个数字被放到它应该被放置的位置上。最后数组有序。

#include 
     
      #include 
      
       using namespace std;void swap(int& a, int& b){    a^=b;    b^=a;    a^=b;}vector
       
        & Sort(vector
        
         & vec1){    if(vec1.size()==1)        return vec1;    for(int i=0;i

vec2(arr,arr+9); Sort(vec2); for(int i=0;i

上面的题目是每个数字只出现一次，如果不限制出现的次数，要求时间复杂度是O(n)，空间复杂度为O(1)又该怎么做，给出数字的最大范围假设为65536。

这个题用桶排序应该可以做。

解法二：利用count[65536]（和n无关，空间复杂度为O(1)）数组记录出现的次数

那么假设有下面这些数字：

100

200

300

119

...

那么对于每个这个数字，都做在count中记录一下：

100 => count[100]++

200 => count[200]++

300 => count[300]++

119 => count[119]++

0 => count[0]++

6 => count[6]++

最后，遍历一边所有这些数字就可得到0~65535每个数字的个数（在count数组中），然后再顺序遍历count数组，count[n] = m，则输出m个n，（比如说有count[3] = 2, 那么说明有2个数字3），依次输出，最后可得结果。

转载于:https://www.cnblogs.com/LUO77/p/5780187.html

你可能感兴趣的文章

[LeetCode] Longest Substring with At Most K Distinct Characters 最多有K个不同字符的最长子串...