快速排序
----记得大二上课时候,这个排序折磨了我一阵,可能确实是没有学习的天赋吧,今天来解决它!gogogo!
一、排序思路:
快速排序(Quicksort)是由冒泡排序改进而得到的,它的基本思想是在待排序的n个元素中任取一个元素,我们通常取第一个元素,把该元素放入恰当位置后,数据序列被此元素划分成两部分,所有关键字比该元素关键字小的元素放置在前一部分,所有比它大的元素放置在后一部分(这不是废话吗?)。之后对产生的两个部分分别重复上述过程,直至每部分只有一个元素或者为空为止。言简意赅,就是用递归吧。
二、步骤再阐述:
1、先从整个数组中取出一个数作为我们的基准。
2、比基准大的通通跑去右边,剩下的小可怜就都丢到左边。
3、递归操作,直至还剩一个元素或为空。
三、算法概述:
int partition(int data[],int low,int high) //一趟划分{ int temp; temp=data[low]; //以data[low]为基准 while(low=temp) high--; //从右向左扫描,找一个小于temp的data[high] data[low]=data[high]; //找到这样的R[high],放入data[low]处 while(low <=temp) low++; //从左向右扫描,找一个大于temp的data[low] data[high]=data[low]; //找到这样的data[low],放入data[high]处 } data[low]=temp; return low;}void QuickSort(int data[],int low,int high) //对data[low..high]的元素进行递增快速排序{ int i; if (low
四、我们把main函数写起来,然后把完整的程序运行一下如下:
int main(){ int data[N]; int a[]={ 13,8,2,9,34,1,69,24,35,79}; int n = (int)(sizeof(a)/sizeof(*a)); for(int i=0;i
结果确实是按照有序排列了,我们还可以考虑输出每一次划分的结果,这里就不一一描述了。