# Cyclic Sort

題目

解法

#include <iostream>
#include <vector>

using namespace std;

class CyclicSort {
 public:
  static void sort(vector<int> &nums) {
    int i = 0;
    while(i < nums.size() - 1) {
      int j = nums[i] - 1; // j is the correct index of nums[i]

      // nums[i] should appear at index j
      // if not, put nums[i] to index j
      if(nums[i] != nums[j]) {
        swap(nums[i], nums[j]);
      }
      else {
        ++i;
      }  
    }  
  }
};

這個時間複雜度可以這樣想，雖然每次 swap 完，i 不會增加，但因為我們最多也只需要 swap n-1 次，就可以將整個 array 排好，所以經過 O(n-1) 的 swap 後，只需要 O(n) 時間走完 while，所以時間複雜度就是 O(n) + O(n-1)。