数据结构-排序-快速排序

冷不防 2023-10-04 16:27 53阅读 0赞

### 快速排序 ###

快速排序法又称分割交换排序法，是目前公认的速度最快的排序法，该方法是现在数据中找到一个虚拟的中间值，然后将大于这个中间值的放到右边，小于中间值的放到左边，然后将数组以该中间值分为两组，左边和右边逐步重复上述操作，直到排序完成为止。操作和分割步骤入下：

假设数组有n项R1，R2，R3…Rn，其相应的键值为K1,k2,k3…kn;

*  先假设K的值为第一个键值，将其设置为第一次的中间值
 *  将数组从左向右找到键值Ki，使得Ki>K
 *  将数组从右向左找到键值Kj，使得Kj<K
 *  如果i<j，对调ki和kj，然后继续重复上序操作
 *  如果i>=j，将kj和k对调，并以j为基准点分割成左右两部分，然后将左右两边继续重复这种排序步骤，直到左半边键值等于右半边键值

比如：

因为i<j，所以交换，继续执行

因为i<j，所以交换，继续执行

因为i>j,所以将k和j交换

按照这样的步骤，一次分割左右两侧，继续执行排序

**快速排序法的分析**

*  在最快和平均情况下，时间复杂度为O(nlog2n)。最坏情况就是每次挑中的中间值不是最大就是最小，因为最坏情况下的时间复杂度为O(n^2)
 *  快速排序法不是稳定排序法
 *  在最差的情况和，空间复杂度为O(n)，而最佳情况为O(log2n)
 *  快速排序法是平均运行时间最快的算法

def quick(data,size,left,right):
        #第一个中间值就是data[left]
        if left < right:
            left_next = left + 1    #从中间值的下一个开始往右查找大于中间值的键值
            while data[left_next] < data[left]:
                if left_next + 1 >= size:
                    break
                left_next += 1      #逐个往右边查找出大的那个
            right_pre = right       #右边从right开始查找小于的
            while data[right_pre] > data[left]:
                right_pre -= 1      #逐个往右边查找出小的那个
            #这时候找到了第一个大于和小于中间值的元素，比较两个索引的大小
            #之所以用while，是因为交换完了要接着比较
            while left_next < right_pre:
                #索引小于就交换
                data[left_next],data[right_pre] = data[right_pre],data[left_next]
                #将left_next+1接着查找
                left_next += 1
                while data[left_next] < data[left]:
                    left += 1
                #将right_pre-1接着查找
                right_pre -= 1
                while data[right_pre] > data[left]:
                    right_pre -= 1
            #如果while left_next < right_pre:满足，就接着查找
            #如果不满足，就和中间值换，然后分割左右两个进行继续排序
            data[left],data[right_pre] = data[right_pre],data[left]
            for i in range(size):
                print(data[i],'',end='')
            print()
            #以right_pre为基准点，进行分割左右两个
            #使用递归调用
            quick(data,size,left,right_pre-1)   #以right_pre为分割点分成左右两边，将左边的进行递归调用
            quick(data,size,right_pre+1,right)  #以right_pre为分割点分成左右两边,将右边的进行递归调用
    
    """
    主程序编写
    """
    def main():
        data = [26,3,18,1,67,8,55]
        print("您输入的原始数据是：")
        for i in range(len(data)):
            print(data[i],'',end='')
        print('\n')
        print("排序过程如下：")
        quick(data,len(data),0,len(data)-1)
        print("排序结果是：")
        for i in range(len(data)):
            print(data[i],'',end='')
    
    if __name__ == '__main__':
        main()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210625221600841.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70