Data structure of the experimental order of a: a row of fast row（learning quick sorting）.

Problem Description

給定N個長整型範圍内的整數，要求輸出以給定資料中第一個數為樞軸進行一趟快速排序之後的結果。

Input

連續輸入多組資料，每組輸入資料第一行給出正整數N(N < = 10^5)，随後給出N個長整型範圍内的整數，數字間以空格分隔。

Output

輸出一趟快速排序後的結果，數字間以一個空格間隔，行末不得有多餘空格。

Example Input

8
49 38 65 97 76 13 27 49      

Example Output

27 38 13 49 76 97 65 49      

       This topic is obviously in the practice time complexity is O (nlogn) sorting method, we take this opportunity to talk about a commonly used internal sorting method: fast sort.

       Quick sorting is an improvement to the bubble sort.The basic idea is that the sorted records are divided into separate parts by a sort of sorting, and some of the recorded keywords are smaller (or equal) than the other recorded keywords, and the two parts can be recorded separatelySorted to achieve the entire sequence.

        Let us assume that the number of sequences to be sorted is {a [l], a [i + 1], a [l + 2], ..., a [r]} first take a record (we select the first position in the sequence) As the standard keyword, and then rearrange the remaining records, all the keywords less than or equal to its records are placed in the left child sequence, all keywords greater than or equal to it are placed in the right child sequence.This allows the sequence to be divided into two sub-sequences (the value of any keyword in the left child sequence is less than or equal to the value of any keyword in the right subsequence).

       The specific approach is: with two pointers i and j, their initial values were l and r, the first record in the sequence of the keyword m, the first from the location of j refers to the first search to find the first The keyword is smaller than the record of m, and then search back from the location of i, find the first keyword is greater than m records, exchange them with each other, repeat these two steps until i> j .

AC code is as follows:

#include<stdio.h>
#include<stdlib.h>
int ksort(int a[],int low,int high)
{
    int key=a[low];
    int t;
    while(low<high)
    {
        while(low<high&&a[high]>=key)   --high;
        {
            t=a[low];
            a[low]=a[high];
            a[high]=t;
        }
        while(low<high&&a[low]<=key)    ++low;
        {
            t=a[low];
            a[low]=a[high];
            a[high]=t;
        }
    }
    return low;
}
int main()
{
    int a[100000],i,n;
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        ksort(a,0,n-1);
        for(i=0;i<n-1;i++)
            printf("%d ",a[i]);
        printf("%d\n",a[n-1]);
    }
    return 0;
}

      

         The time complexity of fast sorting is O (nlogn), fast, but it is an unstable sorting method. If the initial record sequence is ordered or ordered, the fast sort will degrade into a bubble sort, and its time complexity is O (n ^ 2). So we generally use the median position of the record of the keyword as a standard keyword, which can simplify the code, but also to prevent degradation. Fast sorting requires a stack of spaces to implement recursion.