Pulpcode

捕获，搅碎，拼接，吞咽

0%

聊聊快速排序

发表于 更新于 分类于 Valine：

好吧，你可以在网上搜到一大堆的快速排序的代码，包括一些相似的博客（说明+代码实现），所以我想写一篇关于自己所理解的快速排序。

本文假设你明白什么是快速排序= =!

分区

快速排序会以一个数列的某个元素为基准，把一个数列分成两部分，小于这个基准的为一部分，大于等于的作为一部分，然后分别为这两部分递归求解，这是书上，和教程上的说法，这样的描述很容易让人误解，我觉得算上这个基准应该是三部分，基准并没有参加进一步递归，如果你不看别人的代码，第一次通过定义试图写一个快速排序，很容易把基准加入到第二个部分，导致无穷递归，所以我常对快速排序这样描述，快速排序每次分区后，都会确定一个基准的位置（这个位置是它应有的）

python写法

我喜欢用python写这种算法，因为python的许多特性让我们很容易编写程序，也就是表达我们的思想，(当然这种特性不是指lis.sort())比如我们如果用c语言写，你不得不写一些include，写主函数，关键是你要在用几层for和while在数组中移动，所以我们常常在i++的多一和少一中出错，而且对于别人也不容易阅读，对于python而言，list的特性让我们容易描述算法，而且，等你描述成功，明白了，再改成c的也不迟，不过网上的许多python版的qsort实在看不下去，因为他们在“用python写c代码”。

python版qsort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def qsort(lis):
    if len(lis) == 0:
        return []
    else:
        low = []
        hig = []
        for x in lis[1:]:
            if x < lis[0]:
                low.append(x)
            else:
                hig.append(x)
        low = qsort(low)
        hig = qsort(hig)
        return low+lis[:1]+hig

我觉得就很容易理解，不过是长了点，不符和pythonic，wiki百科里面的python版qsort就好多了，

1
2
3
4
def qsort(L):
   if not L: return []
   return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \
          qsort([x for x in L[1:] if x>=L[0]])

聊聊C的版本，

好吧，面对C语言，你不得不自己操作这个数组，我们在描述快速排序的时候说过，将数组分为两个部分，其实你完完全全可以就用两个数组来分别递归，（就像在合并排序中一样）但是没有效率，所以，我们的分区步骤，往往是在一个数组中完成的，所以它很难读懂。。

看看K&R的书中的qsort：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void qsort(int v[], int left, int right)
{
    int i,last;
    void swap(int v[], int i, int j);/*这种写法是因为早期的c语言所有声明要放在一开始*/

    if(left > = right)/*若数组包含的元素少于两个*/
        return;/*则不执行任何操作*/
    swap(v, left, (left + right)/2);/*将基准元素*/
    last = left;                    /*移动到v[0]*/
    for(i = left+1; i <= right; i++)/*划分子集*/
        if(v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);/*恢复划分元素*/
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

这个版本的qsort，在分区时，不采用第一个元素为基准，而是中间位置的元素，并先把基准存放在aleft，在for循环后，last左边（包括last）都是小于基准的元素，然后恢复基准的位置（因为last位置的元素是小于的，所以交换没问题），再分别递归调用。

我们在看看其它的c语言版本，是如何分区的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

就像我说的，太多的while，你很容易搞错，

这个版本主要时在一个数组的头和尾分别遍历，在两边找到不符合的元素的时候，就会进行交换，这样当left==right的时候，就分好区了，但是有意思的是相比于swap的版本，这里的交换直接是在赋值，比如：

1
2
3
4
5
6
7
while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }

这没问题马？当然没有，因为基准元素被存放在pivot后，第一个位置就没用了，所以来回的赋值，就是在做一种“交换”，或者用“插入”来形容更符合，在退出大while后

numbers[left] = pivot;

使得基准放到了它应该有的位置。