前半と後半の両方が独立してソートされている整数のリンクリストがあります。次に、2つの部分をマージして、1つの単一のソートされたリンクリストを作成する必要があります。
サンプル入力：
入力リスト1：1->2->3->4->5->1->2
出力： 1->1->2->2->3->4->5
入力リスト2：1->5->7->9->11->2->4->6
出力2：1->2->4->5->6->7->9->11
期待される出力：
1,2,3....。
5 に答える
2
これがマージソートです。
私は2つの指針を維持します：
ptr1前半の最初の要素を指す
ptr2後半の最初の要素を指します。
最終的なリストを格納するために追加の配列が必要になります。もちろん、この追加の配列を使用しないことを選択することもできますが、その議論はトピックから遠く離れています。
1, を比較*ptr1し*ptr2、*ptr1の値が より小さい場合*ptr2、その値 (つまり*ptr1) を最後の配列にコピーし、ptr1先に進めます。
ptr2の値が小さい場合は、コピーし*ptr2てptr2先に進めます
2、ポインターが最後の要素の後ろを指しているときに停止します。たとえば、前半に5つの要素があるa[0] a[1] a[2] a[3] a[4]場合、ポインターが次の要素を指しているときに停止する必要があります
a[5]
3,前半が空なら後半をコピー、逆も同様。
于 2012-11-07T07:55:30.877 に答える
0
私は関数型言語を使用する際に数え切れないほどの時間を費やしてきたので、簡単に説明できると思います。
再帰的なプロセスと考えた方がアイデアが理解しやすいのですが、ここでは必須のプロセスについて説明します。部分リストと空のソート済みリストの両方から始めます。
次に、ループを開始すると、部分リストは次のように表示されます。
- どちらも空です。この場合、処理は完了しています。
- それらの1つが空で、もう1つをソート済みリストに追加します。
- いくつかの head 要素とリストの末尾。両方の head を比較し、最小のものをソート済みリストに追加し、もう一方を元の場所に残してから、残りのリストでループします。
ループから抜けたら、ソートされたリストを返すだけです。
ただし、注意点が 1 つあります。単純なリンク リストを使用している場合は、並べ替えられたリストの前に要素を追加し、最後に元に戻してから返すことで、実行時間を短縮できます。
于 2012-11-07T08:06:25.130 に答える
0
これはマージソートと呼ばれます。
実装の詳細については、こちらとこちらをご覧ください。
于 2012-11-07T07:47:39.527 に答える
0
最適なソリューションの自然マージ ソートを探します: http://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort
于 2012-11-07T07:48:30.187 に答える