TI

【转】交换排序之快速排序

2019-07-19 14:29发布

站内问答 / TI MCU
3663 6 965
快速排序：快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可 递归进行，以此达到整个数据变成有序序列。时间复杂度：O（n*logn）
最坏：O（n^2）
空间复杂度：O（n*logn）
稳定性：不稳定交换：[cpp] view plain copy
print?

  • void swap(int *a,int *b)  
  • {  
  •     int temp=*a;  
  •     *a=*b;  
  •     *b=temp;  
  • }  
  • int Partitiion(int arr[],int low,int high)  
  • {  
  •     //int pointKey=arr[low];  
  •     while(low<high)  
  •     {  
  •         while(low<high&&arr[low]<=arr[high]) high--;  
  •         swap(&arr[low],&arr[high]);  
  •         while(low<high&&arr[high]>=arr[low]) low++;  
  •         swap(&arr[low],&arr[high]);  
  •     }  
  •     return low;  
  • }  


分治：
[cpp] view plain copy
print?

  • void qSort(int arr[],int low,int high)  
  • {  
  •     int point;  
  •     if(low>=high)  
  •         return ;  
  •     point=Partition(arr,low,high);  
  •     qSort(arr,low,point-1);  
  •     qSort(arr,point+1,high);  
  • }  


举个栗子：[cpp] view plain copy
print?

  • void print(int seq[],int len)  
  • {  
  •     int *p=seq;  
  •     while(p!=&seq[len])  
  •     {  
  •         printf("%d ",*p);  
  •         p++;  
  •     }  
  •     printf(" ");  
  • }  
  • int main()  
  • {  
  •     int Seq[]={11,5,2,3,6,4,8,9,15,12};  
  •     printf("排序前：");  
  •     print(Seq,10);  
  •     printf("排序后：");  
  •     qSort(Seq,0,9);  
  •     print(Seq,10);  
  •     return 0;  
  • }  


友情提示: 此问题已得到解决，问题已经关闭,关闭后问题禁止继续编辑，回答。
6条回答
zhangbo1985
2019-07-19 22:38
这个是采用二分法的进行处理数据的，效率成倍提高的。

一周热门 更多>

相关文章