クラシック並べ替えのまとめ

34441 ワード

データ構造

泡の並べ替え(安定)は2つの隣接元素を順次比較し、大きなものを後ろに変えて、1回の循環が完了した後の結果は、最大の数字が最後になります.上記のステップ(最後の一つを除いて)を繰り返します.

平均時間複雑度:O(n^2)

最適時間複雑度:O(n)

void bubble_sort(vector<int>&nums)
{
	int len=nums.size();
	for(int i=0;i<len;i++)
	{
		for(int j=0;j<len-i-1;j++)
		{
			if(nums[j]>nums[j+1])swap(nums[j],nums[j+1]);
		}
	}
}

並べ替えを選択

簡単に並べ替え(不安定)を選択して、シーケンスの中で一番小さいのを選んで、彼女を最初の位置に挿して、順次類推します.

n個の数を比較する必要がある回数はn(n-1)/2

です.

時間の複雑さはO(n^2)

です.

による移動動作の複雑さはO(n)

である.

void select_sort(vector<int>&nums)
{
	int len=nums.size();
	for(int i=0;i<len;i++)
	{
		int temp=i;
		for(int j=i;j<len;j++)
		{
		if(nums[temp]>nums[j])temp=j;
		}
		swap(nums[i],nums[temp]);
	}
}

ヒープ並べ替え

並べ替えの挿入

は、順序付け(安定性)を直接挿入し、順序付けされた記録をそのキーコード値の大きさに従って、順序付けされた順序付けられた順序付けシーケンスに1つずつ挿入し、すべての記録が挿入されるまで.

平均時間複雑度O(n^2)

空間複雑度O(1)

void insert_sort(vector<int>&nums)
{
	int len=nusms.size();
	for(int i=1;i<len;i++)
	{
		int temp=nums[i];
		int j=i;
		while(j>=1&&temp<nums[j-1])
		{
			nums[j]=nums[j-1];
			j--;
		}
		nums[j]=temp;
	}
}

折半挿入順序の直接挿入順序は、挿入要素と既存の順序要素を一度に比較すると、効率が非常に低いです.半角挿入は、半角検索を使用して挿入点の位置を探します.このように比較の回数を減らすことができますが、移動の回数は不変です.時間の複雑さと空間の複雑さは、直接挿入順序と同じです.要素が多いです.状況下で検索性能を向上させることができます.

void insert_sort(vector<int>&nums)
{
	int len=nums.size（）；
	for(int i=1;i<len;i++)
	{
		int temp=nums[i];
		int pre=0;
		int end=i-1;
		int mid;
		while(pre<=end)
		{
			mid=(pre+end)/2;
			if(nums[mid]>temp)end=mid-1;
			else if(nums[mid]<=temp)pre=mid+1;
		}
		for(int j=i;j>=pre+1;j--)
            nums[j]=nums[j-1];
            nums[pre]=temp;
	}
}

迅速なソート方法

public static int partition(int[] array, int lo,int hi){
	int key=array[lo];
	int i=lo;
	int j=hi;
	while(i<j){
		while(array[j]>=key&&i<j)j--;
		while(array[i]<=key&&i<j)i++;
		swap(array,i,j);
}
	swap(array,lo,j);
	return j;
}

swap()関数を利用して、keyより前に書いて、keyより後ろに書いてください.そうすれば、最初のwhileサイクルをオフにすると、現在のjは必ずkey値より小さい数を指します.そうすると、最後にkey値と交換することができます.
ヒルの順序付けは、増分の順序を縮小し、すべての数を一定の増分パケットに従って順序付けを挿入し、増分を減少させて、上記の動作をインクリメントが1で終わるまで繰り返す.

挿入順序は、ほぼ並べ替えられたデータに対して動作する場合、効率が高く、すなわち線形順序付けの効率に達することができる.

ですが、挿入順序は一般的に非効率です.挿入順序は毎回データを1つだけ移動することができます.

void ShellSort(int array[])
{
	int i,j;
	int temp;//       
for(int step=length/2;step>0;step/=2)//step   ，             
{
	for（i=step;i<LENGTH;i++）
	{
		temp=array[i];//         ，           
		for(j=i-step;(j>=0&&array[j]>temp);j-=step)//          《0       （  ，  ）
		{
			array[j+step]=array[j];
		}
		array[j+step]=temp;//               
	}
}
}

規格化された順序付けは、規格化された動作において作成された効率的な順序付けアルゴリズムであり、このアルゴリズムは、ディヴィッド・アンド・Coquerを用いた非常に典型的なアプリケーションであり、各階層による再帰処理は同時に行われることができる.
実現原理:
①統合後のシーケンスを保存するためのスペースは、順序付けされた2つの合計の大きさにするための空間です.
②2つのポインタを設定し、最初の位置はそれぞれ2つの並べ替え済みシーケンスの開始位置となります.
③2つのポインタが指す要素を比較し、比較的小さい要素を結合空間に入れて、次の位置にポインタを移動します.
④手順③を繰り返し、あるポインタがシーケンスの最後に到達するまで
⑤他のシーケンスの残りの要素をそのまま連結シーケンスの最後にコピーします.

void merge_sort(vector<int>&nums)
    {
        int len=nums.size();
        int result[len];
        int i;
        for(int blocks=1;blocks<len;blocks*=2)
        {
            i=0;
        for(int start=0;start<len;start+=2*blocks)
        {
            int start1=start;
            int end1=(start+blocks)>len?len:start+blocks;
            int start2=end1;
            int end2=(start2+blocks)>len?len:start2+blocks;
            while(start1<end1&&start2<end2)
            {
                if(nums[start1]<nums[start2])
                {
                    result[i++]=nums[start1];
                    start1++;
                }
                 else if(nums[start1]>=nums[start2])
                {
                    result[i++]=nums[start2];
                    start2++;
                }
            }
            while(start1<end1)
            {
                result[i++]=nums[start1++];
            }
            while(start2<end2)
            {
                result[i++]=nums[start2++];
            }
            
                
        }
            for(int i=0;i<len;i++)
            nums[i]=result[i];
        }
           
        
    }

2.再帰的に実現する
シーケンスがn要素であると仮定します.
①シーケンスを隣の2つの数字ごとにまとめて動作し、flor(n/2)のシーケンスを形成し、並べ替え後の各シーケンスには2つの要素が含まれています.
②上記のシーケンスをもう一度まとめてflor(n/4)のシーケンスを形成し、各シーケンスには4つの要素が含まれています.
③手順②を繰り返し、すべての要素がコードを並べ替えるまで:

void merge_sort(vector<int>&nums,int*result,int start,int end)
    {
        if(start>=end)return;
        int len=end-start;
        int start1=start;
        int end1=start+len/2;
        int start2=end1+1;;
        int end2=end;
        merge_sort(nums,result,start1,end1);
        merge_sort(nums,result,start2,end2);
        int i=start;
        while(start1<end1+1&&start2<end2+1)
            {
                if(nums[start1]<=nums[start2])
                {
                    result[i++]=nums[start1];
                    start1++;
                }
                 else if(nums[start1]>nums[start2])
                {
                    result[i++]=nums[start2];
                    start2++;
                }
            }
            while(start1<end1+1)
            {
                result[i++]=nums[start1++];
            }
            while(start2<end2+1)
            {
                result[i++]=nums[start2++];
            }
            for(int i=start;i<=end;i++)
            nums[i]=result[i];
            
        
    }

参考文献:1https://blog.csdn.net/marcosyw/article/details/72794216 2https://blog.csdn.net/hlang8160/article/details/78940780 3https://www.cnblogs.com/bulingpan/p/6416351.html

c言語循環チェーンの実現