题目描述:
对一个数组按给定的下标排序,仅使用两两交换的方式,要求不能对数组进行扩容尽可能使用额外少的空间。
例如:原数组为:A,B,C,D,E,现给定新的位置为:3,1,4,2,那么排序后为D,A,C。
问题分析:
为什么分类为数据结构,因为其实这个题就是快排的挖坑法的变形。如果你还不清楚什么是快排的挖坑法:参见这里。
解决思路:
保存第一个位置的数据后,把第一个位置设为坑,如果给定的新位置与现在i所在位置不相等,说明数据不在我们期待的位置,则把下标为新位置的数据放到i的位置。
代码实现:
#include<iostream> using namespace std; void SwapSort(int*pArr,int*pPos,size_t n) { size_t i = 0; int tmp = 0; tmp = pArr[i]; //第一个坑 while (--n) //总共交换n-1次 { if (i != pPos[i]) { pArr[i] = pArr[pPos[i]]; i = pPos[i]; } } pArr[i] = tmp; //把最开始坑里的数据填到最后一个坑的位置 } int main() { int arr[] = { 'A','B','C','D','E' }; int pos[] = { 3,2 }; SwapSort(arr,pos,sizeof(arr)/sizeof(arr[0])); for (size_t i = 0; i < 5; i++) { cout << (char)arr[i] << " "; } cout << endl; getchar(); return 0; }