仅通过交换元素来对列表进行排序

Question

对于以下问题，最佳解决方案是什么： 给定值列表（fe：0-14范围内的数字）如何通过仅使用交换操作对它们进行排序（fe：交换列表中的第0和第9个元素），您的目标是找到交换次数最少的解决方案。

预先感谢您

Answer 1

假设数值为0到n-1的大小为n的数组，这里是一个具有O（n）时间复杂度的算法，它应该是最小化交换的最优​​算法。每一次交换都会将至少一个值（有时是两者）放置在适当的位置。

// the values of A[] range from 0 to n-1 
void sort(int A[], int n) 
{ 
    for(int i = 0; i < n; i++) 
     while(A[i] != i) 
      swap(A[i], A[A[i]]); 
} 

对于更通用的解决方案且假设仅用于将原始数组排序互换进行计数，根据该阵列是生成索引的阵列到阵列进行排序，排序索引的阵列排序（使用任何排序算法），然后使用上述算法同时对原始数组和索引数组进行排序。使用C++来描述这一点，使用一个lambda比较这个例子：

void sort(int A[], int n) 
{ 
    // generate indices I[] 
    int *I = new int[n]; 
    for(int i = 0; i < n; i++) 
     I[i] = i; 
    // sort I according to A 
    std::sort(I, I+n, 
     [&A](int i, int j) 
      {return A[i] < A[j];}); 
    // sort A and I according to I using swaps 
    for(int i = 0; i < n; i++){ 
     while(I[i] != i){ 
      std::swap(I[i], I[I[i]]); 
      std::swap(A[i], A[A[i]]); // only this swap is counted 
     } 
    } 
    delete[] I; 
} 

对于没有拉姆达commpare相当于语言中，可以使用自定义排序功能。排序是在O（n）时间复杂度的情况下撤销阵列中的“周期”。数组的每一个排列都可以被认为是一系列循环。值实际上是该元素的顺序，但在这种情况下，排序和值是相同的：

index 0 1 2 3 4 5 6 7 
value 6 3 1 2 4 0 7 5 

的周期是“路径”跟随值的链，开始索引为0，其具有值为6，然后转到具有值7的索引6并重复该过程，直到循环完成回到索引0.重复该数组的其余部分。对于此示例，该循环是：

0->6 6->7 7->5 5->0 
1->3 3->2 2->1 
4->4 

掉期上面所示的算法以下是：

swap(a[0],a[6]) // puts 6 into place 
swap(a[0],a[7]) // puts 7 into place 
swap(a[0],a[5]) // puts 0 and 5 into place 
swap(a[1],a[3]) // puts 3 into place 
swap(a[1],a[2]) // puts 1 and 2 into place 
       // done 

链接到根据它们中的一个排序多个阵列的更实用示例。

Sorting two arrays based on one with standard library (copy steps avoided)

Answer 2

您正在搜索的是一种排序算法。

https://brilliant.org/wiki/sorting-algorithms/

一个很好的一个是“快速排序”中包含“冒泡”

泰德 - 爱德也有关于这一主题的好的视频一个简单的排序算法相结合： https://www.youtube.com/watch?v=WaNLJf8xzC4

Answer 3

大概找到这个问题答案的最好方法是打开你最喜欢的搜索引擎，并把标题放在你的问题。你会发现许多成果，包括：

• Sorting algorithm - Wikipedia（包括上Popular sorting algorithms一节）
• 10.4. Sorting Algorithms - Introductory Programming in C#

通读这些和发现，只有使用元素的交换做算法排序（因为这是你的要求）。您还可以阅读有关算法的性能（因为这是需求的另一部分）。

请注意，根据数组的大小和排序方式，有些执行速度会比其他快。

---

另一种解决问题的方法是问问自己：“专业人员做什么？”。这可能会导致您阅读Array.Sort Method的文档，这是我们大多数人使用的内置机制，如果我们需要快速对数组进行排序。在这里，你会发现如下信息：

备注

此方法使用内省排序（内省排序）算法如下：

• 如果分区大小是少于16个元素，它使用insertion sort算法。
• 如果分区数量超过2 * LogN，其中N是输入数组的范围，则使用Heapsort algorithm。
• 否则，它使用Quicksort algorithm。

所以现在我们看到的是，对于小分区（如具有15种元素的例子），在专业人员使用insertion sort。