【快速排序】网络上的挖坑法和一些自己的理解

60 阅读 0 评论 40 点赞

我是靠谱客的博主轻松香菇，最近开发中收集的这篇文章主要介绍【快速排序】网络上的挖坑法和一些自己的理解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

参考网址：白话经典算法系列之六快速排序快速搞定

前言-碎碎念

从学计算机到现在，快速排序至少反复学了5次了，
第一次没搞懂，第二次没记住，第三次忘了重新看，第四次认真背下来，第五次就在两周前
但是今天腾讯面试官问我的时候，我还是做不出来。有点绝望，好像人生剩下的大多数都是遗忘和遗憾。
有时候想想自己擅长什么，其实没什么擅长的，
问问自己大学四年都学到了什么，其实好像也没学到什么，
问问自己大学四年做成了什么事，好像也没做成什么。
好像还是最初入学考了第一次考试，看着别人拿着20分的满分，自己拿着13分快不及格的那个自己。
难道我真的是个蠢人吗……
也许方法不对吧，也许我真的是个没有毅力的人，
但是我对自己说，至少你还知道很多其他的东西，别放弃啊。
看到的不能若理解无用，理解了才能认识，认识了才能感受它

正题：

挖坑法的核心就是，在序列的某个位置挖一个坑，然后用坑的左右的数字去填坑
例如：（用 # 表示坑）

1 2 4 56 9 5 4 0

在k=0的位置挖一个坑:
并且用中间变量把坑里的数字保存下来得到# 2 4 56 9 5 4 0
为了使得序列有序，自然要把大的往右边挪动，小的往左边挪动，以坑里的内容为参照进行移动。建立游标i和j，如果j位置的值比坑里的数字大，j就左移，直到找到比坑里的数字小的数字，就原地挖坑，把坑里的东西丢到之前的那个坑里（无论何时，路上的坑只有一个）；然后看i，如果数组在i位置的值比原来坑里的小，i就右移直到找到比坑里的数字大的数字，原地挖坑，并填好之前的坑。

i=0           j=8  #=1
# 2 4 56 9 5 4 0

这样一来比原先的坑大的一定在现在的坑的右边了，
比原来的坑小的一定在现在的坑左边了，
把最后挖出来的填到最初的坑里（所以这个坑的位置就是该数字的位置！）
从而可以对坑左右再进行快排（分治的思路），这样一来，每一次快排都可以找到一个固定的位置
从而得到结果有序。
在这里插入图片描述
第一次排出红圈中内容，第二次排出蓝括号内容，
所以说是挖坑+分治
python语言版本:

def quick_sort(li):
    # 被分解的Nums小于1则解决了
    if len(li) <= 1:
        return li
    
    # 分解    
    temp = li[0]
    left = [i for i in li[1:] if i < temp xss=removed>= temp]
    
    # 递归求解即分治
    left = quick_sort(left)
    right = quick_sort(right)
    # 合并
    return left + [temp] + right
 
quick_sort(nums2)

C语言版本：

#include <stdio.h>
void print(int a[],int p,int e)
{
    int i=0;
    for(i=p; i<=e; i++)
    {
        printf("%d ",a[i]);
    }
    printf("n");
}


void quick_sort(int s,int k,int a[])
{
    if(s<k)
    {
        int i=s,j=k;
        int tmp=a[i];
        while(i<j)
        {

            while(i<j && a[j]>=tmp)
            {
                j--;
            }
            if(i<j)
            {
                a[i]=a[j];
                i++;
            }

            while(i<j && a[i]<tmp)
            {
                i++;
            }
            if(i<j)
            {
                a[j]=a[i];
                j--;
            }
        }
        a[i]=tmp;
        quick_sort(s,i-1,a);
        quick_sort(i+1,k,a);
    }


}

int main()
{
    int length;
    scanf("%d", &length);
    int i=0;
    int num[20];
    for(i=0; i<length; i++)
    {
        scanf("%d",&num[i]);
    }
    quick_sort(0,length-1,num);
    for(i=0; i<length; i++)
    {
        printf("%d ",num[i]);
    }
}