Michael

写写代码,说说人生

您好,我是Michael,欢迎来到我的个人家园。
代码搬运工,目前就职于XX证券,努力修行中。


H5 / Java / Objc / Swift / Vue / RN

算法-快速排序

这个排序算法的命名有点随意啊,这种态度怎么行

前言

这个算法感觉脱离了简单算法的范畴,脑袋稍微要转那么一点儿弯,排序代码倒是多了不少。

核心思想

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

示例

  1. 首先,我们枪打出头鸟,把第一个数10给拎出来,留下一个坑位(坑位很重要*),做参照物:基数。 快速排序-基数.png
    • 有了基数之后,我们建立左右指针各一个,分别放在最左边和最右边的位置,右指针逐个对比,遇到比基数小的值就停下,很巧的是,右边第一个数就比基数小。 快速排序-右指针
.png
  • 找到比基数10小的值:3,把3挪到空出来的坑位中,3被取走从而留下了新坑,右指针的位置停留在该处,下一次从这里开始向左查找。 快速排序-填坑.png

  • 右指针操作结束后,左指针从左边开始出发,左指针要找到比基数:10更大的数,然后把这个数放进坑里。 快速排序-左指针.png

  • 左指针找到了比基数大的值:11,将11放入坑位,并且留下新坑,左指针的位置停留在该处,下一次从这里开始向右查找。 快速排序-左指针对比.png

  • 左指针结束行动,又轮到右指针,右指针从原地出发,操作和之前一致。 右指针-再次出发.png

  • 左右指针间隔调用 快速排序-左指针再次出发.png

  • 直至左右指针相遇 快速排序-左右指针相遇.png
  • 最后我们以基数为中心得到左右两边两组数据{3,5,3,1,7,6,8,10}和{33,11},然后再将这两组数据分别进行递归排序,再分出子集也是如此。

C语言代码

#pragma mark - 快速排序
int partition(int arr[], int len, int left, int right) {
    int baseNum = arr[left];
    // 坑位
    int baseIndex = left;
    printf("baseNum:%d\n",baseNum);
    // 左右查找指针不相交
    while (left < right) {
        // 从右向左 找到大于等于基数的值
        while (left<right && arr[right]>=baseNum) {
            right--;
        }
        // 找到后填坑
        arr[baseIndex] = arr[right];
        // 留出新坑
        baseIndex = right;
        printf("调整1\n");
        printfArr(arr, len);
        // 从右向左 找小于等于基数的值
        while (left < right && arr[left]<=baseNum) {
            left++;
        }
        // 找到填坑
        arr[baseIndex] = arr[left];
        // 留出新坑
        baseIndex = left;
        printf("调整2\n");
        printfArr(arr, len);

        
    }
    // 基数填最后一个坑
    arr[baseIndex] = baseNum;
    return baseIndex;
}

void fastSort (int arr[], int len, int left, int right) {
    if (left < right) {
        printf("调整前\n");
        printfArr(arr, len);
                
        int baseIndex = partition(arr, len, left, right);
        
        printf("调整3\n");
        printfArr(arr, len);

        
        fastSort(arr, len, left, baseIndex-1);
        fastSort(arr, len, baseIndex+1, right);

    }else{
        printf("结束\n");
        printfArr(arr, len);
    }
}

时间复杂度

快速排序是不稳定的,排序时间平均时间复杂度是O ( nlgn )。

结语

在学习算法的过程中,整个思维沉浸进去,直至水落石出的时候,感觉像给大脑做了一个健身操。

最近的文章

Mac知识整合

.DS_Store 文件是什么?.DS_Store 是 Mac OS 保存文件夹的自定义属性的隐藏文件,如文件的图标位置或背景色,相当于 Windows 的 desktop.ini。1,禁止.DS_store 生成: 打开 “终端” ,复制黏贴下面的命令,回车执行,重启Mac即可生效。defaults write com.apple.desktopservices DSDontWriteNetworkStores -bool TRUE2,恢复.DS_store生成:de...…

iOS继续阅读
更早的文章

算法-插入排序

生活总是充满了惊喜,无论是惊还是喜。核心思想有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序。示例对于长度为n的数组,全部完成排序需要经过n-1轮的查找,首先我们从第二个数开始,向前比较,如果比前面的数小,则继续向前对比,直至遇见大于前置位数字时,或者到了数组的最前...…

算法设计继续阅读