【转】交换排序之快速排序 - 平头弟

TI

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

2019-07-19 14:29发布

站内问答 / TI MCU

3659 6

快速排序：快速排序（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条回答

1楼-- · 2019-07-19 17:05

精彩回答 2 元偷偷看……

2楼-- · 2019-07-19 22:09

采用分割的办法可以快速的进行数据的排序定位的，提高了效率

3楼-- · 2019-07-19 22:38

这个是采用二分法的进行处理数据的，效率成倍提高的。

4楼-- · 2019-07-20 03:13

还是用的冒泡算法比较多。

5楼-- · 2019-07-20 08:41

楼主的交换算法有更加简介的吗？

6楼-- · 2019-07-20 09:38

精彩回答 2 元偷偷看……

一周热门更多>

相关问题

相关文章