|
http://roclinux.cn/?p=566
全详细解析 ：http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.3.htm
昨天笔试google，不甚理想。算法大题用到了快排算法。在这里温故知新一下，以绝后患:D
大家一定对冒泡排序(Bubble Sort)非常熟悉吧，这种排序算法的思路很简单，但是由于时间复杂度比较高（O(n*n)），所以渐渐被更高效的算法所取代。这些高效算法中就包括了著名的快速排序算法（Quick Sort）。
快速排序算法的基本思想是，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
一趟快速排序的算法是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录相互交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。由此可以该“枢轴”记录最后所落的位置i作为分界线，将序列分隔成两个子序列。
实际上low和high可以被理解为位置标志，它们所指向的只是位置。而pivotkey就是一个数值，它被选取被序列中的一个特定元素。在每趟的快排当中，都是low和high所指位置的元素和pivotkey来做比较。
快速排序的算法要分两大块：
第一大块：一趟快速排序的算法程序，我们将其定为一个函数partseq()
第二大块：整个快速排序算法程序，此程序要调用第一大块的partseq函数，而且在这个部分，我们使用了递归算法来实现多趟快排。
===================================================================================
快速排序算法源代码如下：
[rocrocket@wupengchong Sort_Method]$ cat -n Quick_Sort.c
#include<unistd.h>
#include<stdio.h>
#include<string.h>
int partition(int arr[],int low,int high)
{
arr[0]=arr[low];
while(low<high){
while((low<high)&&(arr[high]>arr[0])) high--;
arr[low]=arr[high];
while((low<high)&&(arr[low]<arr[0])) low++;
arr[high]=arr[low];
}
arr[low]=arr[0];
printf("pivotindex:%d/n",low);
return low;
}
void si_sort(int arr[],int low,int high)
{
int pivotindex;
if(low<high){
pivotindex=partition(arr,low,high);
si_sort(arr,low,pivotindex-1);
si_sort(arr,pivotindex+1,high);
}
}
void print_arr(int arr[],int arrnum){
int i=1;
printf("Sorted sequence:");
for(;i<=arrnum;i++){
printf("%d ",arr[i]);
}
printf("/n");
}
int main()
{
int index=1,arrnum;
char s[100],*sp;
int num[10]={0};
printf("Please input(ex:3 5 6 1 7 14):");
fgets(s,sizeof(s),stdin);
sp=strtok(s," ");
while(sp!=NULL){
num[index++]=atoi(sp);
sp=strtok(NULL," ");
}
arrnum=index-1;
printf("You have input %d numbers./n",arrnum);
si_sort(num,1,arrnum);
print_arr(num,arrnum);
return 0;
}
over~ | 
转播
