データ構造: 二分探索、クイックソートのアイデアと実装

最近、私はどのようにデザインするか、どのようにより良いコードを書くか、オブジェクト指向の考え方をより完全に理解するかについて考えており、この側面についても意図的に勉強しています。私も数年間コードを書いてきてまとめてみて、一番大切なのは考えることだと気づきました。 『プログラミング実践』という本を見直し、自分が書いたコードのスタイル、品質、パフォーマンス、移植性などをさらに標準化して反映しました。データ構造の知識とアルゴリズムはさらに統合されます。筆記試験でよく出題される二分探索アルゴリズムとクイックソートアルゴリズムについて書いてみましょう。アルゴリズムを実装する鍵は、実装のアイデアにあります。

(1) 二分探索
二分探索は実際には半探索であり、より効率的な探索方法です。必要な配列を検索します。
主なアイデアは次のとおりです: (検索された配列の周期が array[low, high] であるとします)
(1) 周期の中間位置 K を決定します
(2) 検索された値 T を array[k] と比較します。それらが等しい場合、検索は成功し、この位置に戻ります。そうでない場合は、新しい検索領域を決定して二分探索を続行します。領域は次のように決定されます。
a.array[k]>T 配列の順序性から、array[k,k+1,...,high]>T; であることがわかります。間隔は array[low,..., K-1]
b.array[k] /// 検索する番号

/// ターゲット番号index＆lt;/returns>

while（low＆lt; = low = mid + 1;配列の要素を基本値として使用します。

他の要素を 2 つのグループに分けます。
「小さい」は、基本値より小さい要素です。
「大きい」とは、基本値より大きい要素です。
これら 2 つのグループを再帰的に並べ替えます。
クイック ソートが高速である理由は、要素がベースライン値より小さいことが判明すると、それらのより大きな要素と比較する必要がなくなるからです。このプロパティにより、大きな要素を小さな要素と比較する必要がなく、単純な並べ替えやバブル 並べ替えよりもはるかに高速に並べ替えることができます。

時間间复杂度：O（nlogn）
代码实现：
///

/// 快速排序
///

///
///
public void QuickSort(int[ ] array,int left,int right)
{
int last;
if (left>=right)
return;
int rand = (left+right)/2;
Swap(array, left, rand);
最後= left;
for (int i = left + 1; i <= right; i++)
{
if (array[i] < array[left])
Swap(array, ++last, i );
}
Swap(array, left, last);
QuickSort(array, left, last - 1);
QuickSort(array, last + 1, right);
}

<概要>
///交换两个值
///
///
/// ///
private void Swap(int[] a,int i,int j)
{
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}

更多文章结构之二分法查找、快速排序思想与实関連記事请关注PHP中文网！

">