《数据结构》——排序知识点之快速排序代码笔记

排序和查找的关系

• 排序是查找的前提
• 排序是重点

  排序：

  冒泡
  插入
  选择
  快速排序
  归并排序

  #include <stdio.h>
  void QuickSort(int * a,int low,int high);
  int FindPos(int * a,int low,int high);
  int main(void)
  {
   int a[6]={2,1,-10,5,4,3};
   int i;
   QuickSort(a,0,5);//第二个参数表示第一个元素的下标，第二个参数表示最后一个元素的下标
   for (i=0;i<6;i++)
       printf("%d ",a[i]);
   printf("\n");
  }
  void QuickSort(int * a,int low,int high)
  {
   int pos;
   if(low<high)
   {
       pos=FindPos(a,low,high);
       QuickSort(a,low,pos-1);
       QuickSort(a,pos+1,high);
   }
  }
  int FindPos(int * a,int low,int high)
  {
   int val=a[low];
   while(low<high)
   {
       while(low<high&&a[high]>=val)
           --high;
       a[low]=a[high];
       while(low<high&&a[low]<=val)
           ++low;
       a[high]=a[low];
   }//while循环终止后，low和high一定是相等的
   a[low]=val;
   return low;//return low或high都可以，但是不能为val，a[low],a[high]
  }