快速排序

Sep 12, 2011 • {"display_name"=>"pensz", "login"=>"pensz", "email"=>"email", "url"=>""}

快速排序是分治法的思想，先设定一个标志，保证左边的数据不大于该标志，右边的数据都不小于该标志。然后分别对左右区域使用同样的处理方法，最终得到的序列即为有序序列。

下面是 c++ 的快速排序。

#include <iostream>
using namespace std;

/**
 * 调整数据，使得在一个位置左边的数据均小于 pivotkey， 右边的数据均大于 pivotkey
 */
int Partition(int *p, int low, int high) {
 int pivotkey = p[low];
 while (low < high) {
 while (low < high && p[high] > pivotkey) --high;
 p[low] = p[high];

 while (low < high && p[low] <= pivotkey) ++low;
 p[high] = p[low];
 }

 p[low] = pivotkey;

 return low;
}

/**
 * 快速排序
 */
void QuickSort(int *p, int begin,  int end) {
 if (begin < end) {
 int pivot;

 pivot = Partition(p, begin, end); // 进行一次分区
 QuickSort(p, begin, pivot-1); // 对左边的进行快速排序
 QuickSort(p, pivot+1, end); // 对右边进行快速排序
 }
}

int main() {
 int i, length, *p;
 cin >> length;
 p = (int *) malloc (length * sizeof(int));
 for (i=0; i<length; ++i) {
 cin >> p[i];
 }

 cout << "original" << endl;
 for (i=0; i<length; ++i) {
 cout << p[i] << endl;
 }    

 QuickSort(p, 0, length-1);

 cout << "sorted" << endl;
 for (i=0; i<length; ++i) {
 cout << p[i] << endl;
 }

 return 0;
}