快速排序实现

缺乏、安全感 2022-09-30 12:53 169阅读 0赞

算法思想：采用递归的思想，在将待排序的的N个记录任意选择一个枢纽，经过一趟排序，将N个记录中比选择枢纽的值小的记录放在左子表中，把比枢纽的值大的记录放在右子表中。然后枢纽的位置在左右子表的分界处。分别对左右字表重复以上过程，知道子表只有一个记录，那么排序就完成了。

需要两个函数：  
一个是通过N个无序的记录和它的上界和下界，得到枢纽的位置，以便确定这个无序的记录可分的左右字表的上下界。  
另外一个就是对左右子表分别进行排序递归需要的函数。

快速排序的趟数取决于递归树的深度。每一趟需要N次的比较。所以：

算法的时间复杂度：O（nlog2n）

快速排序是递归的，需要一个栈存放数据。  
算法空间复杂度：O（n）–最坏情况； O(log2n)–最好情况

算法特点：不稳定，速度较快，难以用于链式结构。

一趟排序中元素移动的示意图：![这里写图片描述][SouthEast]

注意事项：当low和high相等时候，一定要把当前low或high位置的值置为pivoty。

直接上代码：

#include <iostream>
    #include<stdio.h>
    using namespace std;
    
    //得到划分左右子树的枢纽下表标的函数
    int getPirotkey_position(int* original,int low ,int high)//作一趟排序，得到枢纽值
    {
        int priotkey;//枢纽的值大小
        priotkey=original[low];//
        while(low<high)//从表的两端交替向中间扫描
        {
               while(low<high&&original[high]>=priotkey)//循环目的是从右端向左找到比枢纽值小的元素进行交换
                    high--;//上界的下标往左移
                    original[low]=original[high];//把比枢纽值小的元素放到最低位
    
    
                while(low<high&&original[low]<=priotkey)//循环目的是从左端向右找到比枢纽值大的元素进行交换
                    low++;
                    original[high]=original[low];
    
        }
        original[low]=priotkey;//确定枢纽位置，不执行这一步会出错
        return low;//high也可以，此时两个指针下标重合，都是指向枢纽下标。
    }
    
    //循环做快速递归的函数
    void QuickSort(int* original,int low,int high)
    {
        if(low<high)//递归的终止条件，很重要
        {
           QuickSort(original,low,getPirotkey_position(original,low,high)-1);//对左子树进行快速排序
           QuickSort(original,getPirotkey_position(original,low,high)+1,high);//对右子书进行快速排序
        }
    }
    int main()
    {
        int paixu[100]={
       0};
        int i,n;
        paixu[0]=0;
        for(i=1;i<100;i++)
        {
            scanf("%d",&paixu[i]);
            if(getchar()=='\n')
                break;
            else
                continue;
        }
        n=i;
        QuickSort(paixu,1,n);
        printf("排序后的结果：\n");
    
        //输出排序后的数组
        for(i=1;i<=n;i++)
        {
            printf("%d ",paixu[i]);
        }
        printf("\n");
        return 0;
    }

CB下运行结果：  
![这里写图片描述][SouthEast 1]

总结：快递排序不是很难，主要是递归思想的运用。完整的写出代码对于我还有点难度。阅读算法并实现算法是一项重要的能力。以后还得加强联系。虽然代码按照严蔚敏奶奶的写，但是每一步都理解了。希望各位多多交流和指正！

[SouthEast]: /images/20220705/b2f19bbc06e047619b11dc5be56a7960.png
[SouthEast 1]: /images/20220705/be65bbfb91fa43af97e3a9f37bd43244.png