まず、アルゴリズムの考えを探る

アイデア: 選択された要素と、リストの各要素とを比較することにより、2つのリストに分けクイック·アレイは、重要な要素と呼ばれている. これらの要素は以下の重要な要素は、進められと最初のリストにあると, より大きな粒子は、バックキーと第二子のリストに入れて. リストは同じ長さになるまでこのような共有してください 1

コンテンツ
1. アルゴリズムのアイデア
2. クイックソートをインストール
3. 取り外し再帰クイックソート
4. クイックソートで末尾再帰を使用して、
5. クイックソートを使用して、C言語で利用可能です
6. クイックソートによって配列構造をソート

以下の重要な要素を選択する方法があります。:
– 一番下の要素を選択し、ヘッドまたは主要な要素を作る.
– 主要な要素として、リストの途中で要素を選択します.
– 中央値要素を選択 3 素子ヘッド, 重要な要素として、中間および最後に立って.

– 主要な要素としてランダムな要素を選択してください (特殊なケースを避けるために選択されるか)

イラスト:

C言語でのインストール:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>		// thu vien de khoi tao tham so cho ham rand()
#define swap(type, a, b) {type temp = a; a = b; b = temp; } // hang hoan vi

void quickSort(int *a, int l, int r)
{
	srand(time(NULL));	//khoi tao tham so ham rand()
	int key = a[l + rand() % (r-l+1)];	//lay khoa la gia tri ngau nhien tu a[l] -> a[r]
	//int key = a[(l+r)/2];
	int i = l, j = r;

	while(i <= j)
	{
		while(a[i] < key) i++;		// tim phan tu ben trai ma >=key
		while(a[j] > key) j--;		// tim phan tu ben trai ma <=key
		if(i <= j)
		{
			if (i < j)
				swap(int, a[i], a[j]);	// doi cho 2 phan tu kieu int a[i], a[j].
			i++;
			j--;
		}
	}
	//bay gio ta co 1 mang : a[l]....a[j]..a[i]...a[r]
	if (l < j) quickSort(a, l, j);	// lam lai voi mang a[l]....a[j]
	if (i < r) quickSort(a, i, r); // lam lai voi mang a[i]....a[r]
}

int main ()
{
	int i, arr[] = { 40, 10, 100, 90, 20, 25 };
	quickSort(arr, 0, 5);
	for (i=0; i<6; i++)
		printf ("%d ", arr[i]);
	return 0;
}

アルゴリズムは、ラインからインストールされている 6 流れるように 29. その行で 21 スワップ(int型, ザ·[で], ザ·[J]); 順列のための定数である 2 の[で] と[J] 行で定義されている 4 そしてそれは、次のコードと同等です (あなたが直接それを変更することができます):

{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

また、次のコードを見ることができます, このコードで、私は画面内に配列のすべてのバリエーションを持っている, Lの, R, で, 彼らは正確にステップの変化を観察したJ助ける:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>		// thu vien de khoi tao tham so cho ham rand()
#define swap(type, a, b) {type temp = a; a = b; b = temp; } // hang hoan vi

void quickSort(int *a, int l, int r)
{
	srand(time(NULL));	//khoi tao tham so ham rand()
	int key = a[l + rand() % (r-l+1)];	//lay khoa la gia tri ngau nhien tu a[l] -> a[r]
	//int key = a[(l+r)/2];
	int i = l, j = r;
	printf("\n\nl = %d   r = %d    select: key = %d  (random) ",l, r, key);

	while(i <= j)
	{
		//printf("n");
		printf("\n\n\ti : %d", i);
		while (a[i] < key) { i++; printf(" -> %d",i); }
		printf("\n\tj : %d", j);
		while (a[j] > key) { j--; printf(" -> %d",j); }
		if(i <= j)
		{
			if (i < j)
			{
				swap(int, a[i], a[j]);	// doi cho 2 phan tu kieu int a[i], a[j].
				printf("\n\tswap(a[%d], a[%d])  swap(%d, %d)", i, j, a[i], a[j]);
			}
			i++;
			j--;
			printf("\n\tarr[] : ");
			for (int i=0; i<8; i++)
				printf ("%d ", a[i]);
		}
	}
	//bay gio ta co 1 mang : a[l]....a[j]..a[i]...a[r]
	if (l < j) quickSort(a, l, j);	// lam lai voi mang a[l]....a[j]
	if (i < r) quickSort(a, i, r); // lam lai voi mang a[i]....a[r]
}

int main ()
{
	int i, arr[] = { 2, 8, 7, 1, 3, 5, 6, 4  };
	int n = 8;
	printf("\n\nArray befor sort: ");
	for (i=0; i<n; i++)
		printf ("%d ", arr[i]);

	quickSort(arr, 0, n-1);

	printf("\n\nArray after sort: ");
	for (i=0; i<n; i++)
		printf ("%d ", arr[i]);
}

我々は、アルゴリズムの効率は、値選択マーカーに依存することを見出し (または重要な要素).

– ベストケース: 我々は中央値の要素を選択した各パーティション (残りの要素よりか等しい半分の粒子が大きいまたは要素の数の半分によると少ない) ランドマークとして. このシーケンスは、2つの等しい部分に分割されているとき, 私たちはLOG2が必要です(N) パーティションは、仕上げをソートされた後. 私はまた、各パーティションに見える、我々はn個の要素を閲覧する必要があります. Oの最良の場合でそう複雑(nlog2(N)).

– 最悪のケース: 我々はランドマークとしての要素を最大値や最小値をターゲットに選択した各パート. その配列は、二つの凹凸部に分割された場合: 一部だけつの要素, 残りは、n-1の要素を持っています. 従って, 私たちは完成した新しいパーティションを配置する必要がn回. Oの最悪の場合にはそのように複雑(N2).

* だから我々は、次のクイックソートの複雑さを持っています:
– ベストケース: ザ·(nlog2n)
– 最悪のケース: ザ·(N2)
– 平均ケース: ザ·(nlog2n)

QUICソートで再帰を排除

再帰的なアルゴリズムパラメータの性質はスタック再帰に格納されています (スタック) 取得したハンドルをオンにします. あなたが重いデータが発生した場合そう簡単にスタックオーバーフローが発生します. 再帰の再帰アルゴリズムを削減すると, 左右の保存された値に置き換え、私のクイックソートの各呼び出しの再帰関数と 2 でサブシーケンス 2 スタックのS1のVAのSr, 中止するとき. また、我々はまた、左右の中に共通の値を格納することができます 1 スタック, 取り出したときにかかります 2 連続要素.

B1: 初期化 2 スタック栄Slは, 各サブアレイの値LとRの値を保存するためのSr.
B2: 問題の当初の範囲から 0 n-1個の, 私のSLにおけるRとL及びSrの点に注意してください。
B3: LのSLから出て行け, のSrからR
B4: パーティションシリーズA[L] .. ザ·[R] 街 2 シリーズA[L]..ザ·[J] とA[で]..ザ·[R]
B5: Lの場合 < S1及びSrのに格納されたLとJ J, 私の場合 < R iおよびRのSL及びSrに格納されています,
B6: スタックは、B3戻っ空でない場合.

ここでコードがインストールされています, コー​​ドの用途に使用することができます スタックtrong C , あなたが望んでいないまたはC に精通していないならば、基準の建物内にスタックすることができます 1 常にスタック.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>		// thu vien de khoi tao tham so cho ham rand()
#include<stack> 		// Su dung Stack trong C++
#define swap(type, a, b) {type temp = a; a = b; b = temp; }

using namespace std;

void quickSortUnRecursive(int *a, int l, int r)
{
	srand(time(NULL));
	stack Sl;		// Stack left
	stack Sr;		// Stack right
	Sl.push(l);			// dua phan tu dau tien l vao Sl
	Sr.push(r);			// dua phan tu dau tien r vao Sl

	while(!Sl.empty())	// trong khi stack khong rong
	{

		int l = Sl.top(); Sl.pop();		// lay phan tu dau tien trong Sl l ra
		int r = Sr.top(); Sr.pop();		// lay phan tu dau tien trong Sr r ra
		int key = a[l + rand() % (r-l+1)];
		int i = l, j = r;
		while (i <= j)		// phan hoach thanh 2 day con
		{
			while (a[i] < key) i++;
			while (a[j] > key) j--;

			if(i <= j)
			{
				if (i < j)
					swap(int, a[i], a[j]);
				i++;
				j--;
			}
		}
		if (l < j) { Sl.push(l); Sr.push(j); }	// dua 2 dau mut l va j vao Sl va Sr
		if (i < r) { Sl.push(i); Sr.push(r); }	// dua 2 dau mut i va r vao Sl va Sr
	}
}

int main ()
{
	int i, arr[] = { 40, 10, 100, 90, 20, 25 };
	quickSortUnRecursive(arr, 0, 5);
	for (i=0; i<6; i++)
		printf ("%d ", arr[i]);
	return 0;
}

クイックソートで末尾再帰を使用して、

また、クイックソートアルゴリズムを構築するために末尾再帰アルゴリズムを使用することができます, 関数の、すなわち唯一の再帰呼び出し, しかし、我々は重要な要素を選択する必要がありますこれを行うには、配列の最初の要素が持続または配置すべきです. 次のように我々はこのケースを分析することができます:

まず、に分布範囲を決定します 2 次の配列:

int partition(int *a, int l, int r)
{
	int key = a[r];		// xac dinh khoa
	int i = l - 1, j;	// khoi tao i, j
	for (j=l; j<r; j++)	// duyet mang
		if (a[j] <= key) //neu a[j] <= key
		{
			i++;
			swap(int, a[i], a[j]);	// hoan vi
		}
	swap(int, a[i+1], a[r]);	// hoan vi voi phan tu khoa
	return i + 1;	// tra ve vi tri cua khoa
}

範囲を分割した後、私たちはあります 2 行, 左側の範囲が小さい要素またはキーであります, 右は重要な要素の大きい配列であります.

次のように今、私たちはクイックソートの末尾再帰を構築します:

void TailRecursiveQuicksort(int *a, int l, int r)
{
	while (l<r)
	{
		int q = partition(a,l,r);	//lay vi tri khoa
		TailRecursiveQuicksort(a, l, q-1);		// sap xep day ben trai
		l = q + 1;		// khi day ben trai sap xep xong ta chuyen sang day ben phai
	}
}

さらに, 目的再帰的に呼び出されたときにそのように, 私たちのスタックは極力含まれている可能性があります, 次のように私たちは、ビットのアルゴリズムを改善し:

void TailRecursiveQuicksort_2(int *a, int l, int r)
{
	while (l<r)
	{
		int q = partition(a,l,r);
		if (q < (l + (r-l)/2))	//Neu vi tri khoa < 1/2 do dai day thi sap xep ben phai
		{
			TailRecursiveQuicksort_2(a, l, q-1);
			l = q + 1;
		}
		else	//Neu vi tri khoa >= 1/2 do dai day thi sap xep ben trai
		{
			TailRecursiveQuicksort_2(a, q + 1, r);
			r = q-1;
		}
	}
}

C言語で構築されたクイックソートを使用してください

私たちのためのqsort関数を構築しているC のライブラリで、私たちはすぐにそれを使用することができます.

#include<stdio.h>
#include<stdlib.h>

int arr[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a > *(int*)b );
}

int main ()
{
	  int n;
	  qsort (arr + 1, 4, sizeof(int), compare);
	  for (n=0; n<6; n++)
		 printf ("%d ",arr[n]);
	  return 0;
}

関数呼び出しのqsortで: のqsort (ARR + 1, 4, はsizeof(int型), 比較します);
ARR + 1 開始位置のアレイ配置であります, ここで要素の一種に相当します[1] = 10 と 配置します 4 要素 から、すなわち[1] へ[4].
はsizeof(int型) サイズ 1 配列内の要素. 配列の場合は実際の型は、はsizeofを持っています(フロート).
比較します 上下に配置されているか、以下の構造が配列を決定するために使用されるように構築されて

int compareMyType (const void * a, const void * b)
{
	return ( *(MyType*)a @ *(MyType*)b );
}

これらの中でも、配列要素の型がMyTypeです. “@” 定義された動作であります. 事前に定義されたライブラリ米国で 3 操作 >, ==, <. この例では、使用します *(int型*)ザ· > *(int型*)増加を配置するB, その逆の場合 *(int型*)B > *(int型*)割引を手配します.

C言語で使用可能なソートクイックソート配列構造

我々が持っている場合は、次の我々が行います 1 構造要素の配列構造体とすることによりソートします 1 特定のフィールド.

私は定義します 1 操作 “@” 比較します 1 顎で特定のフィールド ブール演算子 この関数を再構築 int型の比較 鋼操作が構築されています:

#include<iostream>
#include<cstdlib>
using namespace std;

struct St
{
	string name;
	int scores;
};

bool operator * ( const St &t, const St &u )	// dinh nghia phep toan "*"
{
	return t.name > u.name;	//sap xep tang dan theo ten
}

bool operator/( const St &t, const St &u )	// dinh nghia phep toan "/"
{
	return t.scores < u.scores;	//sap xep giam dan theo diem
}

int compare_name (const void * a, const void * b)
{
	return ( *( St*)a * *(St*)b );	//chi duoc su dung phep toan "*" de sap xep
}

int compare_scores (const void * a, const void * b)
{
	return ( *( St*)a / *(St*)b );	//chi duoc su dung phep toan "/" de sap xep
}

int main ()
{
	St arr[] = { {"Hien", 9}, {"Cuong", 7}, {"Nhung", 8}, {"Nam", 6} };

	int n = sizeof( arr ) / sizeof( St );
	qsort (arr, n, sizeof(St), compare_name);

	cout << "\nDanh sach xap xep tang dan theo ten:\n";
	for (int i = 0; i < n; i++ )
		cout << arr[ i ].name << ' ' << arr[ i ].scores << endl;

	qsort (arr, n, sizeof(St), compare_scores);
	cout << "\nDanh sach xap xep giam dan theo diem:\n";
	for (int i = 0; i < n; i++ )
		cout << arr[ i ].name << ' ' << arr[ i ].scores << endl;

	return 0;
}

上記のコードでは、私は特殊記号を使用します * と / (しかし、より正確には、通常のシンボルは、乗算や除算として使用されています) 配置のための操作を定義します. 我々はいくつかの他の操作などの文字を使用することができます %, ^, *, /, +, -, >, =, < 新しい操作を定義します.

サイトの数から基準記事とサービス:
recurial.com/programming/using-tail-recursion/
mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html
ブック: アルゴリズムの概要
staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap08.htm
cplusplus.com/reference/cstdlib/qsort/?KW =のqsort