快速排序

快速排序

快速排序是一种不稳定的排序算法，平均时间复杂度为O(n*logn)。快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-list).步骤为:

• 从数列中挑出一个元素，称为"基准" (pivot)。
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束后，该基准处于数列的中间位置。这个称为分区(partition)操作。
• 递归地(recursive)把小于基准值元素的子数列和大于基准值的子数列排序。

** 快速排序的时间主要花在划分上，所以 **

• 最坏情况：时间复杂度为O(n^2)。因为最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1 元素的时候。
• 最后情况：每次划分选取的基准都是当前无序区的中值。如果每次划分过程产生的区间大小都是n/2，则快速排序运行就快得多。

void Qsort(int a[], int low, int high)
  {
      if(low >= high)
      {
          return;
      }
      int first = low;
      int last = high;
      int key = a[first];

      while(first < last)
      {
          while(first < last && a[last] >= key)
          {
              --last;
          }
          a[first] = a[last];
          while(first < last && a[first] <= key)
          {
              ++first;
          }
          a[last] = a[first];    
      }
      a[first] = key;
      Qsort(a, low, first-1);
      Qsort(a, first+1, high);
  }

快速排序的优化

1. 当待排序序列的长度分割到一定大小后，使用插入排序。
2. 快速排序函数尾部有两次递归操作，我们可以对其使用尾递归优化。优化后，可以缩减堆栈深度，同原来的O(n) 缩减为O(logn),将会提高性能。
3. 从左，中，右三个数中取中间值。