快速排序的划分及其扩展



快速排序之划分及其拓展：

（一）快速排序中的划分：时间复杂度为O(n)

（0）快速排序，冒泡排序都属于是交换排序，因为都需要用到交换两个元素的值。是不稳定的排序。

（1）方法一：
 int partition(DataType array[],int left, int right){
  
  DataType pivot=array[left];//选择一个枢纽元，同时在left处挖了一个坑 while(left<right){
   while(left<right && array[right]>pivot)//在右边找到比pivot小的元素
   right--;  array[left]=array[right];//填left处的坑，同时在right处有一个坑
  while(left<right && array[left]<pivot)//在左边找到比pivot大的元素
   left++;  array[right]=array[left];
 }
 array[left]=pivot;
  return left;
 }（2）方法二：
int partition(DataType array[], int left ,int right){
  
  int mid=(left+right)/2; DataType pivot=array[mid];
  int start=left;
  int end=right; while(start<end){
   while(start<end && array[end]>=pivot)//寻找出右边小于pivot的元素
   end--;  while(start<end && array[start]<pivot)//寻找出左边大于等于pivot的元素
   start++;  if(start<end){
    swap(&array[start], & array[end]);//交换array[start]与array[end];
    start++;
    end--;
   } }
 swap(&array[mid],&array[start]);
  //使array[mid]归位，即array[left,mid-1]都小于array[mid]。
 return start;
 }（3）递归的快速排序：
 void quickSort(DataType array[],int left, int right){
  int start=left;
  int end=right;
  DataType pivot=array[start]; while(start<end){
   while(start<end && array[end]>pivot)
   end--;  array[start]=array[end];
  while(start<end && array[start]<pivot)
   start++;
   array[end]=array[start]; }
 array[start]=pivot;
 quickSort(array,left,start-1);
  quickSort(array,start+1,right);
 }

（4）非递归的快速排序：

1）思想：

仿造二叉树的先序遍历的非递归实现；

1.建立一个栈，栈中的每个元素为一个结构体，包含low,high两个字段，low,high分别为某个子数组的首尾下标；
2.先将(0,n-1)进栈，在栈不空时循环：出栈一个子序列array[low,high]，然后将array[low]作为枢纽元，对array[low,high]进行划分，分为两个子序列array[low,i-1]和array[i+1,high]。然后将[lwo,i-1]和[i+1,high]进栈

2）代码实现：
 void quickSort(DataType array[], int length){
  
  struct Elem{        //定义栈中的每个元素
        int low;
        int high;
  } ; Elem stack[Maxsize];
  int top=-1; int start,end ;
  int startTemp,endTemp; DataType pivot;
 top++;//0号元素进栈
  stack[top].low=0; stack[top].high=length-1;
 while(top>-1){
  start=stack[top].low;//出栈
   end=stack[top].high;
   top--;  startTemp=start;
   endTemp=end;  if(start<end){
    pivot=array[start];   while(startTemp<endTemp && array[endTemp]>pivot)
    endTemp--;
    array[startTemp]=array[endTemp];   while(startTemp<endTemp && array[startTemp]<pivot)
    startTemp++;   array[endTemp]=array[startTemp];
   }  array[startTemp]=pivot;
  top++;//将左半区间[start,startTemp-1]进栈
   stack[top].low=start;  stack[top].high=startTemp-1;
  top++;//将右半区间[startTemp+1,end]进栈
   stack[top].low=startTemp+1;  stack[top].high=end;
  }
 }----------

（二）给定一个字符串，有大小写字母，写一个函数将小写字母放到前面，大写字母放到后面。

（1）思想：
根据快速排序中的划分思想；比pivot小的元素都在pivot左边，比pivot大的元素都在pivot右边。

（2）代码实现：

void partitionTemp(char *a ){
  
  char * pstart=a;//a的第一个元素的位置
  char * pend=a+strlen(a)-1;//a的最后一个元素的位置 while(pstart<pend){
 //从左往右查找，找第一个大写字母
   while( *pstart && (*pstart<'z' && *pstart>'a' ) )
   pstart++;  if(*pstart=='\0') break;
 //从右往左，找出第一个小写字母
   while(*pend<'Z' &&  *pend>'A')
   pend--;  if(i<j){
    swap(pstart,pend);//交换*pstart,*pend
   }  pstart++;
   pend--;
  }
 }

3）注意：
1.此中为双向扫描，比单向扫描快。
2.只可以保证小写字母在大写字母，不可以保证移动前后小写字母的顺序不变。
----------

（三）给定一个字符串，有字母，有数字，要求将数字放到字母前面，且数字，字母的先后顺序不变。

1）举例：
如原始字符串为"a12bcde3"则变为"123abcde".

2）思想：
1.建立两个队列，分为存储字母和数字。
2.扫描一遍字符串，字母添加到字母队列，数字添加到数字队列，
3.然后将数字队列和字母队列分别出队。