|
快速排序： 快速排序（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("\n");
- }
- 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;
- }
|
楼主
标题置顶
标题高亮
