順序付けアルゴリズムは入門から精通までの六--クイックソート


迅速に並べ替えられたアルゴリズムは、分割されたアルゴリズムであり、再帰的アルゴリズムである.通常の場合、高速の並べ替えアルゴリズムは既知の最も速いアルゴリズムであり、したがって、このアルゴリズムは高速の並べ替えである.通常はデータの分布が平均的で、鍵の範囲が大きいことを指します.キーワードが昇順または逆順である場合、正規化された並べ替えは高速な並べ替えよりもずっと速いです.キーワードの範囲が非常に狭い場合、カウント順序の時間的複雑度はO(n)に低くすることができます.その方法は、まず、枢軸要素baseを見つけることです.2.並べ替えられた配列をスキャンして、この配列を2つの部分に分け、左の部分のすべての要素がベースに等しくないようにします.右の部分のすべての要素はベースより大きいです.3.左部分のサブアレイに対してこの操作を続けます.4.右部分のサブアレイに対して同じ操作をします.5.配列の長さが1より小さいまで再帰し続ける.
次のコードはこのアルゴリズムの実現である.その中心はpartition_である.ソト関数は、この関数の配列のサブ区間[low,high]をスキャンします.このアルゴリズムは,要軸要素としてarr[low]を取り,双方向走査法を採用した.要素が枢軸要素に等しい場合は左にスキャンし、right--、要素が枢軸要素より小さい場合は右にスキャンし、left+++.スキャンが終了したら元の区間[low,right]を3つのサブ区間に分け、[low,left-1]中間区間[left,left]は一つの要素だけを含み、右区間[left+1,high]は、再度partion_を呼び出します.ソトは左右の区間に対して同じ処理をします.以下のコードの中で、区間長がINSERT_に等しい場合SORT_THRESHLDは、挿入ソートアルゴリズムを呼び出します.

#include 
#include 
#include "sorts.h"

void partition_sort(ELE_TYPE arr[], int low, int high)
{
	ELE_TYPE base;
	int left,right;
	
	if ( high-low+1 <= INSERT_SORT_THRESHOLD)
	{
		insert_sort(arr+low, high-low+1);
		return ;
	}

	left=low;right=high;
	base= arr[low];
	
	while (right>left)
	{
		while (right>left && arr[right]>= base)
			right--;
		
		if ( right>left)
		{	arr[left]=arr[right];	left++;}	// fill the hole, the hole is arr[left]

		while (left

上の実装は一番簡単なバージョンです.しかし、このバージョンには欠点があります.特定のデータ分布については、配列が厳密な非漸減シーケンスまたは非インクリメントシーケンスのように、このアルゴリズムの再帰的深さはnに増加し、nは配列長である.時間複雑度はO(n^2)に増加し,空間複雑度はO(n)に増加した.性能が悪くなるのはまだ小さいことで、致命的なのは、スタックのスペースが小さいため、配列が大きいと、スタックがオーバーフローして、プログラムが崩壊します.
問題を解決するために、人々はいろいろな方法を考え出しました.一つの方法は、シーケンスの中で、枢軸要素として一つの要素をランダムに選択することである.もう一つの方法は、配列の一番左、中間、一番右の三つの要素の中間値を枢軸とし、三者を中法と略称する.
配列に対するスキャン方法も双方向スキャンに限定されない.アルゴリズム導論(第二版)第7章で与えられた方法は、左から右への方向に配列をスキャンし、順序付けされる配列を3つの部分に分け、左の部分<=x,xは枢軸要素、中間の部分>x、右の部分は未ソート部分である.