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.