快速排序算法详细讲解c++版

布满荆棘的人生 2022-06-03 01:49 200阅读 0赞

快速排序算法

1.首先我需要对快速排序算法下个定义：什么是快排呢？或者是排序的指导思想比如一个待排序的数组  
int iArray\[\] = \{5,4,45,878,45\}; 我们需要把这个数组从小到大进行排序。  
我们首先需要找到一个参数轴 也就是参数的数据 有了参考数据我们就把数据分成2个部分，一个数据全部是大于或者等于当前参考数据，另一部分数据都是小于或者等于当前参考数据的。

下面分析快排算法的执行过程。 假如开始我们得到一个参考数值是第一个也就piovt = 5  
这个时候我们的目的就是要实现5这个数的右边都是大于或者等于他，反之左边都是小于或者等于他的  
我们是采用2个索引指示器int leftIndex = 0; 这个指示器我们开始是保存了第一个元素  
int rightIndex = 4 保存了数组中最后一个数据 首先我们会把这个piovt轴值先保存下来，这样当前轴对应的内存区域就可以被其他数据覆盖了。 这个时候由于我们右端都是大于5的数，因此我们第一趟快排可以先从右边找到一个小于5的数 然后保存在当前piovt空出来的位置。 比如我们找到的数据就是4 这个时候我们就把4写入到5这个位置去了，这个时候leftIndex++操作这个5提前保存在了临时piovt变量中，不用担心被覆盖，这个时候4位置的内存数据就可以被覆盖了。 现在我们在从左边也就是leftIndex指示的位置开始找一个比5要大的数据 这个时候我从索引为1开始找  
这个时候注意 我们从右边和左边找的索引已经相当因此这轮查询操作完毕 什么意思就是说我们当前这个数据已经被调整过，不能重复去调整  
第一轮排序之后得到的数组就是4 4 45 878 45 索引1对应的内容是可以被覆盖的 5的那个值被提前保存在了piovt中

现在开始第二轮排序 这个时候的leftIndex =1 rightIndex = 1 我们这个时候发现左右指示器已经相等了，说明右边的数据都是大于5的了 左边的数据都已经小于5了  
那么我们就可以把这个轴值写入到当前的空位中 也就是索引为1 这个时候数组就变成了  
4 5 45 878 45 我们发现5两边的数据大小的规则是符号我们需要的

这个时候5已经把数据分成2部分了 这个时候我在用递归 我们专门针对 4 和 45 878 45 这2部分分别在进行快排。 其实在快排之前我们需要做个判断数据是不是大于1 否则就没有必要在排序了

下面来上具体代码

#include "stdafx.h"
    #include<iostream>
    
    void QuickSort(int iArray[],int left, int right)
    {
        //快速排序之前先判断一下当前待排序数组元素个数是不是大于1 否则就没有必要排序
        if (left >= right)
        {
            //直接退出排序代码  没有必要进行排序了
            return; 
        }
    
        //开始进行快排算法
        //首先我们先保存left索引对应的数据  当前数据作为切割数组的轴
        int piovt = iArray[left];
    
        //定义临时变量保存数组2端的索引
        int leftIndex = left;
        int rightIndex = right;
    
        while (leftIndex < rightIndex)
        {
            //现在我们通过循环从右边开始搜索一个比轴值小的数据
            while (leftIndex < rightIndex)
            {
                //如果右边的数大于当前的参数轴值
                if (piovt <= iArray[rightIndex])
                {
                    //右端索引指示器左移
                    rightIndex--;
                }
                else
                {
                    //说明我们右端出现比轴值更大的数据
                    //这个时候我们就可以把这个更大的数据填充到索引轴索引对应的地方
                    iArray[leftIndex] = iArray[rightIndex];
                    leftIndex++;
                    //我们需要跳出循环了当前工作完毕
                    break;
                }
            }
    
            //从左边开始搜索一个比轴值更大的数填写上次留下的坑
            while (leftIndex < rightIndex)
            {
                //如果左边的数据小于轴值 我们索引指示器就往右走
                if (piovt >= iArray[leftIndex])
                {
                    leftIndex++;
                }
                else
                {
                    //说明我们在左端找到了比轴值更大的数据
                    iArray[rightIndex] = iArray[leftIndex];
                    rightIndex--;
                    break;
                }
            }
        }
    
        iArray[leftIndex] = piovt;
    
        QuickSort(iArray, left, leftIndex - 1);
        QuickSort(iArray, rightIndex + 1, right);
    }
    
    int main()
    {
        int arry[] = { 3,21,87,1,21,10 };
    
        QuickSort(arry, 0, 5);
    
        for (int i = 0; i < 6; i++)
        {
            std::cout << arry[i] << std::endl;
        }
        return 0;
    }

快速排序算法的时间复杂度分析：……..