C语言实现快速排序的方法及优化.docx
第
C语言实现快速排序的方法及优化
目录前言快速排序实现逻辑1.hoare版本2.挖坑法3.前后指针版本快速排序优化1.三数取中法选key2.递归到小的子区间时,可以考虑使用插入排序快速排序的特性总结
前言
在学数据结构的第一节课就知道了数据结构课程是要管理并且学会操作数据,当然操作数据首先想到的就是数据的排序,排过顺序的数据的使用价值才够大。前面我们学习了顺序表也学习了链表等等,这些就是储存数据的方法,下面我们来看一看传说中的快速排序的特点与效率怎么样
快速排序
快速排序,又称划分交换排序(partition-exchangesort)
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
实现逻辑
快速排序使用分治法(Divideandconquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
①从数列中挑出一个元素,称为基准(pivot)
②重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
③递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
//假设按照升序对array数组中[left,right)区间中的元素进行排序
voidQuickSort(intarray[],intleft,intright)
if(right-left=1)
return;
//按照基准值对array数组的[left,right)区间中的元素进行划分
intdiv=partion(array,left,right);
//划分成功后以div为边界形成了左右两部分[left,div)和[div+1,right)
//递归排[left,div)
QuickSort(array,left,div);
//递归排[div+1,right)
QuickSort(array,div+1,right);
}
上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。将区间按照基准值划分为左右两半部分的常见方式有:
1.hoare版本
代码
intPartSort1(int*a,intbegin,intend)
intleft=begin,right=end;
intkeyi=left;
while(leftright)
//右边先走,找比a[keyi]小的
while(leftrighta[right]=a[keyi])
right--;
//左边先走,找比a[keyi]大的
while(leftrighta[left]=a[keyi])
left++;
//交换左右边
Swap(a[left],a[right]);
//交换keyi与交点的值
Swap(a[left],a[keyi]);
keyi=left;
}
2.挖坑法
代码
//挖坑法
intPartSort2(int*a,intbegin,intend)
intkey=a[begin];
intpiti=begin;
while(beginend)
//右边找小,填到左边的坑里面去。这个位置形成新的坑
while(beginenda[end]=key)
--end;
a[piti]=a[end];
piti=end;
//左边找大,填到右边的坑里面去。这个位置形成新的坑
while(beginenda[begin]=ke