快速排序

快速排序

#include <iostream>
using namespace std;

#define N 10

int Partition(int *a, int low, int high)
{
  int temp;
  temp = a[low];
  while (low < high)
  {
    while (low < high && temp < a[high])
    {
      high--;
    }
    if (low < high)
    {
      a[low] = a[high];
      low++;
    }
    while (low < high && a[low] < temp)
    {
      low++;
    }
    if (low < high)
    {
      a[high] = a[low];
      high--;
    }
  }
  a[low] = temp;
  return low;
}

void QuickSort(int *a, int low, int high)
{
  int i;
  if (low < high)
  {
    i = Partition(a, low, high);
    QuickSort(a, low, i - 1);
    QuickSort(a, i + 1, high);
  }
}

int main()
{
  int low, high, temp;
  int *a = new int[N];

  for (int i = 0; i < N; i++)
  {
    cin >> a[i];
  }

  QuickSort(a, 0, N - 1);

  for (int i = 0; i < N; i++)
  {
    cout << a[i] << " ";
  }
  cout << endl;
  return 0;
}

• 时间复杂度： 最好的情况是 O(n*log2(n)) ，最坏的情况将退化为冒泡排序为 O(pow(2,n))

测试

[blazehu@MacBook ~]$ g++ -o QuickSort QuickSort.cpp
[blazehu@MacBook ~]$ ./QuickSort
1
3
4
9
6
7
8
2
5
0
0 1 2 3 4 5 6 7 8 9
[blazehu@MacBook ~]$