ソートアルゴリズム(3)のバブルソート、高速ソート

バブルソート
バブルソートの原理:隣接する要素を比較し、前のペアが後のペアより大きい(小さい)場合は、2つを交換します.隣接する各ペアに対して同じ作業を行い、最初のペアから最後のペアまで行います.このままでは、最後のエレメントが最大になるはずです.(小さい)の数.すべての要素について、最後の1つを除いて、上記のステップを繰り返します.数値のペアがないまで、より少ない要素に対して上記のステップを繰り返します.

void Swap(int* a, int* b)
{
	int tmp = *a;
    *a = *b;
    *b =tmp;
}

void BubbleSort(int* a, int n)
{
	for (int end = n - 1; end > 0; --end)
	{
		int flag = 0;
		for (int i = 0; i < end; ++i)
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}

クイックソート
クイックソートはHoareが1960年に提案した.基本的な考え方は、ソートするデータを1回のソートで独立した2つの部分に分割し、その一部のすべてのデータが他の部分のすべてのデータよりも小さくなった後、この方法で2つの部分のデータをそれぞれ迅速にソートし、ソートプロセス全体を再帰的に行うことで、データ全体が秩序化されたシーケンスになることです.一部のソートには、1.Hoare版;2.掘削方法;3.前後指針法
Hoare版

int partition1(int* a, int left, int right)
{
	//             
	int key = a[right];
	int keyindex = right;
	while (left < right)
	{
		//     key   
		while (left < right && a[left] <= key)
			++left;
		//     key   
		while (left < right && a[right] >= key)
			--right;
		//       
		Swap(&a[left], &a[right]);
	}
	//     left,right            
	Swap(&a[left], &a[keyindex]);
	return left;
}

ピット工法

int partition2(int* a, int left, int right)
{
	int key = a[right];
	while (left < right)
	{
		while (left < right && a[left] <= key)
			++left;
		//      key        " "  ,      " "
		a[right] = a[left];
		
		while (left < right && a[right] >= key)
			--right;
		//      key        " "  ,      " "
		a[left] = a[right];
	}
	//            " ",        
	a[left] = key;
	return left;
}

ぜんごししんほう

int partition3(int* a, int left, int right)
{
	int prev = left - 1;
	int cur = left;
	int key = a[right];

	while (cur < right) 
	{
		if (a[cur] < key && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		++cur;
	}
	++prev;
	Swap(&a[prev], &a[right]);

	return prev;
}

ファスト・キューの再帰的な実装:

void QuickSort(int* a, int left, int right)
{
	//       
	if (left >= right)
		return;

    int portion = partition1(a, left, right);
	//int portion = partition2(a, left, right);
	//int portion = partition3(a, left, right);
	
	// [left, portion-1]  key  [portion+1, right]
	QuickSort(a, left, portion - 1);
	QuickSort(a, portion + 1, right);
}