データ構造とアルゴリズム分析-高速ソート

大学2年生は実はすでに速い列を勉強しましたが、今は基本的に速い列の細部と具体的な実現を忘れています.今、可能な面接の準備のために、クイックソートを再復習します.温故知新、古人は誠実に私をいじめない.主に「アルゴリズム導論」を教材としている.
「アルゴリズム導論」という本はアルゴリズムを紹介する時、まずアルゴリズムの説明を与えて、つまり偽コード、それからアルゴリズムの正確性の証明と最適化です.本文はまずアルゴリズムの擬似コードを与え,正確性の証明については,やはり自分が適任かどうかを見る.
スナップフレーム

QUICKSORT(A,p,r)

if p < r

    then q = PARTITION(A,p,r)

    QUICKSORT(A,p,q-1)

    QUICKSORT(A,q+1,r)

スナップショットを理解すると、スナップショットの核心思想は、選択した配列の値が左の要素よりも小さく、右の要素がそれよりも大きいことを保証する配列を実現するたびに実現されることを知っています.これにより、変更値の左側と右側の要素が必ず整列していることは保証されないが、ソート後の配列における相対位置が変化しないことは保証される.例えば、A[i]はi番目の位置にあり、配列全体が整列した後も、A[i]はiにあるに違いない.これにより、上記のコードに再帰するときにqの値を含まない理由がわかります.その位置が確定しているからです.
以上の分析を経て,実際の符号化において速い列の大まかなフレームワークを書くことは難しくない.
はやまち
明らかに、速排は分治の思想を採用している.1つのタスクを2つ以上の部分に分けて解決します.しかし、どのように区別するかが速排の難点とポイントです.面接の工程でこの質問をされて、どうやって分けるか忘れてしまいました.
ソートするたびに左の配列が指定した要素よりも小さく、右の配列が大きくなることを保証するには、比較の対象として参照値を選択する必要があります.この参照値をマスターと呼びます.メンバーが確定したら、比較を始めます.
選択するたびに右端の要素がプライマリとして選択されると、要素の位置を左から右に比較して決定できます.具体的には、次の疑似コードを参照してください.

PARTITION(A,p,r)

x = A[r]

i = p - 1

for j : p to r

    do if A[j] < x

            then i = i + 1

            exchange(A[i],A[j])

exchange(A[i+1],A[r])

return i+1

大まかな戦略は,主元より小さい要素をできるだけ前に並べることである.こうして、不思議な配列全体が並び終わりました.
Cコード実装

/*************************************************************************

    > File Name: myfiles/C/sort/quicksort.c

    > Author: ma6174

    > Mail: [email protected] 

    > Created Time: 2014 10 06      11 38 28 

 ************************************************************************/



#include<stdio.h>

#define maxn 100

int A[maxn];

int n;

/*      */

void read()

{

	printf("input the num:
");

	scanf("%d",&n);

	int i;

	for(i = 0; i < n; i++) {

		scanf("%d",&A[i]);

	}

}

/*    */

int partition(int A[], int p, int r)

{

	int key = A[r];

	int i = p - 1;

	int j;

	for(j = p; j < r; j++) {

		if(A[j] < key) { /*     ，            ，           */

			i++;

			int temp = A[i];

			A[i] = A[j];

			A[j] = temp;

		}

	}

	int temp = A[i+1];

	A[i+1] = key;

	A[r] = temp;

	return i+1;

}

/*    */

void quick_sort(int A[], int p, int r)

{

	if(p < r) {

		int q = partition(A,p,r);

		quick_sort(A,p,q-1);

		quick_sort(A,q+1,r);

	}

}

/*    */

void write() 

{

	printf("the sorted array:
");

	int i;

	for(i = 0; i < n; i++) {

		printf("%d ",A[i]);

	}

	printf("
");

}

int main()

{

	read();

	quick_sort(A,0,n-1);

	write();

}

高速配列の最適化
自分でドラフト紙に全体の早送りの手順を書くと,逆順のシーケンスに対して上の早送りバージョンの複雑さがO(n 2)であることがわかり,最適化されている.単純で、要素をメタとしてランダムに選択します.
-end-