学数据结构时看过快速排序,但是没有具体去分析,今天静下心来,仔细看了一下这个算法,算是明白了,和大家分享一下,也方面以后查询。 其实快速排序的核心思想是分治策略,即先分解再递归求解,最后再合并。
具体来说就是在待排序记录序列中选取一个记录(通常先选取第一个记录)为驱轴,其关键字设为K1,然后将其余关键字小于K1的记录移到前面,而将关键字大于K1的记录移到后面,这样K1就将记录分成了两部分,这有点类似于二分查找。在一次划分之后,对分割后的子表继续按上述原则进行分割,直到所有的子表长不超过1为止,此时待排序记录序列就变成了一个有序表。
下面是我写的一个测试程序:
- #include <stdio.h>
- #define N 8
- void quicksort(int a[],int m,int n);
- int quickpass(int a[],int left,int right);
- int main()
- {
- int i,m,n;
- int a[N]={48,63,35,76,54,12,35,88};
- m=0;
- n=N-1;
- quicksort(a,m,n);
- for(i=0;i<N;i++) //排序后的数据
- printf("%d ",a[i]);
- printf("\n");
- return 0;
- }
- void quicksort(int a[],int m,int n)
- //参数m表示每个子表的第一个元素,n表示每个子表的最后一个元素
- {
- int p;
- if(m < n)
- {
- p=quickpass(a,m,n); //调用一趟快速排序,寻找枢轴,以轴元素为界限将数组划分成两个子表。
- quicksort(a,m,p-1); //对左部子表快速排序
- quicksort(a,p+1,n); //对右部子表快速排序
- }
- }
- int quickpass(int a[],int left,int right)
- {
- int x,low,high;
- x=a[left]; //记录枢轴元素
- low=left;
- high=right;
- while(low < high)
- {
- while(low < high && a[high] >= x) high--;
- //high从右向左找小于x的元素
- if(low < high)//找到小于x的记录则进行交换。
- {a[low] = a[high];low++;}
- while(low < high && a[low] < x) low++;
- //low从左向右找大于x的元素
- if(low < high)//找到大于x的记录则进行交换。
- {a[high]=a[low];high--;}
- }
- a[low]=x; //将枢轴元素保存到low=high的位置
- return low; //返回枢轴元素的位置
- }
如果有疑惑的可以提出来。或者自己调试一下可能会理解的更透彻一些。。。
阅读(9964) | 评论(2) | 转发(3) |