数据结构实验之排序一：一趟快排

本是古典何须时尚 2022-04-06 15:08 233阅读 0赞

Problem Description

给定N个长整型范围内的整数，要求输出以给定数据中第一个数为枢轴进行一趟快速排序之后的结果。

Input

连续输入多组数据，每组输入数据第一行给出正整数N(N < = 10^5)，随后给出N个长整型范围内的整数，数字间以空格分隔。

Output

输出一趟快速排序后的结果，数字间以一个空格间隔，行末不得有多余空格。

Sample Input

8  
49 38 65 97 76 13 27 49

Sample Output

27 38 13 49 76 97 65 49  
这道题实际上不不是用快排进行排序，而是只进行一次排序，也就是删除快速排序的递归。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int a[100001];
    
    void sort(int l,int r)
    {
        if(l<r)
        {
            int i=l;
            int j=r;
            int key=a[0];
            while(i<j)
            {
                while(i<j&&key<=a[j])
                {
                    j--;
                }
                a[i]=a[j];
                while(i<j&&key>=a[i])
                {
                    i++;
                }
                a[j]=a[i];
            }
    
            a[i]=key;
        }
    }
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            int i;
            for(i=0; i<n; i++)
            {
                scanf("%d",&a[i]);
            }
            sort(0,n-1);
            for(i=0; i<n; i++)
            {
                if(i==n-1)
                {
                     printf("%d\n",a[i]);
                }
                else
                {
                    printf("%d ",a[i]);
                }
            }
        }
        return 0;
    }

一次快排过程解释：49 38 65 97 76 13 27 49 是原始序列  
由于以第一个为轴心，所以先用key 来暂存49；  
然后i 和 j 分别指向 首尾 即 i指向 49 j 指向 49（后）；  
首先j开始向前遍历，查找比key（49）小的数，查找到27  
此时27 就要更新i当前的位置，序列更换成  
27 38 65 97 76 13 27 49  
此时i开始从前往后查找比49大的数，查找到65，此时就会更换后面j的值  
序列换成 27 38 65 97 76 13 65 49  
然后j再开始向前查找比65 小的数，查找到13，此时更新i的值  
序列换成 27 38 13 97 76 13 65 49  
然后i开始从前往后查找比49大的数，查找到97，此时就会更换后面j的值  
序列换成 27 38 13 97 76 97 65 49  
此时j 再从后往前遍历，i,和j 在13后的97相遇，此时循环终止  
将key存的值给97  
序列变成 27 38 13 49 76 97 65 49