算法-快速排序

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

前言

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

核心思想

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

示例

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 )。

结语

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