PTAデータ構造とアルゴリズム7-12並べ替え

間違いがあればご指摘ください
テーマを提示:
N個(長整数範囲)の整数を与え,小さいものから大きいものへのソート後の結果を出力することが要求される.
本問題は,種々の異なるソートアルゴリズムの種々のデータの場合の表現をテストすることを目的とする.各グループのテストデータの特徴は以下の通りである.
データ1:要素が1つしかありません.データ2:11個の異なる整数で、基本的な正確性をテストします.データ3:103個のランダム整数;データ4:104ランダム整数;データ5:105ランダム整数;データ6:105シーケンス整数;データ7:105個の逆順序整数;データ8:105の基本秩序の整数.データ9:105ランダム正の整数で、各数値は1000を超えません.入力形式:
1行目に正の整数N(≦10 5)を入力し、1行目にN個(長整数範囲)の整数を入力し、その間をスペースで区切る.
出力フォーマット:
1行に小から大へ並べ替えた結果を出力し、数字間は1つのスペースで区切られ、行末に余分なスペースがあってはならない.
入力例:11 4 981 10-17 0-20 29 50 8 43-5
出力サンプル:-20-17-50 4 8 10 29 43 50 981
これは普通の並べ替え問題です最大Nは10^5級まで取るのでNlogn以下の時間複雑度の並べ替えアルゴリズムを選択すればいいです.私が選んだのは高速並べ替えです.

#include

void QuickSort(long *array,int left,int right);

int main(void)
{
    int N,i;
    scanf("%d",&N);
    long array[N];

    for(i=0;i=right)
      return ;

    int i,j;
    long temp;
    i=left;
    j=right;

    while(i=array[left]&&i

ここでよく言われる質問について議論します.クイックソートは右から始まるかどうか、私たちが見ている多くのバージョンは右から始まるのですが、ネット上では、必ずしも右から始まる必要はありません.交換を保証するときは基数の逆から始めればいいのではないでしょうか.この良い文章を見ることができます.なぜ右から始めなければならないのか、私は少し面倒だと思います.私たちはビッグデータを速く並べ替えるときに基本的な秩序配列を防ぐために、一般的に3数取りの方法で基数を見つける(qsortは別に計算して、それは先に1.5*lognを速く並べて、まだ並べ終わっていないうちにスタックを選んでスタックオーバーフローを避ける)ので、あなたの基数位置と速く並べ始める位置が逆であることを保証しなければなりません.だから、私たちがleft、right位置の変数を交換したかどうかをマークする変数を利用したいと思っています.速い列の思想は基数があるべき位置を見つけると同時に逆順対を交換することであるため、left,rightの交換が行われていなければ、基数が見つからなかった位置を説明する.つまり、基数はこの輪の中で位置を移動する必要はない.以下、その文章のデータでシーケンス2 1 4 9を説明する.私たちはleft=0を取り、right=3は右から速い列を行う.私たちは第1ラウンドのleftが2に着いたことを発見し、rightも2に着いた.しかし、この中で逆シーケンスペアの交換が行われていないので、基数とleftの位置を交換しないで、次の交換はシーケンス2 1とシーケンス9になって速く並べ替えます.これにより、基数位置と並べ替え開始位置が逆にならなければならないという問題が解決されます.