交换排序——快速排序

电玩女神 2022-03-20 02:54 162阅读 0赞

/*
     *算法思想：
     *  在待排序元素中选定一个作为中间数，使该数据表中的其他元素的关键字与“中间数”
     *  的关键字相比较，将整个数据表划分成为左右两个子表，其中左边子表任一元素的关键字
     *  不大于右边子表中任一元素的关键字，然后再对左右子表分别进行快速排序，直到整个数据表有序
     */
    
    /*
     *过程分析：
     *  1.首先较典型的选择“中间数”的方法是选择第一个元素
     *  2.定义一个x来存放中间数，使得中间数可以随时与其他元素比较，同时该元素在表中的位置
     *    可以腾出来，方便比较后的元素存放。
     *  3.设置两个指针low、high，初始时分别记录数据表中第一个和最后一个元素的位置。当选取
     *    第一个元素为中间数后（x=r[low]），low指向的空间可以被腾出来
     *  4.首先通过high所记录的位置值，从最后边往前搜索，将第一个关键字小于中间数的元素存放
     *    到low所指示的空位（左子表的空位），这是high所指示的位置就成了空位
     *  5.再从最前边开始往后面搜索，将第一个关键字不小于中间数关键字的元素放在high所指示的
     *    位置上，这时low指示的位置成为空位
     *  6.重复4、5步骤，直到所有元素均与关键字比较过，此时有low与high相等，此位置刚好存放中间数
     *  7.继续在分出来的左右子表中进行以上步骤，直到所有子表的表长不超过1为止。
     */
    
    /*
     *性能分析：
     *  时间复杂度为O(nlog2n)。该排序方法被认为是目前最好的一种内部排序方法
     */
    
    #include <stdio.h>
    #define length 9
    
    //对order中left到right为止的数据进行一次快速排序的划分，返回划分后的中间数的位置
    int Partition(int *order,int left,int right)
    {
        int x;
        int low,high;
        x=order[left];
        low=left;high=right;
        while(low<high)
        {
            while(order[high]>=x && low<high)high--;//从右往左扫描，找到第一个小于x的元素
            if(low<high)
            {
                order[low]=order[high];
                low++;
            }
            while(order[low]<x &&low<high)low++;
            if(low<high)
            {
                order[high]=order[low];
                high--;
            }
        }
        order[low]=x;
        return low;
    }
    void QuickSort(int *order,int low,int high)
    {
        int mid;
        if(low<high)
        {
            mid=Partition(order,low,high);
            QuickSort(order,low,mid-1);//递归
            QuickSort(order,mid+1,high);
        }
    }
    
    int main()
    {
        int order[length]={0,49,52,65,97,35,13,27,49};
        QuickSort(order,0,length-1);
        int i;
        for(i=0;i<length;i++)printf("%d  ",order[i]);
        return 0;
    }