面接シリーズのソートアルゴリズムまとめ(C/C++バージョン)

バブルソート

/*
               ，
                     
*/

#include 

void Exchange(int &a,int &b)
{
    //      ，        
    a = a^b;
    b = a^b;
    a = a^b;
}

void BubbleSort(int a[],int len)
{
    //           ，          
    if(a == NULL || len <= 0)
        return;
    //         
    for(int i = 0; i < len; i++)
    {
        for(int j = len-1; j > i; j--)
        {
            if(a[j] < a[j-1])
                exchange(a[j],a[j-1]);
        }
    }
}

時間複雑度O(n²),空間複雑度O(1)
ソートの選択

/* 
       
     n-i    ，      i           i    
*/ 
void SelectSort(int a[],int len)
{
    //           ，          
    if(a == NULL || len <= 0)
        return;
    //         
    for(int i = 0; i < len; i++)
    {
        int min_index = i;
        for(int j = i+1; j < len; j++)
        {
            //     ，     i        
            if(a[i] > a[j])
                min_index = j;
        }
        if(min_index != i)
            exchange(a[i],a[min_index]);
    }
}

時間複雑度O(n²),空間複雑度O(1)
ソートの挿入

/*
        
    a[0...i]  ，
      a[i+1]    a[0...i]     ，
     a[0...i+1]  
*/
void InsertSort(int a[], int len)
{
    for(int i = 1; i < len; i++)
    {
        int j = i-1;
        int key = a[i];
        while(j >=0 && a[j] > key)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}

時間複雑度O(n²),空間複雑度O(1)
クイックソート

/*
                 ：
          ，          O(nlogn),  O(nlogn)         
             
*/
int Partition(int a[], int p, int r)
{
	int i = p;
	for(int j = p; j < r; j++)
	{
		if(a[j] < a[r])
		{
			exchange(a[i],a[j]);
			i++;
		}
	}
	exchange(a[i],a[r]); 
	return i;
}

void QuickSort(int a[],int p,int r)
{
	if(p < r)
	{
		int q = Partition(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}
}

高速ソートの最悪の時間複雑度はO(n^2)であるが,平均時間複雑度はO(nlogn)である.
平均空間複雑度はO(nlogn),最悪空間複雑度はO(n)である.
集計ソート

void merge(int a[], int p, int q, int r)
{
	int n1 = q-p+1;
	int n2 = r-q;
	int L[n1+1],R[n2+1];
	int i,j,k;
	for(i = 0; i < n1; i++)
	{
		L[i] = a[p+i];
	}
	for(i = 0; i < n2; i++)
	{
		R[i] = a[q+i+1];//      0  ，    +1
	}
	L[n1] = 0x7fffffff;
	R[n2] = 0x7fffffff;
	i = 0, j = 0;
	for(k = p; k <= r; k++)
	{
		if(L[i] <= R[j])
			a[k] = L[i++];
		else
			a[k] = R[j++];
	}
}

void mergeSort(int a[],int p,int r)
{
	if(p < r)
	{
		int q = (p+r)/2;
		mergeSort(a,p,q);
		mergeSort(a,q+1,r);
		merge(a,p,q,r);
	}
}

この再帰ツリーから,第1層の時間代価はcn,第2層の時間代価はcn/2+cn/2=cn.....各層の代価はcnであり,logn+1層が合計される.従って、総時間の代価はcn*(logn+1)である.時間の複雑さはo(nlogn)である.空間複雑度O(n)
ヒープのソート
スタックは完全二叉木の構造であるため,n個のノードを有するスタックに対して高さはO(logn)である.
≪最大ヒープ｜Maximum Heap｜oem_src≫:ヒープ内の最大要素がルート・ノードの場所に格納されます.
ルートノード以外の各ノードの値は、親ノードの値と同じくらいになります.つまり、いずれかのサブツリーに含まれるすべてのノードの値は、ルートノードの値よりも大きくありません.
スタック内のノードの位置番号はすべて決定され、ルートノード番号は1で、各層は左から右に順番に番号付けされます.スタックが完全二叉木であることから、スタック内のあるノードの番号がiである場合、このノードに左右のサブツリーがある場合、左サブツリーのノード番号が2*i、右サブツリーのノード番号が2*i+1であることが分かる(もちろんこれはルートノード番号が1の場合).
そしてn個のノードがあるスタックにおけるリーフノードの番号はn/2+1~nである.ノードn/2+1がリーフノードではないと仮定すると、その左サブノード番号(n/2+1)*2=n+1であり、ノードは合計n個しかない.完全二叉木の葉ノードは一番下の2階にしか現れません.最下層の葉は左側に集中し、逆数2層の葉は右側に集中する.
最大ヒープ関数MAX_のメンテナンスHEAPWEIHU(A,i)は,ノードiの左右のサブツリーが最大スタックであると仮定する.では、ヒープのメンテナンスでは、まずiノードの値と左右のノードの値の大きさを比較し、3つの数の最大値をルートノードの位置に交換します.ルートノードiが左サブノードの値と交換されたと仮定すると、左サブツリーはMAX_を再び呼び出すHEAPWEIHU(A,2*i)は,左サブツリーが最大スタックであるか否かを判断し,もしそうであれば終了し,そうでなければメンテナンスの呼び出しを継続する.したがってMAX_を呼び出すHEAPWEIHU(A,i)の時間的複雑度はO(logn)である.

void heapfy(int a[],int index,int heapsize)
{
	int left = index*2;
	int right = index*2+1;
	int largest = index;
	if(left < heapsize && a[index] < a[left])
	{
		largest = left;
	}
	if(right < heapsize && a[largest] < a[right])
	{
		largest = right;
	}
	if(largest != index)
	{
		swap(a[index],a[largest]);
		heapfy(a,largest,heapsize);
	}
}

void heapSort(int a[],int len)
{
	for(int i = len/2-1; i>=0; i--)
	{
		heapfy(a,i,len);
	}
	for(int i = len-1; i>=0; i--)
	{
		swap(a[i],a[0]);
		heapfy(a,0,i);
	}
}

カウントソート
入力配列a[]は、出力データがb[]に格納され、一時記憶領域c[0...k]
初期化配列cはすべて0に設定され、入力配列a[]を遍歴し、1つの要素の値がiであれば、c[i]の値+1となる.
そこで、このときのc[i]はiに等しい要素の数を保存し、i=0...k
コード

c[i] = c[i] + c[i-1];

は、i以下の要素の数を示します.

void CountingSort(int a[], int *b)
{
	int c[13] = {-1};
	for(int i = 0; i < 10; i++)
		c[a[i]]++;
	for(int i = 1; i < 13; i++)
		c[i] = c[i] + c[i-1];
	printf("hello world
");
	for(int i = 9; i >=0; i--)
	{
		#printf("a[%d] = %d\t,b[%d] = %d\t,c[%d] = %d
",i,a[i],i,b[i],i,c[a[i]]);
		b[c[a[i]]] = a[i];
		c[a[i]] = c[a[i]] -1;
	}
} 

時間複雑度はO(k+n)であり、実際に中級k=O(n)を適用する場合、一般的に技術ソートが採用され、総時間複雑度はO(n)である.
ベースソート
バケツソート