快速排序算法与实现(c++)

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法的基本思想

　　快速排序的基本思想是基于分治策略的。对于输入的子序列p[m..n]，如果规模足够小则直接进行排序，否则分三步处理：

分解(Divide)：将输入的序列p[m..n]划分成两个非空子序列p[m..k]和p[k+1..n]，使p[m..k]中任一元素的值不大于p[k+1..n]中任一元素的值。

递归求解(Conquer)：通过递归调用快速排序算法分别对p[m..k]和p[k+1..n]进行排序。

合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在p[m..k]和p[k+1..n]都排好序后不需要执行任何计算p[m..n]就已排好序。

　　这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。

代码：

// qsort.cpp : 定义控制台应用程序的入口点。//

#include "stdafx.h"

void print_data(int *data, int start, int end){ for (; start < end; ++start )  {  printf("%d ", *(data+start)); } printf("/n");}

void quick_swap(int *data, int i, int j){ int tmp;

 tmp = *(data+i); *(data+i) = *(data+j); *(data+j) = tmp;}

int quick_partition(int *data, int start, int end){ int v; int i,j;

 v = *(data+start); i = start; j = end;

 do  {  do  {   ++i;   if (i == end - 1)   {    break;   }  }while((*(data+i) < v));    do   {   --j;   if (j == start)   {    break;   }  } while((*(data+j) > v));

  if (i >= j)  {   break;  }  quick_swap(data, i, j);  print_data(data,start, end); } while(true);

 *(data+start) = *(data+j); *(data+j) = v; print_data(data, start, end);

 return j;}

void quick_sort(int *data, int left, int right){ if (left < right) {  int pos;  pos = right + 1;  pos = quick_partition(data, left, pos);  quick_sort(data, left, pos-1);  quick_sort(data, pos+1, right); }}

int _tmain(int argc, _TCHAR* argv[]){ int keys[] = { 5, 8, 9, 15, -18, 150, 0, 55, -5, -108, 100 }; int i; const int keys_size = (sizeof keys) / (sizeof *keys);

 print_data(keys, 0, keys_size);

 quick_sort( keys, 0, keys_size-1); print_data(keys, 0, keys_size);

 printf("/nPress ENTER to quit...");     getchar();

 return 0;}