循环排序
入门理解"最少写入"的排序策略，适合理解循环分解。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void cycleSort(int arr[], int n) {
2 for (int cycle = 0; cycle < n - 1; cycle++) {
3 int item = arr[cycle];
4 int pos = cycle;
5 for (int i = cycle + 1; i < n; i++)
6 if (arr[i] < item) pos++;
7 if (pos == cycle) continue;
8 while (item == arr[pos]) pos++;
9 swap(arr[pos], item);
10 while (pos != cycle) {
11 pos = cycle;
12 for (int i = cycle + 1; i < n; i++)
13 if (arr[i] < item) pos++;
14 while (item == arr[pos]) pos++;
15 swap(arr[pos], item);
16 }
17 }
18}
复杂度分析
时间 O(n²)
空间 O(1)
最优 O(n)
最坏 O(n²)
算法讲解
循环排序将数组分解为若干个循环，每个循环内的元素通过交换到达正确位置。
它的核心思想是：对于每个位置，计算它应该放哪个元素，然后循环交换。
写入次数为 O(n)，是理论上写入次数最少的排序算法。
适合闪存等写入代价高的存储介质。