1,2,3あります.nの無秩序な配列、並べ替えのアルゴリズムを求めます
651 ワード
1,2,3,...nの無秩序配列があり,並べ替えアルゴリズムを求める.時間複雑度O(n),空間複雑度O(1)が要求される.交換を使用し、一度に2つの数しか交換できません.(2020回鼎信通信現場筆記試験問題)未ソートの配列は
arr1[] = {10,6,9,5,2,8,4,7,1,3}
、ソート後の配列はarr2[]={1,2,3,4,5,6,7,8,9,10}
である.arr1
とarr2
の対応関係を観察すると、arr1[i]
はarr2
の下にarr1[i]-1
と表記されている.arr1[i] = arr2[arr1[i]-1]
です.#include
using namespace std;
void Order(int *arr,int len)
{
int i = 0;
int temp = 0;
for(i=0;i