手撕快速排序算法

Page content

身为程序员啊,还是要多刷刷题,工作一年多连快排都给忘了,今天捡一下。

快速排序

快速排序,顾名思义,没道理,就是快!快速排序是分而治之的代表算法之一,其基本思想很简单,选取一个基准,将一个待排序的序列分为两部分,一部分比基准大,一部分比基准小,接下来就分别针对这两部分重复算法,直到整个序列都有序。

那么,快速排序的三大要素如下:

  • 选取基准:选取基准的方法有:1. 取第一位或末位 2. 取中位数 3. 随机选取
  • 分割序列:采用“挖坑填坑”的思想,将序列分为两部分,左边小于基准,右边大于基准
  • 重复分割:对子序列依次进行选基准,分割,直到序列为空或者只有一个元素。

快排的平均时间复杂度为O(logn),最坏情况,当本来就有序时,退化成O(n^2)

算法实现:

#include <stdio.h>
#include <iostream>
#include <stack>

int parttion(int arr[], int left, int right)
{
    int i = left;
    int j = right;
    int tmp = arr[left];  // 选基准,这里挖了一个坑
    while (i < j)
    {
        while (i < j && arr[j] >= tmp) // 从右至左找到第一个小于基准的数
        {
            j--;
        }
        if (i < j) // 将小于基准的数填进基准所在的坑,这下大于基准的一方多出来一个坑
        {
            arr[i] = arr[j];
        }

        while (i < j && arr[i] <= tmp) // 从左至右找到第一个大于基准的数
        {
            i++;
        }
        if (i < j) // 将大于基准的数填进上一个坑,这下小于基本的一方多出来一个坑
        {
            arr[j] = arr[i];
        }
    }
    arr[i] = tmp; // 将基准填入坑中,完成大于和小于基准的序列分别在基准左边和右边
    return i;
}

// 递归版本
void quicksort(int arr[], int left, int right)
{
    if (left > right)
    {
        return;
    }
    int part = parttion(arr, left, right); 
    quicksort(arr, left, part - 1);
    quicksort(arr, part + 1, right);
}

// 非递归版本,用stack来模拟递归!
void quicksortNor(int arr[], int left, int right)
{
    if (left > right)
    {
        return;
    }
    stack<int> s;
    s.push(left);
    s.push(right);

    while (!s.empty())
    {
        int right = s.top();
        s.pop();
        int left = s.top();
        s.pop();
        if (left < right)
        {
            int part = partition(arr, left, right);
            s.push(left);
            s.push(part - 1);
            s.push(part + 1);
            s.push(right);
        }
    }
}

int main()
{
    int arr[10] = {49, 38, 65, 97, 76, 13, 27, 49, 100, 20};
    quicksort(arr, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        printf("%d\n", arr[i]);
    }
}

Q:快排找中位数

问题:在一个无序数组中找中位数

利用快排的思想,当part为中位数的index的时候退出循环。

int findMidByQ  uickSort(int arr[], int left, int right, int len)
{
    if (left >= right)
    {
        return arr[left];
    }
    int part = partition(arr, left, right);
    int mid = len / 2;
    if (part == mid) // 找到中位数
    {
        return arr[part];
    }
    else if (part > mid) // 从左边继续找
    {
        return findMidByQuickSort(arr, left, part, len);
    }
    else // 从右边继续找
    {
        return findMidByQuickSort(arr, part + 1, right, len);
    }
}