面接で身につけなければならない4つの古典的なソートアルゴリズム

良いソートアルゴリズムは、時間の複雑さと空間の複雑さの優位性を兼ね備えなければならない.これまでできるソートアルゴリズムの中で、時間の複雑さが最も低いのもn*log nである.そのため、ソートアルゴリズムを最適化するには、どの可能なアルゴリズムから最適化すべきかを知っておく必要がある.このブログでは、私はいくつかの最もよく見られる、面接問題に最も現れやすいソートアルゴリズムを羅列し、完全な比較をします.直接挿入アルゴリズム直接挿入アルゴリズムのアルゴリズム思想(1)デフォルト配列が整列している(2)要素を入れ続ける場合は、配列の最後の要素から比較する(3)挿入値xが最後の値より小さい場合は、それよりも小さい値に直面するまで前に進み、前の要素をすべて後ろに移動します.さらにxを挿入(4)xが最後の値より大きい場合は、最後のビットの後ろに直接置くコードは次の通りです.

void InsertSort(int *a,size_t n)
{
    int tag=3;
    int tmp;
    for(size_t i=0;i1;i++)
    {
      DataType end=i;
      tmp=a[end+1];

      while(end> 0 && a[end]>tmp)//    tmp
      {
          a[end+1]=a[end];//    
          end--;
      }
      a[end+1]=tmp;// tmp  
    }
}

2.ヒルソート(直接ソートを挿入する最適化アルゴリズム)の考え方:ヒルソートのコードと挿入ソートには大きな違いはありません.それらの間には小さな違いがあります.ヒルソートには複数の事前ソートが追加されています.この複数の事前ソートこそ、時間の複雑さを大幅に低下させます.もちろん、ここの時間の複雑さはあなたが選んだtagと関係があります.次に、ヒルソートの実現手順について(1)プリソートとは,全体挿入を行った上で,1つの配列に隣接するtag距離の要素を先に1回粗列(2)を1回粗列にした後,tagを1縮小することで,隣接するtag-1距離の要素ごとに1回挿入ソートを行い,また1ラウンドのプリソートを経た後,配列全体の要素が隣接して秩序に近づいている場合、tagが1に等しい場合、最後の挿入並べ替えが行われ、配列が完全に秩序化されているヒル並べ替えが直接挿入並べ替えの最適化は、配列が最悪の場合、挿入並べ替えアルゴリズムが各要素をn-1回移動させることで算出される.時間複雑度はn^2に達しヒルソートを用い,複数回の事前ソートを経て配列が秩序に近づいたため,挿入時に移動するデータ量も小さく,時間複雑度コードを大幅に低減できる.

void  ShellSort(int *a,size_t n)
{
    int tag=3; //      
    int tmp;
    while(tag>1)
    {
        tag=tag/3+1;  //tag   1
        for(size_t i=0;iend=i;
            tmp=a[end+tag]; 

            while(end>=0 &&a[end]>tmp)
            {
                a[end+tag]=a[end]; //      
                end-=tag;
            }
            a[end+tag]=tmp;

        }
    }

3.選択ソート選択ソートは安定性があり、これは一般的なソートには備わっていないが、選択ソートにはいくつかの欠点があり、時間の複雑度が高く、アルゴリズムの最適化が難しい.ソートを選択する考え(1)最大最小値を選択するたびに、下付き(2)を覚えてから、最初の要素と最後の要素をそれぞれ交換操作し、配列を比較する必要があるデータを2(3)減らして下付きを制御し、順番にループし、中間位置に行くと、配列も次のようにソートされます.

void SelectSort(int *a,int b)
{
    int i=0;
    int left=0;
    int right=9;
    int min=0;
    int max=0;

    while(leftmin=max=left;

        for(i=left;i<=right;++i)
        {
            if(a[i]min])
{
min=i;  //    をマークする  き
}
if(a[i]>a[max])
{
max=i;//    の  きをマーク
}
}
swap(&a[left],&a[min]);//minとmaxの  の  を  します
if(left!=max)
swap(&a[right],&a[max]);
++left;
--right; //アレイ  
}

4.クイックソート(左右ポインタ法再帰バージョン)クイックソートの左右ポインタ法は、実は2つの下付き文字を定義して配列のソートを制御し、1つの配列に10の要素があると仮定し、最後の要素の値をkeyに保存することを想定している.(2)1つのbeginと1つのendを設定し、beginを0に初期化し、endを9(3)に初期化して一番左からkeyより大きい値を探し、見つけたら現在の下付き文字(4)を一番右から一番後ろからkeyより小さい値を保存し、見つかったら現在の下付き文字を保存(5)両方の値が見つかったら交換(6)見つからなかったら、keyと右から探している最初の値を交換(7)するように1回のループ交換を経て、大きな値はkeyの後ろにあり、小さい値はkeyの前(8)で再帰的にkeyの左右の要素を2回グループ化し、それぞれにコードを並べて次のようにします.

int  QuickSort1(int a[],int left,int right)
{
    int key=a[right];
    int begin=left;
    int end=right;
    while(begin<end)
    {
        if(a[begin]<=key)
        {
            begin++;
            continue;
        }
        if(a[end]>=key)
        {
            end--;
            continue;
        }
        swap(&a[begin],&a[end]);
    }
    swap(&a[begin],&a[right]);
    return begin;
}

void QuickSort(int a[],int left,int right)
{
    assert(a);
    if(left>=right)
        return;
    int div=QuickSort1(a,left,right);
    QuickSort(a,left,div-1);
    QuickSort(a,div+1,right);

}